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.
| Original language | English |
|---|---|
| Article number | 23.7.2 |
| Journal | Journal of Integer Sequences |
| Volume | 26 |
| Issue number | 7 |
| State | Published - 2023 |
Bibliographical note
Publisher Copyright:© 2023, University of Waterloo. All rights reserved.
Funding
Both authors were partially supported by National Science Foundation award DMS-1953785. The authors thank Rob Davis and Tianran Chen for helpful discussions. The authors thank the anonymous referees for many helpful suggestions and references. The authors made extensive use of both OEIS [14] and SageMath [19] in this work.
| Funders | Funder number |
|---|---|
| National Science Foundation (NSF) | DMS-1953785 |
Keywords
- binomial coefficient
- facet
- symmetric edge polytope
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
Fingerprint
Dive into the research topics of 'Facets of Symmetric Edge Polytopes for Graphs with Few Edges'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver