[seqfan] Re: Antichains and RAM

[Tim Peters]

That's a nice approach!  Makes sense.  Just FYI, I wrote a Python
program for this, and it confirmed the values you reported:

1, 1, 1, 2, 12, 133, 11386, 12143511.

Memory use is trivial - because I wrote my own FindClique work-a-like
so didn't have to store anything anywhere ;-)

a(8) has been running over 5 hours now, and has gotten to over 2.5
billion.  The top level recursion computed a list of 37 nodes to
traverse, and is only on the 5th of them now.  So there's no quick end
in sight.  Indeed, it's found over 2 billion answers since the last
time the top level loop advanced.  It finds another million about
every 9 seconds.

I won't be able to let this run overnight.  If anyone is inspired to
do something similar, I'm using the Bron-Kerbosch algorithm to
enumerate maximal cliques.  The "pivot" variation is very valuable in
this context.  Also using degeneracy ordering at the top level seems
to _hurt_, though - this is very far from a sparse graph with limited
connectivity.

Elijah Beregovsky <elijah.beregovsky at gmail.com> wrote:
>
> 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