[seqfan] Re: Antichains and RAM

[Tim Peters]

[Tim (me), commenting on Elijah Beregovsky's work to extend
 A326361 <https://oeis.org/A326361>]
> ... Just FYI, I wrote a Python
> program for this, and it confirmed the values you reported:
>
> 1, 1, 1, 2, 12, 133, 11386, 12143511.
>
> ...
>
> 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.

A faster version of that program has been running about 4 1/2 days.
It's found over 96 billion maximal cliques so far, but is _still_ only
on the 5th node in the top-level list.

It would eventually end, but I have to use the box for other things
now that the weekend is ending, and it looks like this could continue
to run for weeks.  Here's the most recent it found, which hints at why
enumerating all of 'em is so long-winded:

{7, 27, 212, 51, 236, 83, 131, 75, 99, 188, 106, 186, 117, 77, 197,
181, 90, 202, 78, 45, 226, 141, 198, 142, 30, 209, 118, 153, 169, 201,
89, 105, 182}

Unlike as when doing small examples by hand, the cardinalilty of
maximal cliques in a(8) can be "largish".

Maybe it's time to think? ;-)

One thing that occurs to me:  this graph has many symmetries.  For
example, take any maximal clique, like

{3, 5, 9, 14}

arising in a(4).  Then pick any permutation of the bit positions, and
apply it to each integer in the clique.  For example, take the
permutation that rotates a 4-bit integer left by 2 bits.  Then

 3 = 0011 -> 1100 = 12
 5 = 0101 -> 0101 =  5
 9 = 1001 -> 0110 =  6
14 = 1110 -> 1011 = 11

and, indeed, {5, 6, 11,12} is another maximal clique in a(4).

Or take the permutation that reverses the bit order, and  {3. 5, 9,
14} transforms to {12, 10,  9, 7}, another maximal clique.

And so on.  A little thought convinces me that "can be transformed
into by some bit position permutation" defines an equivalence relation
on maximal cliques for these specific graphs.

So the computation could conceivably be slashed enormously if there
were a way to construct only a canonical representative for each
equivalence class.  But I haven't found a practical way to exploit
that.

I can count equivalence classes after the fact, though, via brute
force, yielding this.  Four columns:  n, a(n), number of equivalence
classes, and the average number of maximal cliques per class:

2, 1, 1, 1.00
3, 2, 2, 1.00
4, 12, 4, 3.00
5, 133, 12, 11.08
6, 11386, 92, 123.76
7, 12143511, 5016, 2420.96

At least vaguely interesting ;-)