Braun–Bruegge facet bounds conjecture for symmetric edge polytopes

About 3 years old · traced to

Let GG be a connected graph with n≥3n\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

3⋅2n−12−2≤N(PG)≤6n−12.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(n−1)/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 (n−1)/2(n-1)/2 triangles. If nn is even, then

2n2+1−2≤N(PG)≤14⋅6n2−2.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/2−2n/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.

References

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.