The extremals of the Kahn-Saks inequality.(English)Zbl 07919769
Summary: A classical result of Kahn and Saks states that given any partially ordered set with two distinguished elements, the number of linear extensions in which the ranks of the distinguished elements differ by \(k\) is log-concave as a function of \(k\). The log-concave sequences that can arise in this manner prove to exhibit a much richer structure, however, than is evident from log-concavity alone. The main result of this paper is a complete characterization of the extremals of the Kahn-Saks inequality: we obtain a detailed combinatorial understanding of where and what kind of geometric progressions can appear in these log-concave sequences. This settles a partial conjecture of Chan-Pak-Panova, while the analysis uncovers new extremals that were not previously conjectured. The proof relies on a much more general geometric mechanism – a hard Lefschetz theorem for nef classes that was obtained in the setting of convex polytopes by Shenfeld and Van Handel – which forms a model for the investigation of such structures in other combinatorial problems.
MSC:
| 06A07 | Combinatorics of partially ordered sets |
| 52A39 | Mixed volumes and related topics in convex geometry |
| 52A40 | Inequalities and extremum problems involving convexity in convex geometry |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
Keywords:
partially ordered sets;log-concave sequences;extremal problems;Alexandrov-Fenchel inequality;hard Lefschetz theoremCite
References:
| [1] | Adiprasito, K.; Huh, J.; Katz, E., Hodge theory of matroids, Not. Am. Math. Soc., 64, 1, 26-30, 2017 ·Zbl 1359.05017 |
| [2] | Alexandrov, A. D., Zur Theorie der gemischten Volumina von konvexen Körpern II, Mat. Sb. N.S., 2, 1205-1238, 1937 ·Zbl 0018.27601 |
| [3] | Brändén, P.; Huh, J., Lorentzian polynomials, Ann. Math. (2), 192, 3, 821-891, 2020 ·Zbl 1454.52013 |
| [4] | Brightwell, G.; Winkler, P., Counting linear extensions, Order, 8, 3, 225-242, 1991 ·Zbl 0759.06001 |
| [5] | Chan, S. H.; Pak, I., Introduction to the combinatorial atlas, Expo. Math., 40, 4, 1014-1048, 2022 ·Zbl 1504.05027 |
| [6] | Chan, S. H.; Pak, I., Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy, 2023, Preprint |
| [7] | Chan, S. H.; Pak, I., Log-concave poset inequalities, J. Assoc. Math. Res., 2, 1, 53-153, 2024 ·Zbl 1547.05035 |
| [8] | Chan, S. H.; Pak, I.; Panova, G., Extensions of the Kahn-Saks inequality for posets of width two, Comb. Theory, 3, 1, Article 8 pp., 2023 ·Zbl 1508.05007 |
| [9] | Fulton, W., Introduction to Toric Varieties, Annals of Mathematics Studies, vol. 131, 1993, Princeton University Press: Princeton University Press Princeton, NJ ·Zbl 0813.14039 |
| [10] | Gromov, M., Convex sets and Kähler manifolds, (Advances in Differential Geometry and Topology, 1990, World Sci. Publ.: World Sci. Publ. Teaneck, NJ), 1-38 ·Zbl 0770.53042 |
| [11] | Hu, J.; Xiao, J., Numerical characterization of the hard Lefschetz classes of dimension two, 2023, Preprint |
| [12] | Huh, J., Combinatorial applications of the Hodge-Riemann relations, (Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018, vol. IV. Invited Lectures, 2018, World Sci. Publ.: World Sci. Publ. Hackensack, NJ), 3093-3111 ·Zbl 1448.05016 |
| [13] | Kahn, J.; Saks, M., Balancing poset extensions, Order, 1, 2, 113-126, 1984 ·Zbl 0561.06004 |
| [14] | Ma, Z. Y.; Shenfeld, Y., The extremals of Stanley’s inequalities for partially ordered sets, Adv. Math., 436, Article 109404 pp., 2024 ·Zbl 07781638 |
| [15] | Schneider, R., On the Aleksandrov-Fenchel inequality, (Discrete Geometry and Convexity. Discrete Geometry and Convexity, New York, 1982. Discrete Geometry and Convexity. Discrete Geometry and Convexity, New York, 1982, Ann. New York Acad. Sci., vol. 440, 1985, New York Acad. Sci.: New York Acad. Sci. New York), 132-141 ·Zbl 0567.52004 |
| [16] | Schneider, R., Convex Bodies: the Brunn-Minkowski Theory, 2014, Cambridge University Press: Cambridge University Press Cambridge ·Zbl 1287.52001 |
| [17] | Shenfeld, Y.; van Handel, R., The extremals of the Alexandrov-Fenchel inequality for convex polytopes, Acta Math., 231, 1, 89-204, 2023 ·Zbl 1529.05032 |
| [18] | Stanley, R. P., Two combinatorial applications of the Aleksandrov-Fenchel inequalities, J. Comb. Theory, Ser. A, 31, 1, 56-65, 1981 ·Zbl 0484.05012 |
| [19] | Stanley, R. P., Two poset polytopes, Discrete Comput. Geom., 1, 1, 9-23, 1986 ·Zbl 0595.52008 |
| [20] | Stanley, R. P., Log-concave and unimodal sequences in algebra, combinatorics, and geometry, (Graph Theory and Its Applications: East and West. Graph Theory and Its Applications: East and West, Jinan, 1986. Graph Theory and Its Applications: East and West. Graph Theory and Its Applications: East and West, Jinan, 1986, Ann. New York Acad. Sci., vol. 576, 1989, New York Acad. Sci.: New York Acad. Sci. New York), 500-535 ·Zbl 0792.05008 |
| [21] | Teissier, B., Bonnesen-type inequalities in algebraic geometry. I. Introduction to the problem, (Seminar on Differential Geometry. Seminar on Differential Geometry, Ann. of Math. Stud., vol. 102, 1982, Princeton Univ. Press: Princeton Univ. Press Princeton, N.J.), 85-105 ·Zbl 0494.52009 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
