The CR Graph
It is natural to define a graph based on clique replacement. Its vertices correspond to all the polytopes of a fixed dimension and fixed number of facets. An edge of the graph indicates a clique replacement connecting two polytopes.
There are a variety of potentially interesting questions related to this graph, for example:
- What is the CR Distance from the cube to the dual of the cyclic polytope?
- What is the diameter of the CR graph for various values of dimension and number of facets?
- What is the edge density for various CR graphs?
While it is infeasible to draw this graph for any but the smallest dimensions, below are drawn some various representations of the CR Graph for 4 dimensions, eight facets.
Each edge corresponds to a clique replacement. Edge colors are merely intended to clarify the connections.
All items in the a given row have the same number of vertices.
The numbering scheme is the one introduced by Grünbaum and Sreedharan (for the duals of these polytopes). Brückner’s Sphere and Barnette’s sphere are also included as indicated. The gray ovals indicate polytopes with edge diameter three.
Polytopes (and spheres) are color coded to indicate the order of their (combinatorial) symmetry group. Edges are given the color of the smaller of the two groups of incident polytopes (with the exception that black is used instead of yellow).
Polytopes are color coded to indicate the number of estranged vertex pairs – i.e. pairs of vertices with no facet in common. Edges are given the color of the smaller of the two counts.
Each pair of estranged vertices has several different edge paths of length four connecting them. In this “information overload” graph, the colors of the Ovals and the Numbers give the min and max # of such paths (respectively) over the different possibilities for estranged pair. (Edge colors are taken from the previous graph and indicate the smaller of the two counts of estranged vertex pairs.)