Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
arXiv:2309.05764 · doi:10.1017/fmp.2024.20
Abstract
Describing the equality conditions of the Alexandrov--Fenchel inequality has been a major open problem for decades. We prove that in the case of convex polytopes, this description is not in the polynomial hierarchy unless the polynomial hierarchy collapses to a finite level. This is the first hardness result for the problem, and is a complexity counterpart of the recent result by Shenfeld and van Handel (arXiv:archive/201104059), which gave a geometric characterization of the equality conditions. The proof involves Stanley's order polytopes and employs poset theoretic technology.
35 pages. Fixed some typos and updated some references. to appear in Forum Math. Pi
References in corpus (7)
- Introduction to the combinatorial atlas
- Extensions of the Kahn--Saks inequality for posets of width two
- Effective poset inequalities
- Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
- The hull metric on Coxeter groups
- Linear extensions and continued fractions
- On the cross-product conjecture for the number of linear extensions