5
$\begingroup$

How does one enumerate the distinct orbit classes of independent sets of the hypercube modulo symmetries of the hypercubes?

The counting of the number of independent sets in an $n$-dimensional hypercube modulo symmetries of the hypercube has been done up to $n=5$ by D.Eppstein as seen in the OEIS. We do have a bound on the number of independent sets of a regular graph as found by Y.Zhao. But I'm not aware of other results to this old problem of mine.

Does anyone know of a resource on how to go about this enumeration? I've already coded a brute-force program to do this listing and had reproduced Eppstein's results up to $n=5$. The $n=6$ took too much time and memory space on my personal computer that it always crashed. But this was years ago. I was just reminded of this recently, so here's my first post on MO.

$\endgroup$
1
  • 1
    $\begingroup$ Here is an idea. Break the task up into 288 pieces, one for each orientation of an independent set in the five-cube. Assume that you have chosen an orientation where at least half the points are in the "lower" part of the 6-cube and you know where those are. (They may not be in the standard orientation, but that is what the computer is for.) Now cycle through all independent sets in the upper part that avoid the lower part and are no larger. You might have some theory that restricts the orientations needed in the lower part. Gerhard "Welcome To The MathOverflow Forum" Paseman, 2012.08.14 $\endgroup$ Aug 14, 2012 at 7:25

2 Answers 2

6
$\begingroup$

This is an easy problem for an orderly algorithm, which can generate the independent sets without isomorphs with no direct isomorphism checks between different independent sets.

It takes a couple of minutes on a recent computer and concludes that there are there are 519195 independent sets in the 6-cube up to isomorphism.

The numbers of each size (from 0 to 32) are:

1, 1, 5, 11, 56, 182, 742, 2323, 6714, 15233, 29200, 44870, 58711, 64916, 64902, 58982, 51064, 40835, 30884, 21145, 13511, 7631, 4058, 1859, 839, 316, 133, 42, 19, 5, 3, 1, 1

$\endgroup$
12
  • $\begingroup$ And the 7-cube? $\endgroup$ Aug 15, 2012 at 14:38
  • 1
    $\begingroup$ I knew you'd say that. $\endgroup$ Aug 15, 2012 at 14:40
  • $\begingroup$ Do you have a simple function which chooses a representative of the orbit of the symmetry group on subsets of the vertices? $\endgroup$ Aug 16, 2012 at 0:30
  • $\begingroup$ Same question, do you generate the orbit representatives? Or just do a counting of the orbits? I guess then that my algorithm was not that efficient and my computer not that powerful. I'll try to generate this the next couple of hours. $\endgroup$ Aug 16, 2012 at 0:57
  • $\begingroup$ Even if asked to enumerate the independent sets of size 3 up to symmetry, I am having a hard time seeing how to do it without isomorphism checks. Would you be so kind as to hint at what orderly algorithm can do this? Gerhard "Will Settle For A Reference" Paseman, 2012.08.15 $\endgroup$ Aug 16, 2012 at 1:26
3
$\begingroup$

Enumeration via Burnside's Lemma should be feasible if you program efficiently.

$$ |X/G| = \frac 1{|G|} \sum_{g\in G} |X^g|$$

where $X^g$ is the set of fixed points of $g$.

The biggest piece comes from the identity. To enumerate all independent sets, you can use your understanding of the $288$ classes of independent subsets of the $5$-cube. Every independent subset of the $6$-cube induces an independent subset on the top facet and on the bottom facet. So, for each ordered pair $(S_0,S_1)$ of independent subsets of the $5$-cube, determine for each element of the orbit of $S_1$ by the symmetries of the $5$-cube whether this is disjoint from $S_0$. Then multiply by the size of the orbit of $S_0$. This takes about $288^2 2^5 5! 2^5 \approx 2^{33}$ steps, which is not too much.

Each other element of the symmetry group of the $6$-cube acts nontrivially on the cube. The quotient is a smaller graph than the $6$-cube, and most of these quotients fall to a brute force enumeration. Note that if $g$ reverses an edge then you may delete the vertex from the quotient because the edge turns into a loop, and that vertex can't be included in an independent set fixed by $g$.

The largest quotients by nontrivial elements come from the element which transposes the first two coordinates and its conjugates. The quotient has size $48$, and has the structure of a $4$-cube times a chain with $3$ vertices. You can make a $21\times21$ transfer matrix $M$ indexed by the classes of independent sets whose value counts images of the row under the symmetries of the $4$-cube which are disjoint from the column. The number of independent subsets of the quotient equals the $(\emptyset,\emptyset)$ entry of $M^4$.

Similarly, the third largest quotients, by a $3$-cycle, have a quotient of size $32$, which is a little bit too large to brute-force comfortably as a step in a larger computation. However, the quotient is again a product with a chain, and again a transfer matrix simplifies the calculation.

The second largest quotients, by two disjoint transpositions, have the structure of the product of a square with two chains on $3$ vertices. A brute-force check could be done since there are only $36$ vertices, but you can construct a transfer matrix $M$ indexed by independent subsets of a square times a $3$-chain so that the sum of the entries of $M^2$ counts the independent sets. There are fewer than $2^11$ independent subsets of a square times a $3$-chain, so this computation is feasible.

The other quotients are small enough that you can handle them by brute force enumerations, although back-tracking might be faster.

I would test this method on the $5$-cube first, but another check is whether the sum is divisible by $|G| = 2^6 6!$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.