Parking trees and the toric g-vector of nestohedra
Richard EHRENBORG, Gábor HETYEI and Margaret READDY · 2025
Read Parking trees and the toric g-vector of nestohedra by Richard EHRENBORG, Gábor HETYEI and Margaret READDY (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-04815.txt.
Introduction
Richard Ehrenborg and two colleagues decode the toric g-vector of nestohedra and related polytopes. These shape invariants pack deep combinatorial data into a short vector. Nonnegativity of the entries was known for several classic families without clear meanings.
The entries of any dual simplicial polytope's toric g-vector split into gamma-vector parts with positive weights. For the associahedron, cyclohedron, and permutahedron, meanings come from pattern avoidance. Parking functions, plain functions, and new parking trees carry the counts. The parking tree model extends to all chordal nestohedra, proving nonnegativity across the whole family at once.
Catalog record
| CREATOR | Richard EHRENBORG, Gábor HETYEI and Margaret READDY |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-04815
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Parking trees and the toric g-vector of nestohedra Richard EHRENBORG, Gábor HETYEI and Margaret READDY Abstract . We express the toric g g -vector entries of any simple polytope as a nonnegative integer linear combination of its γ \gamma -vector entries. Using this expression we obtain that the toric g g -vector of the associahedron is the ascent statistic of 123 123 -avoiding parking functions. An analogous result holds for the cyclohedron and 123 123 -avoiding functions. We prove that the toric g g -vector of the permutahedron records the ascent statistics of parking trees representing 123 123 -avoiding parking functions. We indicate how our approach extends to all chordal nestohedra. 2000 Mathematics Subject Classification Primary 52B05, 52B12, 52B15, Secondary 05A15, 05E45 1. Introduction In his book, Enumerative Combinatorics, Richard Stanley wrote that the toric g -vector of an Eulerian poset is “an exceedingly subtle invariant”; see [ 34 , Section 3.16] . As an example, he computed the toric g -vector of the permutahedron up to dimension 5 ; see [ 33 , Page 195] . In the present paper we not only give a closed form formula for the toric g -vector of this polytope and of several other simple polytopes, but we also find a combinatorial interpretation in each case. The key result making such computations and interpretations possible is Theorem 3.4 . It expresses the entries of the toric g -vector of a simple polytopes as nonnegative integer linear combinations of its \gamma -vector entries. This result naturally inspires us to revisit combinatorial models for the \gamma -vectors of classical simple polytopes. The n -dimensional cube is the most basic example of a simple polytope, where the \gamma -vector is straightforward and the toric g -vector is well known; see Corollaries 4.9 and 4.10 . Our approach offers new enumerative results. We give a combinatorial interpretation of the toric g -vector of the associahedron in Theorem 6.3 , stating that the k th entry is given by the number of 123 -avoiding parking functions f:[n]\longrightarrow[n] that have exactly k ascents. The \gamma -vector of the associahedron is discussed alongside that of the permutahedron and of the cyclohedron in the work of Postnikov, Reiner and Williams [ 25 ] . As in their work on the \gamma -vector, our computation of the toric g -vector of the cyclohedron is analogous to that of the associahedron. For the cyclohedron we replace the set of 123 -avoiding parking functions with the set of 123 -avoiding functions f:[n]\longrightarrow[n] . Postnikov, Reiner and Williams [ 25 ] expressed the \gamma -vector of a permutahedron in terms of the peak statistics of all permutations containing no double descents and no final descent. Our key observation is that their result may be translated into a result on the peak statistics of all plane 0 - 1 - 2 trees having a descending labeling on the vertices. The equivalence of the two statistics may be shown using a restricted variant of the Foata–Strehl group action, first considered by Brändén [ 4 ] . Having a descending vertex labeling is also part of our definition of a parking tree that we introduce as a variant of the definitions given in [ 9 , Section 8] and in [ 18 ] , inspired by an exercise of Sagan [ 28 , Ch 1. Exercise (32)(c)] . In Theorem 9.3 we express the toric g -vector of the permutahedron in terms of the peak statistics of parking trees representing 123 -avoiding parking functions. This approach extends to all chordal nestohedra , studied by Postnikov, Reiner and Williams [ 25 ] . Our paper raises many open questions, the most important is the following. It is inspired by Theorem 3.4 and the Nevo–Petersen conjecture [ 23 , Conjecture 1.4] stating that the \gamma -vector entries of a simplicial complex that is a flag homology sphere satisfy the Kruskal–Katona inequalities. Conjecture 1.1 . When the \gamma -vector entries of a simple polytope satisfy the Kruskal–Katona inequalities, the same holds for its toric g -vector. The paper is organized as follows. In the preliminaries section we introduce two essential bijections. The first, due to Krattenthaler, is between 123 -avoiding permutations and Dyck paths. The second, due to Garsia and Haiman, is between functions on the set [n]=\{1,2,\ldots,n\} and pairs of compatible permutations and lattice paths. Their important observation is that when the function is a parking function, the associated lattice path is a Dyck path. We also discuss the Foata–Strehl group action on the symmetric group. In Section 3 we show how to compute the toric g -vector of a simple polytope in terms of its \gamma -vector. This computation involves the toric g -contribution polynomials g_{n,j}(x) whose coefficients are described in terms of counting peaks in Dyck paths. In Section 4 we give two interpretations of the coefficients of these polynomials. One of these is in terms of ascent sets in 123 -avoiding permutations. In Section 5 we obtain generating functions for the toric g -contribution polynomials. We combine the bijections of Garsia–Haiman and Krattenthaler in Section 6 to prove our combinatorial interpretation of the toric g -vector of the associahedron. We modify our arguments to obtain a similar result for the cyclohedron in Section 7 . Parking trees are introduced in Section 8 . They form the essential structure in order to obtain an explicit expression for the toric g -polynomial of the permutahedron, completing Stanley’s quest for computing these polynomials; see Section 9 . Finally in Section 10 we extend our results to nestohedra associated with chordal building sets. We end with open problems in Section 11 . 2. Preliminaries 2.1. Permutations For a non-negative integer n , let [n] denote the set \{1,2,\ldots,n\} . Similarly for two integers i\leq j , let [i,j] denote the interval \{i,i+1,\ldots,j\} . Let {\mathfrak{S}}_{n} denote the symmetric group on n elements. We choose the underlying set to be the set [n] . The index i\in[n-1] is an ascent of a permutation \pi=(\pi(1),\pi(2),\ldots,\pi(n))\in{\mathfrak{S}}_{n} if \pi(i)<\pi(i+1) , otherwise i is a descent . The ascent set and descent set of a permutation \pi are given by \displaystyle\Asc(\pi) \displaystyle=\{i\in[n-1]:\pi(i)<\pi(i+1)\}, \displaystyle\Des(\pi) \displaystyle=\{i\in[n-1]:\pi(i)>\pi(i+1)\}. The number of ascents and descents are denoted by \asc(\pi)=|\Asc(\pi)| , respectively \des(\pi)=|\Des(\pi)| . Finally, a permutation \pi\in{\mathfrak{S}}_{n} is 123 -avoiding if there is no triple 1\leq i_{1}<i_{2}<i_{3}\leq n satisfying \pi(i_{1})<\pi(i_{2})<\pi(i_{3}) . For more on pattern avoidance, see [ 19 ] . 2.2. Lattice paths A Dyck path of semilength n is a lattice path from the origin (0,0) to (2n,0) composed of n up steps (1,1) and n down steps (1,-1) that does not go below the horizontal axis. We may encode such a Dyck path with the associated Dyck word by recording each up step by the letter U and each down step by the letter D . The number of Dyck paths, and hence also the number Dyck words, of semilength n is the n th Catalan number \displaystyle C_{n} \displaystyle=\frac{1}{n+1}\cdot\binom{2n}{n}. The generating function for the Catalan numbers is well-known: \displaystyle C(t) \displaystyle=\sum_{n\geq 0}C_{n}\cdot t^{n}=\frac{1-\sqrt{1-4t}}{2t}. (2.1) By rotating our perspective by \pi/4 radians counterclockwise, we may also consider paths from the origin to the point (n,n) taking North steps