[seqfan] Antichains and RAM

Elijah Beregovsky elijah.beregovsky at gmail.com
Tue May 5 17:02:33 CEST 2020


Hello, seqfans!
I've been trying to extend A326361 <https://oeis.org/A326361> - the number
of maximal intersecting antichains of sets covering n vertices with no
singletons. To do that I construct a graph on 2^n vertices, where index of
each vertex is encoding a subset of numbers [0,n-1]. For example, for n=5,
vertex 17 (10001 in binary) corresponds to a set (0;4) and 7 (00111) to
(0;1;2). I then connect with edges only those vertices, which can be
together in an intersecting antichain, i.e. those, that have a non-empty
intersection (non-zero bitwise AND) and aren't subsets of each other (their
bitwise AND isn't equal to either of them). Then I find all maximal cliques
in this graph. They correspond to all maximal intersecting antichains on n
vertices (if every two sets in a system can together be in an intersecting
antichain, then the system itself is an intersecting antichain). And
finally I find all sets that span every number in [0,n-1] (bitwise OR of
the system equals 2^n-1). In Mathematica:

n = 2^6; (* Computes a(6) *)
g = CompleteGraph[n];
i = 0;
While[i < n, i++; j = i;
  While[j < n, j++;
   If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j,
    g = EdgeDelete[g, i <-> j]]]];
sets = Select[FindClique[g, Infinity, All], BitOr @@ # == n - 1 &]
Length[sets]

It produces the sequence 1, 1, 1, 2, 12, 133, 11386, 12143511.
It finishes instantly for n less than 7, and works out a(7) in 2 minutes.
But there's a problem: FindClique function dumps all found cliques in RAM
and while trying to compute a(8) I run out of memory. Could someone,
please, suggest some way of either reducing memory usage, or making
FindClique dump the results in a file? I'm totally willing to spend several
hours of CPU time on this ;)
Thanks in advance!
Elijah



More information about the SeqFan mailing list