Ehrhart $h^*$-polynomials of $(132,213)$-avoiding permutation polytopes: A repair cone and eventual real-rootedness

Source abstract

Let $P_d(132,213)$ be the convex hull of the permutations in $S_d$ that avoid $132$ and $213$, and let $H_d(t)$ be its Ehrhart $h^*$-polynomial, defined by $\sum_{m\ge0}|mP_d(132,213)\cap\mathbb{Z}^d|t^m=\frac{H_d(t)}{(1-t)^d}$. We give an explicit lattice equivalence between this polytope, a path-Laplacian deficit polytope, and twice a translated chain-poset permutahedron. The resulting face description and triangulation give a self-contained proof of Davis and Sagan's cubicality and volume conjecture, with normalized volume $2^{d-1}d^{d-3}$ for $d\ge2$. For $d\ge3$, the coefficient of $t^{d-1}$ in $H_d(t)$ counts strong tournament score sequences. The refined Eulerian expansion of $H_d(t)$ has a negative coordinate already at $d=7$. We construct a compatible cone of adjacent signed differences that accommodates this obstruction. Its largest uniform repair parameter is $2-\sqrt{3}$, and membership reduces to explicit geometric-tail inequalities. An exact dataset and reconstruction algorithm verify these inequalities through $d=1000$. A marked-component identity, discrete smoothing, and Darroch's mode theorem (Ann. Math. Statist. 35 (1964), 1317--1321, Theorem 4) prove them for every $d\ge2^{72}$. Thus $H_d(t)$ has only negative real zeros for $3\le d\le1000$ and for $d\ge2^{72}$, while $H_1(t)=H_2(t)=1$. Uniform real-rootedness in the intervening range remains open.