Braun–Bruegge facet bounds conjecture for symmetric edge polytopes

Let GG be a connected graph with n3n\geq 3 vertices. Let PG{\mathcal P}_G be its symmetric edge polytope, and let N(PG)N({\mathcal P}_G) denote the number of its facets. A 11-sum of graphs is formed by taking their union along a common vertex. Braun–Bruegge's conjecture. If nn is odd, then

32n122N(PG)6n12.3\cdot 2^{\frac{n-1}{2}}-2\leq N({\mathcal P}_G)\leq 6^{\frac{n-1}{2}}.

Moreover, equality on the left holds if and only if G=K(n1)/2,(n+1)/2G=K_{(n-1)/2,(n+1)/2}, while equality on the right holds if and only if GG is the 11-sum of (n1)/2(n-1)/2 triangles. If nn is even, then

2n2+12N(PG)146n22.2^{\frac{n}{2}+1}-2\leq N({\mathcal P}_G)\leq 14\cdot 6^{\frac{n}{2}-2}.

Moreover, equality on the left holds if and only if G=Kn/2,n/2G=K_{n/2,n/2}, while equality on the right holds if and only if GG is the 11-sum of K4K_4 with n/22n/2-2 triangles.

The conjecture concerns sharp lower and upper bounds for facets of symmetric edge polytopes. The paper states that it proves the conjecture for every graph that is the join of two graphs, equivalently every connected graph whose complement is disconnected; the supplied context does not establish the conjecture in full generality.

Sources & referencesView supporting material

Primary source

Aki Mori, Kenta Mori and Hidefumi Ohsugi, “Number of facets of symmetric edge polytopes arising from join graphs”, arXiv:2312.11287 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.