Lattice Polytopes from Graphs and Networks

University Of Kentucky Research Foundation, Lexington KY

Investigators

Abstract

Lattice polytopes are convex polytopes where every vertex is an integer vector. They include simple examples like two-dimensional polygons with corners on a rectangular grid and extend to high-dimensional examples beyond our ability to visualize. Lattice polytopes are ubiquitous throughout mathematics and the sciences, including combinatorics, optimization, commutative algebra, algebraic geometry, transportation problems, and many other fields. A graph, also called a network, is a collection of objects that are connected pairwise. Two common examples are cities connected by interstates, or people connected when they are friends. Graphs and networks are a source of important lattice polytopes that allow us to study the structure of the pairwise connections among objects. In this proposal, the principal investigator will study three types of lattice polytopes and their structure. First, flow polytopes will be analyzed, which model the flow of material through transportation networks. Second, graphical Hermite normal form simplices will be studied, which are a new class of lattice polytopes whose structure is determined by a graph. Third, faces of symmetric edge polytopes will be investigated, which are lattice polytopes with connections to solving equations related to the behavior of coupled systems of oscillators. For these three classes of lattice polytopes, this project will study geometric and algebraic properties such as volume, faces, and integer point counting. These properties of lattice polytopes play a fundamental role in both pure and applied mathematics. In addition to contributing directly to the expansion of our understanding of lattice polytopes, the principal investigator will continue his ongoing work in advising doctoral students. Further, by contributing mathematical expertise to research teams in mathematics education and history of mathematics, the project will have an impact on the culture and teaching of mathematics. Finally, the PI will continue to lead workshops and seminars dedicated to teaching and learning in the mathematical sciences. More technically, the goal of this project for flow polytopes is to understand how combinatorial properties of directed acyclic graphs influence volume and refined volume information obtained via Ehrhart theory. By studying the relation between invariants such as degree sequences of networks and volumes of their flow polytopes, the principal investigator expects to increase our collective understanding of how the edge structure of networks influences flow polytope volumes. The goal of this proposal for graphical Hermite normal form simplices is to classify the simplices having the Gorenstein and integer decomposition properties, and to obtain bounds on the values of vectors arising in Ehrhart theory for these objects. Further, by focusing on the recently-initiated study of Ehrhart h-star distributions of these polytopes, the principal investigator will contribute to our understanding of limits of these distributions. For symmetric edge polytopes, the goal of this project is to study the relationship between clustering metrics on graphs and facet numbers of the polytopes, in pursuit of a proof for a conjecture regarding facet maximizing and facet minimizing graphs. The methods used in these projects will involve a mix of computational experimentation and mathematical proof. In prior work of the Principal Investigator in these topics, computational experiments have proven crucial to the process of making conjectures and proving theorems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.