TL;DR
This paper provides the first systematic study of "zig-zag Eulerian polynomials," a class of polynomials arising from zig-zag partially ordered sets (posets). By introducing a novel framework of "relaxed $P$-partitions," the authors unify disparate results from geometry, chemistry, and combinatorics, proving that these polynomials are gamma-nonnegative and establishing new recurrences that mirror those of classical Eulerian polynomials.
What Problem Does This Paper Address?
In enumerative combinatorics, Eulerian polynomials are fundamental objects that track the distribution of "descents" (positions where a sequence decreases) in permutations. While the classical case is well-understood, the theory of $P$-Eulerian polynomials—which generalizes this to permutations constrained by a partially ordered set $P$—is a vast field with many specialized sub-cases.
One such case involves zig-zag posets (posets with an alternating up-down structure). While these have appeared sporadically in various contexts—such as the study of simplicial polytopes, magic labelings of graphs, and even the stability of chemical "Kekulé structures"—they had never been studied as a unified family. The authors set out to provide a systematic treatment, specifically addressing the connection between these posets and the distribution of "big returns" in alternating permutations.
Methods
The authors employ several key combinatorial techniques:
- Relaxed $P$-partitions: The core innovation is a modification of Stanley’s classical $P$-partition theory. Standard $P$-partitions are order-preserving maps from a poset to integers. The authors define "relaxed" versions where the strictness of the inequality depends on the distance between labels (e.g., $g(i) \leq g(j)$ if $i \leq j+1$). This allows them to bridge the gap between different labeling conventions.
- Generating Functions and Recurrences: They derive functional equations for generating functions $G_n(p, q, x)$ that refine the zig-zag order polynomials.
- Gamma-Nonnegativity: Using a result by Brändén, the authors prove that these polynomials can be expanded in a specific basis $\{\gamma_{n,j} t^{j+1}(1+t)^{n-2(j+1)}\}$ with non-negative coefficients. This is a powerful property that automatically implies the coefficients are both symmetric and unimodal (rising to a peak and then falling).
- Refined Statistics: They introduce $(p, q)$-analogues to track specific values within the partitions, allowing for the derivation of derivative-based recurrences.
Datasets
As a theoretical mathematics paper, this work does not use empirical datasets. However, it heavily references and contributes to the Online Encyclopedia of Integer Sequences (OEIS):
- A050446: The array of zig-zag order polynomial values.
- A205497: The zig-zag Eulerian numbers.
- The paper provides computed tables for these values up to $n=10$ to support their conjectures.
Key Insights and Ideas
- The "Big Return" Connection: The authors prove that the zig-zag Eulerian polynomial $Z_n(t)$ is exactly $t$ times the generating function for "big returns" in alternating permutations. A "big return" occurs when a value $j$ appears to the right of $j+1$ in a permutation, but with the added constraint of the alternating up-down structure.
- Structural Symmetry: They demonstrate that "up-down" and "down-up" zig-zag posets yield the same Eulerian polynomials, providing a bijection that simplifies the landscape of these objects.
-
Analogy to Classical Theory: One of the most striking "aha moments" is the discovery of Corollary 1.2, which shows that zig-zag Eulerian polynomials satisfy a derivative recurrence: $$Z_{n+1}(t) = t(1-t)\frac{d}{dt}[tU_n(s,t)]_{s=t} + (n+1)tZ_n(t)$$ This almost perfectly mirrors the fundamental recurrence for classical Eulerian polynomials, suggesting a deep structural harmony between the two.
-
Interdisciplinary Reach: The paper highlights that these abstract combinatorial objects are the same ones used to count perfect matchings in hexagonal lattices (Kekulé structures) in chemistry.
Key Results
- Gamma-Nonnegativity (Theorem 2.5): Formally established that $Z_n(t)/t$ is gamma-nonnegative, confirming long-standing conjectures about the symmetry and unimodality of these coefficients.
- Refined Recurrences (Theorem 1.1): Developed a recursive procedure to compute the refined generating functions $G_n(p, q, x)$ and $U_n(s, t)$.
- Order Polynomial Recurrences (Theorem 3.15): Introduced new recurrences for the generating functions of the order polynomials $F_m(y)$, including a continued-fraction-like relation: $$F_m(y) = \frac{1}{F_{m-1}(-y) - y}$$
Limitations and Future Work
- Real-Rootedness Conjecture: While the authors proved unimodality via gamma-nonnegativity, they conjecture (Conjecture 6.1) that $Z_n(t)$ has only real roots. This is a stronger property that remains unproven for the general case, though they verified it up to $n=35$.
- Direct Combinatorial Proofs: The authors note that while they have proven symmetry and unimodality via algebraic means, a "direct" combinatorial explanation for the distribution of big returns is still missing.
- Entringer Refinements: They introduced refinements for Entringer numbers (which count alternating permutations starting with a specific value) but have not yet found a "nice" linear recurrence for the resulting polynomials $U_{n,r}(s, t)$.
- Higher Rank Generalizations: The paper touches on $r$-chainlink posets (a generalization of zig-zags), opening a new door for studying "rank $r$" Eulerian polynomials.
Summary updated