Maximum independent sets of the 120-cell and other regular polytopes

Sean Debroni, Erin Delisle, Wendy Myrvold, Amit Sethi, Joseph Whitney, Jennifer Woodcock, Patrick W. Fowler, Benoit de La Vaissiere, Michel Marie Deza

Abstract


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.

Keywords


Independent sets, graphs, polyhedra, polytopes

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.170.fd8

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications