Maximum independent sets of the 120-cell and other regular polyhedra
A d-code in a graph is a set of vertices such that all pairwise distances are at least d. As part of a study of d-codes of three-and four-dimensional regular polytopes, the maximum independent set order of the 120-cell is calculated. A linear program based on counting arguments leads to an upper bound of 221. An independent set of order 110 in the antipodal collapse of the 120-cell (also known as the hemi-120-cell) gives a lower bound of 220 for the 120-cell itself. The gap is closed by the computation described here, with the result that the maximum independent set order of the 120-cell is 220. All maximum d-code orders of the icosahedron, dodecahedron, 24-cell, 600-cell and 120-cell are reported.
Independent sets, graphs, polyhedra, polytopes