A spectral approach to polyhedral dimension (Q750306)

The author defines a new dimension function for polytopes using the convex hull of the edge or arc incidence vectors of Hamiltonian tours and other objects in graphs. A matrix with rows equal to the extreme points of the polytope and supplemented with a column of units is constructed. The matrix is reduced to diagonal form by orthogonal transformations. The number of nonzero diagonal elements defines the dimension of the polytope. Values of such diagonal elements are obtained for some graphs and hypergraphs.