Graphs of Polytopes
Issue Date
2014-12-31Author
Espenschied, William Joshua
Publisher
University of Kansas
Format
109 pages
Type
Dissertation
Degree Level
Ph.D.
Discipline
Mathematics
Rights
Copyright held by the author.
Metadata
Show full item recordAbstract
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.
Collections
- Dissertations [4626]
- Mathematics Dissertations and Theses [179]
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.