# [seqfan] Re: Antichains and RAM

rgwv at rgwv.com rgwv at rgwv.com
Tue May 5 19:32:22 CEST 2020

```11386

I'm working on a(7).

-----Original Message-----
From: SeqFan <seqfan-bounces at list.seqfan.eu> On Behalf Of Elijah Beregovsky
Sent: Tuesday, May 5, 2020 11:03 AM
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Subject: [seqfan] Antichains and RAM

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

--
Seqfan Mailing list - http://list.seqfan.eu/

```