#Tableaux and polytopes
This page collects real-rootedness results from tableaux and polytope combinatorics: descent polynomials of standard Young tableaux, Ehrhart polynomials from Schur functions, and related families. The main tools are interlacing, Brenti’s Ehrhart criterion, and occasionally total-positivity methods. For the broader context, see unimodality and real-rootedness.
#Brenti’s Ehrhart criterion
The examples below use the same bridge between Ehrhart theory and real-rootedness. Suppose \(L(m)\) is a polynomial of degree \(d,\) and define the numerator \(H(t)\) by \[\sum_{m\geq 0} L(m)t^m = \frac{H(t)}{(1-t)^{d+1}}.\] In the factored cases below, the hypotheses in Brenti’s Worpitzky-transform criterion [Thm. 4.6.1, Bre89] are checked directly from the linear-factor product. The conclusion is that the numerator \(H(t)\) has only real roots. Thus the proof strategy is to identify the desired descent or \(h^*\)-polynomial as such a numerator and then prove that \(L(m)\) factors with only real roots.
#Descent polynomials of standard Young tableaux
Example (Descents in standard Young tableaux).
For a non-skew shape \(\lambda\) with \(n\) boxes, the descent-generating polynomial (\(i\) is a descent if \(i+1\) appears in a strictly lower row) \[W_\lambda(t) \coloneqq \sum_{T \in \SYT(\lambda)} t^{\des(T)}\] is real-rooted [Thm. 5.2.3, Bre89]. The argument proceeds in two steps. First, [Eq. (7.96), Sta01] gives the identity \[\sum_{m \geq 0} \schurS_{\lambda}(1^m)\,z^m = \frac{W_\lambda(z)}{(1-z)^{n+1}},\] which identifies \(W_\lambda(z)\) as the \(h^*\)-polynomial of the associated order polytope, and \(m \mapsto \schurS_\lambda(1^m)\) as its Ehrhart polynomial. Second, the hook-content formula gives \[\schurS_\lambda(1^m) = \prod_{u \in \lambda} \frac{m + c(u)}{h(u)},\] where \(c(u)\) is the content and \(h(u)\) the hook length of cell \(u.\) Each factor is linear in \(m,\) so the relevant Ehrhart/order polynomial is real-rooted. By Brenti’s Ehrhart criterion, the numerator is real-rooted, giving real-rootedness of \(W_\lambda(t).\)
This argument does not extend to skew shapes: the Ehrhart polynomial of \(\lambda/\mu\) need not be real-rooted, so Brenti’s criterion does not apply (see the remark below).
[Br04] shows moreover that \(W_\lambda(t)\) interlaces \(W_{\lambda^+}(t)\) whenever \(\lambda^+\) is obtained from \(\lambda\) by adding a box. In particular, for \(\lambda=(n,n),\) \(W_\lambda(t)\) is the Narayana polynomial \(N_n(t).\)
Remark (Skew shapes).
For skew shapes \(\lambda/\mu,\) the identity \(\sum_{m\geq 0} \schurS_{\lambda/\mu}(1^m)\,z^m = W_{\lambda/\mu}(z)/(1-z)^{n+1}\) still holds, but the Ehrhart polynomial \(m \mapsto \schurS_{\lambda/\mu}(1^m)\) need not be real-rooted, so Brenti’s criterion does not apply. Whether \(W_{\lambda/\mu}(t)\) is nevertheless real-rooted for all skew shapes is open.
#Schur Ehrhart polynomials
Example (Ehrhart polynomials from Schur functions).
Let \(k = \ell(\lambda)\) be the number of parts of \(\lambda.\) The map \[n \mapsto |\SSYT(n \lambda, k)|,\] counting semi-standard Young tableaux of shape \(n\lambda\) with entries in \(\{1,\dotsc,k\},\) is a polynomial in \(n.\) The Weyl character formula gives \[P_\lambda(n) \coloneqq \prod_{1 \leq i \lt j \leq k} \frac{n(\lambda_i - \lambda_j)+j-i}{j-i}.\] Since \(\lambda_i \geq \lambda_j\) for \(i \lt{} j,\) each factor is linear in \(n\) with a non-positive root, so \(P_\lambda(n)\) is real-rooted as a product of such factors. By Brenti’s Ehrhart criterion, this implies that the corresponding \(h^*\)-polynomial is also real-rooted. Brändén [Br04] showed moreover that \(P_\lambda(n)\) interlaces \(P_\mu(n)\) whenever \(\mu\) covers \(\lambda\) in Young’s lattice. The above map is the Ehrhart polynomial of the Gelfand–Tsetlin polytope associated with \(\lambda\) and \(k.\)
We note that the map \[n \mapsto |\SSYT(n \lambda/ n\mu, k)|\] for skew shapes is not real-rooted in general: \(\lambda =(3,2),\) \(\mu = (1)\) gives for \(k=3\) the polynomial \(\frac{1}{4} (n+1)^2 \left(7 n^2+10 n+4\right)\) which has non-real roots.
It does look like the corresponding \(h^*\)-polynomials are real-rooted even for skew shapes. For non-skew shapes, this is proved by F. Brenti [Bre89].
Bibliography
- [Br04]Petter Brändén. On operators on polynomials preserving real-rootedness and the Neggers-Stanley conjecture. Journal of Algebraic Combinatorics, 20(2):119–130, September 2004.
.bib
@article{Branden2004operators, title = {On Operators on Polynomials Preserving Real-Rootedness and the {N}eggers-{S}tanley Conjecture}, volume = {20}, ISSN = {0925-9899}, url2 = {http://dx.doi.org/10.1023/B:JACO.0000047295.93525.df}, DOI = {10.1023/b:jaco.0000047295.93525.df}, number = {2}, journal = {Journal of Algebraic Combinatorics}, publisher = {Springer Science and Business Media LLC}, author = {Petter Br{\"{a}}nd{\'{e}}n}, year = {2004}, month = sep, pages = {119–130} } - [Bre89]Francesco Brenti. Unimodal, log-concave and Pólya frequency sequences in combinatorics. Mem. Amer. Math. Soc., 81(413):viii+106, 1989.
.bib
@article{Brenti1989, AUTHOR = {Brenti, Francesco}, TITLE = {Unimodal, log-concave and {P}{\'{o}}lya frequency sequences in combinatorics}, JOURNAL = {Mem. Amer. Math. Soc.}, FJOURNAL = {Memoirs of the American Mathematical Society}, VOLUME = {81}, YEAR = {1989}, NUMBER = {413}, PAGES = {viii+106}, ISSN = {0065-9266,1947-6221}, MRCLASS = {05A15 (05A10 05A20)}, MRNUMBER = {963833}, MRREVIEWER = {Ira\ Gessel}, DOI = {10.1090/memo/0413}, URL = {https://doi.org/10.1090/memo/0413}, } - [Sta01]Richard P. Stanley. Enumerative Combinatorics: Volume 2. Cambridge University Press, First, 2001.
.bib
@book{StanleyEC2, author = {Richard P. Stanley}, title = {Enumerative {C}ombinatorics: {V}olume 2}, publisher = {Cambridge University Press}, year = {2001}, edition = {First}, isbn = {0521789877}, doi = {10.1017/CBO9780511609589} }