User:MWinter4/Eigenpolyope

In graph theory and polytope theory, an eigenpolytope of a graph is a convex polytope constructed from some of the graph's spectral properties, such as eigenvalues and eigenvectors. More precisely, an eigenpolytope is the convex hull of a spectral embedding of the graph.

What polytopes occur as eigenpolytopes depends on the matrix used to construct the spectral embeddings (e.g. adjacency matrix or Laplace matrix). In any case, only few polytopes seem to occur as eigenpolytopes. Still, no classification or alterantive characterization is known.

Eigenpolytopes were first introduced by Chris Godsil.

A polytope that is an eigenpolytope of its edge graph is called spectral or self-reproducing.

Construction

For most graphs there is not the eigenpolytope since the construction depends crucially on the matrix used to represent the graph (e.g. adjaceny matrix vs. Laplace matrix). For some graphs however, all reasonable matrices (i.e. that respect the graph's symmetries) result in the same eigenpolytopes. This includes all graphs that are both vertex- and edge-transitive. More generally, this includes all graphs that are 1-walk regular.

Examples

Powers computed the eigenpolytopes of the Petersen graph, which he called the Petersen polytopes. ??? constructed the Hamming polytopes, eigenpolytopes of Hamming graphs.

Properties and relations

• The dimension of an eigenpolytope is given by the multiplicity of the used eigenvalue.

Applications

• Eigenpolytopes are used for combinatorial designs.
• Eigenpolytopes are estimating the clique number of a graph.

Spectral polytopes

A polytope is spectral (or self-reproducing) if it is the eigenpolytope of its edge graph. A more precise definition requires that the skeleton is a spectral embedding of the edge graph. This avoids special cases where the convex hull of an alternative embedding of the edge graph gives the same polytope (e.g. the pentagram or the great stellated dodecahedron).

It is believed that a polytope can be spectral only to the second largest eigenvalue, though this is not proven. Moreover, all known spectral polytopes are very symmetric. The only known example of a spectral polytope that is not vertex-transitive is the rhombic dodecahedron. For those, being spectral depends on the chosen matrix. The rhombic dodecahedron is spectral w.r.t. the adjacency matrix, but not w.r.t. the Laplace matrix.

Some properties of spectral polytopes:

• Spectral polytopes are perfect polytopes in the sense of Gevay That means they have a unique relization of maximal symmetry.
• Spectral polytopes are as symmetric as their edge-graph. That means, for every automorphism of the edge graph there exists an isometry of the polytope that permutes the vertices in the same way.
• A spectral polytope is uniquely determined by its edge graph (among spectral polytopes).
• A spectral polytope has a unique spectral realization.

Examples

Platonic solids

All Platonic solids are spectral. More generally, every regular polytope in every dimension is spectral. Even more general, every polytope that is both vertex- and edge-transitive is spectral. As a cosnequence, some metric properties of these polytopes can be derived from the spectral properties of the edge graph. This includes the circumradius, edge lengths and dihedral angles.

Distance-transitive polytopes

Chris Godsil classified the distance-regular graphs that appear as edge graphs of spectral polytopes:

edge graph	eigenpolytope	dim	diagram
cycle graph $C_{n},n\geq 3$	regular $n$-gon	2
dodecahedral graph	regular dodecahedron	3
icosahedral graph	regular icosahedron	3
Schläfli graph	$2_{21}$-polytope (Schläfli polytope)	6
Gosset graph	$3_{21}$-polytope	7
Complete $n$-partite graph $K_{2,...,2}$	$n$-dimensional cross-polytope	$n$	...
Johnson graph $J(n,k)$	hypersimplex $\Delta _{n,k}$	$n-1$	depends on parameter
Hamming graph $H(d,q)$	$d$-th cartesian power of a $(q-1)$-dimensional simplex; this includes hypercubes ($q=2$) and simplices ($d=1$)	$d(q-1)$	depends on parameter
halved cube graph ${\tfrac {1}{2}}Q_{n}$	$n$-dimensional demihypercube	$n$	...

Remarkably, all graphs in this class are distance-transitive. This is also the complete classification of distance transitive polytopes. All of them are Wythoffian polytopes. They include all regular polytopes except for the 24-, 120- and 600-cell.

External links

• www.example.com