1
[2309.05764] Equality cases of the Alexandrov--Fenchel inequality are not in the...
source link: https://arxiv.org/abs/2309.05764
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 11 Sep 2023 (v1), last revised 1 Nov 2023 (this version, v2)]
Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
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.
| Comments: | 34 pages. Conjecture 10.2 and 10.3 in v1 are now resolved, and become Theorem 1.3 and Corollary 4.8, respectively. Proofs in Section 7 and 8 are streamlined and improved. Several final remarks in Section 10 are revised, and new references are included |
| Subjects: | Combinatorics (math.CO); Computational Complexity (cs.CC); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Metric Geometry (math.MG) |
| MSC classes: | 05A20, 06A07, 52A40 (Primary) 11A55, 52A39, 68Q15, 68Q17, 68R05 (Secondary) |
| Cite as: | arXiv:2309.05764 [math.CO] |
| (or arXiv:2309.05764v2 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2309.05764 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK