Journal of Integer Sequences, Vol. 26 (2023), Article 23.7.2

Facets of Symmetric Edge Polytopes for Graphs with Few Edges


Benjamin Braun and Kaitlin Bruegge
Department of Mathematics
University of Kentucky
Lexington, KY 40506-0027
USA

Abstract:

Symmetric edge polytopes, also called adjacency polytopes, are lattice polytopes determined by simple undirected graphs. We introduce the integer array giving the maximum number of facets of a symmetric edge polytope for a connected graph having a fixed number of vertices and edges and the corresponding array of minimal values. We establish formulas for the number of facets obtained in several classes of sparse graphs, and provide partial progress toward conjectures that identify facet-maximizing graphs in these classes. These formulas are combinatorial in nature, and lead to independently interesting observations and conjectures regarding integer sequences defined by sums of products of binomial coefficients.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A027383 A360408 A360409.)


Received February 28 2023; revised versions received July 7 2023; July 11 2023. Published in Journal of Integer Sequences, July 24 2023.


Return to Journal of Integer Sequences home page