Graphs of Polytopes

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.