How many sets of non-adjacent edges in the 600-cell?

224 Views Asked by At

(This is a simpler variant of my previous question, with one colour instead of two.)

The 600-cell is a 4D regular polytope. It has $120$ vertices, $720$ edges, $1200$ triangular faces, and $600$ tetrahedral cells. Each vertex touches $12$ edges, in an icosahedral arrangement.

Two edges are adjacent if they're part of one triangular face. The number of adjacent pairs of edges is $1200\times\binom{3}{2}=3600$.

Question 1: How many subsets (of that set of $720$ edges) have no adjacent pairs of edges?

Question 2: How many of these are distinct, considering symmetries of the 600-cell?

An obvious upper bound for these numbers is the total number of subsets, $2^{720}\approx5.515\times10^{216}$.


The rectified 600-cell is a 4D uniform polytope, whose vertices correspond to the edges of the 600-cell, with the same adjacency relations. It has $720$ vertices and $3600$ edges. Each vertex touches $10$ edges.

So I may equivalently ask about sets of non-adjacent vertices in the rectified 600-cell:

Question 1: How many vertex-induced subgraphs (of the rectified 600-cell's graph) have no edges?

Question 2: How many of these are distinct, considering symmetries of the rectified 600-cell?


An approximate answer would still be appreciated.

Let $A_1$ and $A_2$ be the answers to the two questions (respectively). The order of the 600-cell's symmetry group is $600\times24=14400$, where the $24$ is from tetrahedral symmetry. Thus, for each subset, there are between $1$ and $14400$ subsets in its orbit under the symmetry group. As $A_1$ counts the subsets and $A_2$ counts the orbits, we get

$$A_2\leq A_1\leq14400A_2.$$

In fact, it seems very likely that a random subset would have no symmetry; all $14400$ subsets in its orbit would be unequal to each other. So I'm expecting

$$A_1\approx14400A_2.$$

And I think $A_2$ would be more difficult to compute than $A_1$. Indeed, ignoring the adjacency condition, we'd have $2^{720}$ for $A_1$, but nothing so easy for $A_2$.

1

There are 1 best solutions below

6
On

This following images will help better understand the structure of the $600-$Cell when considered as a graph. enter image description here

enter image description here