Voir la notice de l'article provenant de la source Cambridge University Press
@article{10_1017_fmp_2024_20,
author = {Swee Hong Chan and Igor Pak},
title = {Equality cases of the {Alexandrov{\textendash}Fenchel} inequality are not in the polynomial hierarchy},
journal = {Forum of Mathematics, Pi},
publisher = {mathdoc},
volume = {12},
year = {2024},
doi = {10.1017/fmp.2024.20},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1017/fmp.2024.20/}
}
TY - JOUR AU - Swee Hong Chan AU - Igor Pak TI - Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy JO - Forum of Mathematics, Pi PY - 2024 VL - 12 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.1017/fmp.2024.20/ DO - 10.1017/fmp.2024.20 LA - en ID - 10_1017_fmp_2024_20 ER -
%0 Journal Article %A Swee Hong Chan %A Igor Pak %T Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy %J Forum of Mathematics, Pi %D 2024 %V 12 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.1017/fmp.2024.20/ %R 10.1017/fmp.2024.20 %G en %F 10_1017_fmp_2024_20
Swee Hong Chan; Igor Pak. Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy. Forum of Mathematics, Pi, Tome 12 (2024). doi: 10.1017/fmp.2024.20
[Aar16] , ‘’, in Open Problems in Mathematics (Springer, Cham, 2016), 1–122. Available at scottaaronson.com/papers/pnp.pdf.Google Scholar | DOI
[AHK18] , and , ‘Hodge theory for combinatorial geometries’, Ann. Math. 188 (2018), 381–452.Google Scholar | DOI
[AAHS99] , , and , ‘Approximation and exact algorithms for minimum-width annuli and shells’, in Proceedings of the 15th Annual Symposium on Computational Geometry (ACM, New York, 1999), 380–389.Google Scholar | DOI
[Ale37] , ‘To the theory of mixed volumes of convex bodies II. New inequalities between mixed volumes and their applications (in Russian)’, in Selected Works, Mat. Sb. (1937), 1205–1238, Classics of Soviet Mathematics (CRC Press, FL, 1996), 61–97. English translation in A. D. Alexandrov, Selected works, Part I, Ch. IV. Google Scholar
[Ale50] , Convex Polyhedra (translated from the Russian 1950 ed.) (Springer, Berlin, 2005), 1–542.Google Scholar
[AS16] and , The Probabilistic Method, fourth edn (John Wiley, Hoboken, NJ, 2016), i+301.Google Scholar
[ALOV24] , , and , ‘Log-concave polynomials III: Mason’s ultra-log-concavity conjecture for independent sets of matroids’, Proc. Am. Math. Soc. 152 (2024), 1969–1981.Google Scholar
[AB09] and , . A Modern Approach (Cambridge University Press, Cambridge, 2009), 1–594.Google Scholar
[AASS20] , and , ‘Geometric inequalities for anti-blocking bodies’, Commun. Contemp. Math. 25(3) (2023), Paper No. 2150113.Google Scholar | DOI
[Bar07] , ‘Brunn–Minkowski inequalities for contingency tables and integer flows’, Adv. Math. 211 (2007), 105–122.Google Scholar | DOI
[BW89] and , ‘-hook length formulas for forests’, J. Comb. Theory, Ser. A 52 (1989), 165–187.Google Scholar | DOI
[Blå05] , ‘The isoperimetric problem’, Am. Math. Mon. 112 (2005), 526–566.Google Scholar | DOI
[BCSS98] , , and , Complexity and Real Computation (Springer, New York, 1998), i+299.Google Scholar | DOI
[BO43] , ‘Beweis einer Vermutung von H. Minkowski’, Abh. Math. Sem. Hansischen Univ. 15, 1943, 37–56.Google Scholar | DOI
[BBS99] , and , ‘Geometrical techniques for estimating numbers of linear extensions’, Eur. J. Comb. 20 (1999), 329–335.Google Scholar | DOI
[Bon29] , Les problèmes des isopérimètres et des isépiphanes (in French) (Gauthier-Villars, Paris, 1929), 1–175.Google Scholar
[BF34] and , Theory of Convex Bodies (translated from the German 1934 ed.) (BCS, Moscow, ID, 1987), 1–172.Google Scholar
[BH20] and , ‘Lorentzian polynomials’, Ann. Math. 192 (2020), 821–891.Google Scholar | DOI
[BL23] and , ‘Lorentzian polynomials on cones’, Preprint, 2023, .Google Scholar | arXiv
[Bre89] , ‘Unimodal, log-concave and Pólya frequency sequences in combinatorics’, in Memoirs of the American Mathematical Society 413 (American Mathematical Society, Providence, RI, 1989), 1–106.Google Scholar
[BT02] and , ‘A combinatorial approach to correlation inequalities’, Discrete Math. 257 (2002), 311–327.Google Scholar | DOI
[BW00] and , ‘Partially ordered sets’, in Ch. 11 Handbook of Discrete and Combinatorial Mathematics (CRC Press, Boca Raton, FL, 2000), 717–752.Google Scholar
[BW91] and , ‘Counting linear extensions’, Order 8 (1991), 225–247.Google Scholar | DOI
[BZ88] and , Geometric Inequalities (Springer, Berlin, 1988), 1–331.Google Scholar | DOI
[CP22] and , ‘Introduction to the combinatorial atlas’, Expo. Math. 40 (2022), 1014–1048.Google Scholar | DOI
[CP23a] and , ‘Computational complexity of counting coincidences’, Preprint, 2023, arXiv:2308.10214. To appear in Theor. Comp. Sci. Google Scholar
[CP23b] and , ‘Linear extensions of finite posets’, Preprint, 2023, .Google Scholar | arXiv
[CP24a] and , ‘Log-concave poset inequalities’, JAMR 2 (2024), 53–153.Google Scholar | DOI
[CP24b] and , ‘Linear extensions and continued fractions’, Eur. J. Comb. 122 (2024), 104018.Google Scholar | DOI
[CP24+] and , ‘Quadratic permanent equality is not in ’, In preparation.Google Scholar
[CPP23a] , and , ‘Extensions of the Kahn–Saks inequality for posets of width two’, Comb. Theory 3(1) (2023), Paper No. 8.Google Scholar
[CPP23b] , and , ‘Effective poset inequalities’, SIAM J. Discret. Math. 37 (2023), 1842–1880.Google Scholar | DOI
[CPP24] , and , ‘On the cross-product conjecture for the number of linear extensions’, Can. J. Math. (2024). doi:10.4153/S0008414X24000087 Google Scholar | DOI
[CFG80] , and , ‘On unimodality for linear extensions of partial orders’, SIAM J. Algebr. Discret. Meth. 1 (1980), 405–410.Google Scholar | DOI
[CKMS19] , , and , ‘One more proof of the Alexandrov–Fenchel inequality’, C.R. Math. Acad. Sci. Paris 357(8) (2019), 676–680.Google Scholar | DOI
[DD85] and , ‘Order preserving maps and linear extensions of a finite poset’, SIAM J. Algebr. Discret. Meth. 6 (1985), 738–748.Google Scholar | DOI
[DDP84] , and , ‘On log concavity for order-preserving maps of partial orders’, Discret. Math. 50 (1984), 221–226.Google Scholar | DOI
[Day84] , ‘Monotonic functions of finite posets’, University of Warwick, Ph.D. thesis, 1984. Available at wrap.warwick.ac.uk/131009 Google Scholar
[DP20] and , ‘Counting linear extensions of restricted posets’, Electron. J. Comb. 27 (2020), Paper No. 4.48.Google Scholar
[DF88] and , ‘On the complexity of computing the volume of a polyhedron’, SIAM J. Comput. 17 (1988), 967–974.Google Scholar | DOI
[DGH98] , and , ‘On the complexity of computing mixed volumes’, SIAM J. Comput. 27 (1998), 356–400.Google Scholar | DOI
[EHS89] , and , ‘A recurrence for linear extensions’, Order 6 (1989), 15–18.Google Scholar | DOI
[Ego81] , ‘The solution of van der Waerden’s problem for permanents’, Adv. Math. 42 (1981), 299–305.Google Scholar | DOI
[EK14] and , ‘Dimensionality and the stability of the Brunn–Minkowski inequality’, Ann. Sc. Norm. Super. Pisa, Cl. Sci. 13 (2014), 975–1007.Google Scholar
[Est10] , ‘Newton polyhedra of discriminants of projections’, Discrete Comput. Geom. 44 (2010), 96–148.Google Scholar | DOI
[EG15] and , ‘Systems of equations with a single solution’, J. Symb. Comput. 68 (2015), 116–130.Google Scholar | DOI
[Ewa88] , ‘On the equality case in Alexandrov–Fenchel’s inequality for convex bodies’, Geom. Dedicata 28 (1988), 213–220.Google Scholar | DOI
[Fal81] , ‘Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix’, Math. Notes 29 (1981), 475–479.Google Scholar | DOI
[Fav33] , ‘Sur les corps convexes (in French)’, J. Math. Pures Appl. 12 (1933), 219–282.Google Scholar
[Fej72] , Lagerungen in der Ebene auf der Kugel und im Raum (in German) (Springer, Berlin, 1972), 1–238.Google Scholar | DOI
[Fig13] , ‘Stability in geometric and functional inequalities’, in Proceedings of the European Congress of Mathematics (EMS, Zürich, 2013), 585–599.Google Scholar
[Fig14] , ‘Quantitative stability results for the Brunn–Minkowski inequality’, in Proceedings of the International Congress of Mathematicians Seoul, Vol. III (Kyung Moon Sa, Seoul, 2014), 237–256.Google Scholar
[FJ17] and , ‘Quantitative stability for the Brunn–Minkowski inequality’, Adv. Math. 314 (2017), 1–47.Google Scholar | DOI
[FMP09] , and , ‘A refined Brunn–Minkowski inequality for convex sets’, Ann. Inst. H. Poincaré C, Anal. Non Linéaire 26 (2009), 2511–2519.Google Scholar | DOI
[FMP10] , and , ‘A mass transportation approach to quantitative isoperimetric inequalities’, Invent. Math. 182 (2010), 167–211.Google Scholar | DOI
[Fis84] , ‘A correlational inequality for linear extensions of a poset’, Order 1 (1984), 127–137.Google Scholar | DOI
[FRS85] , and , ‘Perpendicular polygons’, Am. Math. Mon. 92 (1985), 23–37.Google Scholar | DOI
[FKG71] , and , ‘Correlation inequalities on some partially ordered sets’, Commun. Math. Phys. 22 (1971), 89–103.Google Scholar | DOI
[GG22] and , ‘The hull metric on Coxeter groups’, Comb. Theory 2(2) (2022), Paper No. 7.Google Scholar
[Gar02] , ‘The Brunn–Minkowski inequality’, Bull. Am. Math. Soc. 39 (2002), 355–405.Google Scholar | DOI
[GJ78] and , ‘“Strong” -completeness results: Motivation, examples, and implications’, J. ACM 25 (1978), 499–508.Google Scholar
[GJ79] and , Computers and Intractability: A Guide to the Theory of -completeness (Freeman, San Francisco, CA, 1979), 1–338.Google Scholar
[GJT76] , and , ‘The planar Hamiltonian circuit problem is -complete’, SIAM J. Comput. 5 (1976), 704–714.Google Scholar | DOI
[Gol08] , Computational Complexity. A Conceptual Perspective (Cambridge University Press, Cambridge, UK, 2008), 1–606.Google Scholar | DOI
[Gra82] , ‘Linear extensions of partial orders and the FKG inequality’, in Ordered Sets (Reidel, Boston, MA, 1982), 213–236.Google Scholar
[Gra83] , ‘Applications of the FKG inequality and its relatives’, in Mathematical Programming: The State of the Art (Springer, Berlin, 1983), 115–131.Google Scholar
[GK94] and , ‘On the complexity of some basic problems in computational convexity. II. Volume and mixed volumes’, in Polytopes: Abstract, Convex and Computational (Kluwer, Dordrecht, 1994), 373–466.Google Scholar | DOI
[GK97] and , ‘Computational convexity’, in Handbook of Discrete and Computational Geometry (CRC, Boca Raton, FL, 1997), 491–515.Google Scholar
[Gro90] , ‘Stability properties of geometric inequalities’, Am. Math. Mon. 97 (1990), 382–394.Google Scholar | DOI
[Gro93] , ‘Stability of geometric inequalities’, in Handbook of Convex Geometry, Vol. A (North-Holland, Amsterdam, 1993), 125–150.Google Scholar | DOI
[Gro86] , ‘Isoperimetric inequalities in Riemannian manifolds’, in Lecture Notes in Mathematics 1200 (Springer, Berlin, 1986), 114–129. Available at tinyurl.com/2p93zyvz.Google Scholar
[Gur08] , ‘Van der Waerden/Schrijver–Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: One theorem for all’, Electron. J. Comb. 15(1) (2008), RP 66, 26.Google Scholar
[Hal01] , ‘The honeycomb conjecture’, Discrete Comput. Geom. 25 (2001), 1–22.Google Scholar | DOI
[HW08] and , An Introduction to the Theory of Numbers, sixth edn (revised) (Oxford University Press, Oxford, 2008), 1–621.Google Scholar | DOI
[HW20] and , Lectures on Convex Geometry (Springer, Cham, 2020), 1–287.Google Scholar | DOI
[Huh18] , ‘Combinatorial applications of the Hodge–Riemann relations’, in Proceedings of the ICM Rio de Janeiro, vol. IV (World Scientific Publishing Co., Hackensack, NJ, 2018), 3093–3111.Google Scholar
[IP22] and , ‘What is in and what is not?’, Preprint, 2022, arXiv:2204.13149. Extended abstract in Proceedings of the 63rd Symposium on Foundations of Computer Science (2022), 860–871.Google Scholar
[IPP22] , and , ‘Positivity of the symmetric group characters is as hard as the polynomial time hierarchy’, Int. Math. Res. Not. 2024(10) (2024), 8442–8458.Google Scholar | DOI
[IN15] and , ‘On the stability of the polygonal isoperimetric inequality’, Adv. Math. 276 (2015), 62–86.Google Scholar | DOI
[KS84] and , ‘Balancing poset extensions’, Order 1 (1984), 113–126.Google Scholar | DOI
[Kal22] , ‘The work of June Huh’, in Proceedings of the International Congress of Mathematicians (2022, virtual), 16. Available at tinyurl.com/dnnncve5.Google Scholar
[KK12] and , ‘Algebraic equations and convex bodies’, in Perspectives in Analysis, Geometry, and Topology (Birkhäuser, New York, 2012), 263–282.Google Scholar
[Kis68] , ‘A finite partially ordered set and its corresponding set of permutations’, Math. Notes 4 (1968), 798–801.Google Scholar | DOI
[Knu81] , ‘A permanent inequality’, Am. Math. Mon. 88 (1981), 731–740; Erratum 798.Google Scholar | DOI
[Knu98] , ‘Seminumerical algorithms’, in The Art of Computer Programming . Vol. 2, third edn (Addison-Wesley, Reading, MA, 1998), 1–762.Google Scholar
[KS21] and , ‘Linear extension numbers of -element posets’, Order 38 (2021), 49–66.Google Scholar | DOI
[KS99] and , ‘Roundness estimation via random sampling’, in Proceedings of the 10th ACM-DIAM Symposium on Discrete Algorithms (ACM, NY, 1999), 603–612.Google Scholar
[LP07] and , ‘Cell transfer and monomial positivity’, J. Algebraic Comb. 26 (2007), 209–224.Google Scholar | DOI
[LS10] and , ‘On Leonid Gurvits’s proof for permanents’, Am. Math. Mon. 117 (2010), 903–911.Google Scholar | DOI
[Law91] , ‘Polytope volume computation’, Math. Comput. 57 (1991), 259–271.Google Scholar | DOI
[Lei80] , Konvexe Mengen (in German) (DVW, Berlin, 1980), 1–330.Google Scholar | DOI
[Lin86] , ‘Hard enumeration problems in geometry and combinatorics’, SIAM J. Algebr. Discret. Meth. 7 (1986), 331–335.Google Scholar | DOI
[LMS19] , and . Dizier, ‘Gelfand–Tsetlin polytopes: A story of flow and order polytopes’, SIAM J. Discret. Math. 33 (2019), 2394–2415.Google Scholar | DOI
[Loe11] , Bijective Combinatorics (CRC Press, Boca Raton, FL, 2011), 1–590.Google Scholar | DOI
[MS24] and , ‘The extremals of Stanley’s inequalities for partially ordered sets’, Adv. Math. 436 (2024), Paper No. 109404.Google Scholar | DOI
[Mar17] , ‘A stability estimate for the Aleksandrov–Fenchel inequality under regularity assumptions’, Monatsh. Math. 182 (2017), 65–76.Google Scholar | DOI
[Mat02] , Lectures on Discrete Geometry (Springer, NY, 2002), 1–481.Google Scholar | DOI
[MNY21] , and , ‘Strictness of the log-concavity of generating polynomials of matroids’, J. Comb. Theory, Ser. A 181 (2021), Paper 105351.Google Scholar | DOI
[Oss78] , ‘The isoperimetric inequality’, Bull. Amer. Math. Soc. 84 (1978), 1182–1238.Google Scholar | DOI
[Oss79] , ‘Bonnesen–style isoperimetric inequalities’, Am. Math. Mon. 86 (1979), 1–29.Google Scholar | DOI
[Pak05] , ‘Partition bijections, a survey’, Ramanujan J. 12 (2006), 5–75.Google Scholar | DOI
[Pak09] , ‘Lectures on discrete and polyhedral geometry’, monograph draft (2009), 1–440. Available at math.ucla.edu/˜pak/book.htm.Google Scholar
[Pak19] , ‘Combinatorial inequalities’, Not. Am. Math. Soc. 66 (2019), 1109–1112.Google Scholar
[Pak22] , ‘What is a combinatorial interpretation? in Open Problems in Algebraic Combinatorics (AMS, Providence, RI, to appear), 1–58.Google Scholar | arXiv
[Pap94] , Computational Complexity (Addison-Wesley, Reading, MA, 1994), 1–523.Google Scholar
[Por33] , ‘A history of the classical isoperimetric problem’, in Contributions to the Calculus of Variations (University of Chicago Press, Chicago, 1933), 475–523. Available at tinyurl.com/526frnkf.Google Scholar
[StR81] , ‘Sur le volume des corps convexes symétriques (in French)’, in Initiation Seminar on Analysis (Publications Mathematics de l’Universite Pierre et Marie Curie , Paris, 1981), 1–25.Google Scholar
[Schn85] , ‘On the Aleksandrov–Fenchel inequality’, in Discrete Convexity (New York Academy of Sciences, NY, 1985), 132–141.Google Scholar
[Schn90a] , ‘On the Aleksandrov–Fenchel inequality for convex bodies. I.’, Results Math. 17 (1990), 287–295.Google Scholar | DOI
[Schn90b] , ‘A stability estimate for the Aleksandrov–Fenchel inequality, with an application to mean curvature’, Manuscr. Math. 69 (1990), 291–300.Google Scholar | DOI
[Schn94] , ‘Equality in the Aleksandrov–Fenchel inequality — present state and new results’, in Intuitive Geometry (North-Holland, Amsterdam, 1994), 425–438. Available at tinyurl.com/5bwrvu9n.Google Scholar
[Schn14] , Convex Bodies: The Brunn–Minkowski Theory, second edn (Cambridge University Press, Cambridge, UK, 2014), 1–736.Google Scholar
[Schr86] , Theory of Linear and Integer Programming (John Wiley, Chichester, 1986), 1–471.Google Scholar
[Schr03] , Combinatorial Optimization. Polyhedra and Efficiency, vols. A–C (Springer, Berlin, 2003), 1–1881.Google Scholar
[Schü72] , ‘Promotion des morphismes d’ensembles ordonnés (in French)’, Discrete Math. 2 (1972), 73–94.Google Scholar | DOI
[SW19] and , ‘A unifying method for the design of algorithms canonizing combinatorial objects’, Proc. 51st STOC (2019), 1247–1258.Google Scholar | DOI
[Sey80] , ‘Decomposition of regular matroids’, J. Comb. Theory, Ser. B 28 (1980), 305–359.Google Scholar | DOI
[SvH19] and , ‘Mixed volumes and the Bochner method’, Proc. Am. Math. Soc. 147 (2019), 5385–5402.Google Scholar | DOI
[SvH22] and , ‘The extremals of Minkowski’s quadratic inequality’, Duke Math. J. 171 (2022), 957–1027.Google Scholar | DOI
[SvH23] and , ‘The extremals of the Alexandrov–Fenchel inequality for convex polytopes’, Acta Math. 231 (2023), 89–204.Google Scholar | DOI
[She82] , ‘The XYZ conjecture and the FKG inequality’, Ann. Probab. 10 (1982), 824–827.Google Scholar | DOI
[Sid91] , ‘Inequalities for the number of linear extensions’, Order 8 (1991), 331–340.Google Scholar | DOI
[Sta81] , ‘Two combinatorial applications of the Aleksandrov–Fenchel inequalities’, J. Comb. Theory, Ser. A 31 (1981), 56–65.Google Scholar | DOI
[Sta86] , ‘Two poset polytopes’, Discrete Comput. Geom. 1(1) (1986), 9–23.Google Scholar | DOI
[Sta89] , ‘Log-concave and unimodal sequences in algebra, combinatorics, and geometry’, in Graph Theory and Its Applications (New York Academy of Sciences, NY, 1989), 500–535.Google Scholar
[Sta00] , ‘Positivity problems and conjectures in algebraic combinatorics’, in Mathematics: Frontiers and Perspectives (American Mathematical Society, Providence, RI, 2000), 295–319.Google Scholar
[Sta09] , ‘Promotion and evacuation’, Electron. J. Comb. 16(2) (2009), RP 9, 24.Google Scholar
[Sta12] , Enumerative Combinatorics, vol. 1, second edn and vol. 2 (Cambridge University Press, Cambridge, 2012 and 1999), 1–626 and 1–581.Google Scholar
[Tao08] , Structure and Randomness. Pages From Year One of a Mathematical Blog (American Mathematical Society, Providence, RI, 2008), 1–298. Section 1.3 is available at wp.me/p3qzP-h.Google Scholar
[Toda91] , ‘ is as hard as the polynomial-time hierarchy’, SIAM J. Comput. 20 (1991), 865–877.Google Scholar | DOI
[Tro95] , ‘Partially ordered sets’, in Handbook of Combinatorics, vol. 1 (Elsevier, Amsterdam, 1995), 433–480.Google Scholar
[VTL82] , and , ‘The recognition of series parallel digraphs’, SIAM J. Comput. 11 (1982), 298–313.Google Scholar | DOI
[vHYZ23] , and , ‘The extremals of the Kahn–Saks inequality’, Adv. in Math., 456(109892) (2024).Google Scholar | DOI
[vL82] , ‘The van der Waerden conjecture: Two proofs in one year’, Math. Intell. 4(2) (1982), 72–77.Google Scholar | DOI
[Wang18] , ‘A remark on the Alexandrov–Fenchel inequality’, J. Funct. Anal. 274 (2018), 2061–2088.Google Scholar | DOI
[Wig19] , Mathematics and Computation, (Princeton University Press, Princeton, NJ, 2019), 1–418. Available at math.ias.edu/avi/book.Google Scholar
[YK75] and , ‘Analysis of the subtractive algorithm for greatest common divisors’, Proc. Nat. Acad. Sci. USA 72 (1975), 4720–4722.Google ScholarPubMed | DOI
[Zhang98] , ‘Schur-convex functions and isoperimetric inequalities’, Proc. AMS 126 (1998), 461–470.Google Scholar | DOI
Cité par Sources :