Loading...
Thumbnail Image
Publication

Graphs of Polytopes

Espenschied, William Joshua
Citations
Altmetric:
Abstract
The graph of a polytope is the graph whose vertex set is the set of vertices of the polytope, and whose edge set is the set of edges of the polytope. Several problems concerning graphs of polytopes are discussed. The primary result is a set of bounds (Theorem 39) on the maximal size of an anticlique (sometimes called a coclique, stable set, or independent set) of the graph of a polytope based on its dimension and number of vertices. Two results concerning properties preserved by certain operations on polytopes are presented. The first is that the Gale diagram of a join of polytopes is the direct sum of the Gale diagrams of the polytopes and dually, that the Gale diagram of a direct sum of polytopes is the join of their Gale diagrams (Theorem 23). The second is that if two polytopes satisfy a weakened form of Gale's evenness condition, then so does their product (Theorem 32). It is shown, by other means, that, with only two exceptions, the complete bipartite graphs are never graphs of polytopes (Theorem 47). The techniques developed throughout are then used to show that the complete 3-partite graph K_{1,n,m} is the graph of a polytope if and only if K_{n,m} is the graph of a polytope (Theorem 49). It is then shown that K_{2,2,3} and K_{2,2,4} are never graphs of polytopes. A conjecture is then stated as to precisely when a complete multipartite graph is the graph of a polytope. Finally, a section is devoted to results concerning the dimensions for which the graph of a crosspolytope is the graph of a polytope.
Description
Date
2014-12-31
Journal Title
Journal ISSN
Volume Title
Publisher
University of Kansas
Research Projects
Organizational Units
Journal Issue
Keywords
Mathematics, Anticlique, Gale diagram, Graph, Polytope
Citation
DOI
Embedded videos