Rook polynomials of generalized snake posets
The order polytope of a generalized snake poset has a real-rooted $h^*$-polynomial, and deleting the last letter of the defining word gives an interlacing polynomial.
Results
A generalized snake poset $P(w)$ is a width-two poset built from a word $w$ in the letters $L$ and $R$. Under the Alexandersson–Jal correspondence between naturally labeled width-two posets and skew shapes, the incomparable cross-chain pairs of $P(w)$ form a board, and the $P(w)$-Eulerian polynomial is the non-nesting rook polynomial $$ M_w(x)=\sum_P x^{|P|} $$ of this board with its columns reversed. Here $P$ runs over the sets of cells with no two in a row and with columns strictly decreasing as rows increase [AJ24]. By Braun and Jal, $M_w$ is the $h^*$-polynomial of the order polytope of $P(w)$.
Theorem (Braun–Jal). If $w$ is nonempty, then $M_w$ is nonzero and real-rooted, and $M_{w'}\ll M_w$, where $w'$ is $w$ with its last letter deleted [BJ26].
Proof
Let $N_n(x)=\sum_k\frac1n\binom nk\binom n{k-1}x^k$ be the Narayana polynomials and $P_n=x^{-1}N_{n+1}$. Then $P_n$ is the rook polynomial of the full truncated staircase board of size $n$, and $M_w=P_{|w|+1}$ for a constant word $w$. In general, let $k$ be the last position (counting from $0$) where $w$ differs from its final letter, and $s=|w|-k-1$. Then $$ M_w=M_{w[:k+1]}\,P_s+x\,M_{w[:k]}\,G_s, $$ where $w[:j]$ is the prefix of length $j$ and $x\,G_{n-1}=P_n-(1+x)P_{n-1}$; each $G_n$ is a sum of rook polynomials of truncated staircase boards. The theorem follows by induction along this recurrence from three facts: each $P_n$ has nonnegative coefficients and real nonpositive roots, with $P_n\ll P_{n+1}$; $G_n\ll P_n$, and $G_n-G_{n-1}$ has nonnegative coefficients; and $(\lambda x+\nu)P_{m-1}+P_m\ll(\lambda x+\nu)P_m+P_{m+1}$ for $m\ge2$, $\lambda\ge0$ and $\nu\ge-1$.
References
See also rook matroid polynomials on symmetricfunctions.com.
- [BJ26] Benjamin Braun & Aryaman Jal. Order polytopes of generalized snake posets are $h^*$-real-rooted. arXiv e-prints, 2026.
BibTeX
@article{BraunJal2026x,
author = {Benjamin Braun and Aryaman Jal},
title = {Order polytopes of generalized snake posets are {$h^*$}-real-rooted},
year = {2026},
eprint = {2607.00922},
url = {https://arxiv.org/abs/2607.00922},
journal = {arXiv e-prints}
}
- [AJ24] Per Alexandersson & Aryaman Jal. Rook matroids and log-concavity of ${P}$-Eulerian polynomials. arXiv e-prints, 2024.
BibTeX
@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}
}
≔ Definitions
Letters L and R of a snake word
inductive SnakeLetter where
| L
| R
deriving DecidableEq, Repr
Constant snake words
def IsConstant (w : SnakeWord) : Prop :=
∀ a ∈ w, ∀ b ∈ w, a = b
Last position differing from the final letter
def IsLastChangeIndex (w : SnakeWord) (k : ℕ) : Prop :=
k ∈ changeIndices w ∧ ∀ j ∈ changeIndices w, j ≤ k
Board of a generalized snake poset
def generalizedSnakeBoard (w : SnakeWord) : FiniteSkewBoard where
cells := (snakeIncomparableBoard w).cells.image fun cell => (cell.1, w.length - cell.2)
Non-nesting rook polynomial of a board
def rookPolynomial (B : FiniteSkewBoard) : ℝ[X] := by
classical
exact (B.cells.powerset.filter (fun P => B.IsNonNestingPlacement P)).sum
(fun P => X ^ P.card)
Modified Narayana polynomials Pₙ
def modifiedNarayanaPolynomial (n : ℕ) : ℝ[X] :=
narayanaQuot (n + 1)
Auxiliary polynomials Gₙ
def rookSum : ℕ → ℝ[X] :=
fun n => ((List.range n).map fun i => truncatedStaircaseRookPolynomial n i).sum
⊢ Theorems
Modified Narayana polynomials are Pólya-frequency
theorem modifiedNarayanaPolynomial_isPFPolynomial (n : ℕ) :
IsPFPolynomial (modifiedNarayanaPolynomial n)
Consecutive modified Narayana polynomials interlace
theorem modifiedNarayanaPolynomial_strictInterl_succ (n : ℕ) :
StrictInterl (modifiedNarayanaPolynomial n) (modifiedNarayanaPolynomial (n + 1))
Affine combinations of consecutive modified Narayana polynomials interlace
theorem affineModifiedNarayanaInterlacing_modified :
AffineModifiedNarayanaInterlacing modifiedNarayanaPolynomial
Full truncated staircases have rook polynomial Pₙ
theorem FiniteSkewBoard.rookPolynomial_full_eq_modifiedNarayana
(n : ℕ) :
FiniteSkewBoard.truncatedStaircaseRookPolynomial n n =
modifiedNarayanaPolynomial n
The auxiliary polynomials Gₙ in terms of Pₙ
theorem GeneralizedSnakePosets.rookSum_recurrence {n : ℕ} (hn : n ≠ 0) :
X * FiniteSkewBoard.rookSum (n - 1) =
modifiedNarayanaPolynomial n - (1 + X) * modifiedNarayanaPolynomial (n - 1)
The auxiliary polynomial Gₙ interlaces Pₙ
theorem rookSum_strictInterl_modifiedNarayana {n : ℕ} (hn : n ≠ 0) :
StrictInterl (FiniteSkewBoard.rookSum n) (modifiedNarayanaPolynomial n)
Constant words give modified Narayana polynomials
theorem generalizedSnakeRookModel_snakePolynomial_of_isConstant {w : SnakeWord}
(hw : w.IsConstant) :
generalizedSnakeRookModel.snakePolynomial w = modifiedNarayanaPolynomial (w.length + 1)
Recurrence for the snake polynomials
theorem GeneralizedSnakePosets.rookPolynomial_recurrence {w : SnakeWord} {k : ℕ}
(hk : w.IsLastChangeIndex k) :
(generalizedSnakeBoard w).rookPolynomial =
(generalizedSnakeBoard (w.take (k + 1))).rookPolynomial *
modifiedNarayanaPolynomial (w.length - (k + 1)) +
X * (generalizedSnakeBoard (w.take k)).rookPolynomial *
FiniteSkewBoard.rookSum (w.length - (k + 1))
Snake polynomials are real-rooted and interlaceMain result
theorem GeneralizedSnakePosets.rookPolynomial_splits_and_interlaces {w : SnakeWord}
(hw : w ≠ []) :
((generalizedSnakeBoard w).rookPolynomial ≠ 0 ∧
(generalizedSnakeBoard w).rookPolynomial.Splits) ∧
Interlaces (generalizedSnakeBoard w.dropLast).rookPolynomial
(generalizedSnakeBoard w).rookPolynomial
Lean source RealRooted/Challenges/Combinatorial/GeneralizedSnakePosets.lean at revision d6670742. Formalized 2026-10-05.