The extremals of the Kahn-Saks inequality
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914851417227264 |
|---|---|
| author | van Handel, Ramon Yan, Alan Zeng, Xinmeng |
| author_facet | van Handel, Ramon Yan, Alan Zeng, Xinmeng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_13434 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The extremals of the Kahn-Saks inequality van Handel, Ramon Yan, Alan Zeng, Xinmeng Combinatorics Metric Geometry 06A07, 52A39, 52A40, 52B05 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. |
| title | The extremals of the Kahn-Saks inequality |
| topic | Combinatorics Metric Geometry 06A07, 52A39, 52A40, 52B05 |
| url | https://arxiv.org/abs/2309.13434 |