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