Facets of Symmetric Edge Polytopes for Graphs with Few Edges

Symmetric edge polytopes, also called adjacency polytopes, are lattice polytopes determined by simple undirected graphs. We introduce the integer array $\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{f}(n,m)$ giving the maximum number of facets of a symmetric edge polytope for a connected graph having $n$ vertices and $m$ edges, and the corresponding sequence $\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{f}(n,m)$ 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.