#Ultra-log-concavity for rigid width-three posets

The \(P\)-Eulerian polynomial records descents in the linear extensions of a poset. Brenti conjectured that its coefficients are log-concave with no internal zeros [Bre89]. Real-rootedness is false even for naturally labeled width-two posets [Ste07], while ultra-log-concavity holds in width two by the rook-matroid construction of Alexandersson and Jal [AJ24].

Here we record an extension to a class of width-three posets. The proof encodes linear extensions by three-color words whose color-\(1\) and color-\(2\) classes are bases of transversal matroids. Rigidity makes this encoding exact.

#\(P\)-Eulerian polynomials

Let \(P\) be a naturally labeled poset on \([n]=\{1,\dotsc,n\}.\) A linear extension is a permutation \(\sigma=\sigma_1\dotsm\sigma_n\) compatible with the order of \(P.\) Write \(\mathcal L(P)\) for the set of linear extensions. A position \(i\lt{}n\) is a descent if \(\sigma_i\gt{}\sigma_{i+1}.\)

Definition (\(P\)-Eulerian polynomial).

The \(P\)-Eulerian polynomial is \[W_P(t)\coloneqq \sum_{\sigma\in\mathcal L(P)}t^{\operatorname{des}(\sigma)}.\]

Definition (Ultra-log-concavity).

A nonnegative sequence \((a_0,\dotsc,a_d)\) is ultra-log-concave of order \(d\) if \[\left(\frac{a_j}{\binom d j}\right)^2 \geq \frac{a_{j-1}}{\binom d{j-1}} \frac{a_{j+1}}{\binom d{j+1}} \qquad (1\leq j\lt{}d).\] It has no internal zeros if \(a_i,a_k\gt{}0\) and \(i\lt{}j\lt{}k\) imply \(a_j\gt{}0.\)

#Rigid choices

Let \(Z=z_1\lt{}\dotsm\lt{}z_h\) be a longest chain of \(P,\) and let \(X=x_1\lt{}\dotsm\lt{}x_r\) and \(Y=y_1\lt{}\dotsm\lt{}y_s\) be chains that partition \(P\setminus Z.\) Thus \(r+s=n-h.\) For \(q\notin Z,\) put \[p_q\coloneqq\#\{z\in Z:z\lt{}q\}, \qquad b_q\coloneqq h-\#\{z\in Z:z\gt{}q\}.\] The constrained order is generated by the order of \(P\) together with \[z\lt{}q\quad\text{if }z\in Z\text{ and }z\parallel q, \qquad y\lt{}x\quad\text{if }x\in X,\ y\in Y\text{ and }x\parallel y.\]

For \(x\in X,\) define \[\operatorname{lo}(x)\coloneqq\#\{y\in Y:y\lt{}x\}, \qquad \operatorname{hi}(x)\coloneqq s-\#\{y\in Y:y\gt{}x\}.\] If \(x=x_i,\) let \(K_x\) be the set of \(k\in\{0,\dotsc,s\}\) such that \[\operatorname{lo}(x)\leq k\leq\operatorname{hi}(x)\] and either \(k=\operatorname{hi}(x),\) or \(i\lt{}r\) and \(k\geq\operatorname{lo}(x_{i+1}).\) We use the conventions \(p_{y_0}=0\) and \(b_{y_{s+1}}=h.\)

Definition (Rigid choice).

The triple \((Z,X,Y)\) is a rigid choice if the constrained order is acyclic and the following conditions hold.

  • (D) If \(x\in X,\) \(y\in Y,\) and \(x\parallel y,\) then \(p_x\leq p_y.\)

  • (Y) For each \(1\leq k\leq s,\) the number \(\max(p_x,p_{y_{k-1}})\) is independent of the choice of \(x\in X\) with \(x\parallel y_k.\)

  • (X) For each \(x\in X,\) the pair \[\bigl(\max(p_x,p_{y_k}),\min(b_x,b_{y_{k+1}})\bigr)\] is independent of \(k\in K_x.\)

Since \(P\) is covered by the three chains \(Z,X,Y,\) it has width at most three.

#A three-color encoding

For a word \(u:E\to\{0,1,2\},\) write \[B(u,c)\coloneqq\{e\in E:u(e)=c\}.\] Let \(M_1\) and \(M_2\) be matroids on \(E.\) Consider the family \[\mathcal F(M_1,M_2)\coloneqq \{u:E\longrightarrow\{0,1,2\}: B(u,1)\in\mathcal B(M_1),\ B(u,2)\in\mathcal B(M_2)\}.\] The remaining positions have color \(0.\) Put \[R=|E|-\operatorname{rk}(M_1)-\operatorname{rk}(M_2),\] and define the generating polynomial \[Q_{\mathcal F}(\mathbf x)\coloneqq \sum_{u\in\mathcal F(M_1,M_2)} \prod_{e\in B(u,0)}x_e.\]

Proposition (Lorentzian generating polynomial).

If \(\mathcal F(M_1,M_2)\) is nonempty, then \(Q_{\mathcal F}\) is Lorentzian and homogeneous of degree \(R.\)

Proof

Apply the basis-generating differential operators of \(M_1\) and \(M_2\) to the squarefree monomial \(\prod_{e\in E}x_e.\) Terms in which the two bases overlap vanish, and the surviving monomial records the complementary color-\(0\) class. Using the dual basis polynomial, each basis-generating differential operator can be written as a product of operators \(\partial_{x_e}+\partial_{z_e}\) followed by the specialization \(\mathbf z=0.\) These operations preserve Lorentzianity by the Brändén–Huh theory [BH20].

#The theorem

Theorem (Rigid width-three posets).

Let \(P\) be a naturally labeled poset with \(n\) elements and height \(h.\) If \(P\) admits a rigid choice, and \[W_P(t)=\sum_{j\geq0}w_jt^j,\] then \(w_j=0\) for \(j\gt{}n-h,\) and \((w_0,\dotsc,w_{n-h})\) is ultra-log-concave of order \(n-h\) with no internal zeros.

Proof

The chains \(X\) and \(Y\) give two transversal matroids on a common set of positions. A linear extension of \(P\) determines a word in the corresponding family \(\mathcal F(M_1,M_2),\) whose color-\(0\) class has size \(n-h.\) The rigidity conditions say that the interval assigned to a position is independent of the intermediate linear extension; consequently this map is a bijection, and the number of descents is the number of marked color-\(0\) positions.

After setting the marked variables of \(Q_{\mathcal F}\) equal to \(t\) and the remaining variables equal to \(s,\) we obtain \[\sum_{j=0}^{n-h}w_j s^{n-h-j}t^j.\] This polynomial is Lorentzian. The bivariate characterization of Lorentzian polynomials gives ultra-log-concavity of order \(n-h\) and no internal zeros.

Bibliography

  1. [AJ24]Per Alexandersson and Aryaman Jal. Rook matroids and log-concavity of ${P}$-Eulerian polynomials. arXiv:2410.00127, 2024.
    .bib
    @article{AlexanderssonJal2024x,
Author = {Per Alexandersson and Aryaman Jal},
Title = {Rook matroids and log-concavity of ${P}$-{E}ulerian polynomials},
Year = {2024},
Eprint = {2410.00127},
  url = {https://arxiv.org/abs/2410.00127},
journal = {arXiv e-prints}
}
  2. [BH20]Petter Brändén and June Huh. Lorentzian polynomials. Annals of Mathematics, 192(3), November 2020.
    .bib
    @article{BrandenHuh2020,
  title = {Lorentzian polynomials},
  volume = {192},
  ISSN = {0003-486X},
  url = {http://dx.doi.org/10.4007/annals.2020.192.3.4},
  DOI = {10.4007/annals.2020.192.3.4},
  number = {3},
  journal = {Annals of Mathematics},
  publisher = {Annals of Mathematics},
  author = {Br{\"{a}}nd{\'{e}}n,  Petter and Huh,  June},
  year = {2020},
  month = nov
}
  3. [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},
}
  4. [Ste07]John R. Stembridge. Counterexamples to the poset conjectures of Neggers, Stanley, and Stembridge. Trans. Amer. Math. Soc., 359(3):1115–1128, 2007.
    .bib
    @article {Stembridge2007NeggersStanleyCounter,
    AUTHOR = {Stembridge, John R.},
     TITLE = {Counterexamples to the poset conjectures of {N}eggers,
              {S}tanley, and {S}tembridge},
   JOURNAL = {Trans. Amer. Math. Soc.},
  FJOURNAL = {Transactions of the American Mathematical Society},
    VOLUME = {359},
      YEAR = {2007},
    NUMBER = {3},
     PAGES = {1115--1128},
      ISSN = {0002-9947,1088-6850},
   MRCLASS = {06A07 (05A15)},
  MRNUMBER = {2262844},
MRREVIEWER = {David\ B.\ Penman},
       DOI = {10.1090/S0002-9947-06-04271-1},
       URL = {https://doi.org/10.1090/S0002-9947-06-04271-1},
}