Zig-zag Eulerian polynomials

T. Kyle Petersen, Yan Zhuang

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:

  1. 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.
  2. Generating Functions and Recurrences: They derive functional equations for generating functions $G_n(p, q, x)$ that refine the zig-zag order polynomials.
  3. 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).
  4. 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

Abstract

For any finite partially ordered set $P$, the $P$-Eulerian polynomial is the generating function for the descent number over the set of linear extensions of $P$, and is closely related to the order polynomial of $P$ arising in the theory of $P$-partitions. Here we study the $P$-Eulerian polynomial where $P$ is a naturally labeled zig-zag poset; we call these zig-zag Eulerian polynomials. A result of Brändén implies that these polynomials are gamma-nonnegative, and hence their coefficients are symmetric and unimodal. The zig-zag Eulerian polynomials and the associated order polynomials have appeared fleetingly in the literature in a wide variety of contexts$\unicode{x2014}$e.g., in the study of polytopes, magic labelings of graphs, and Kekulé structures$\unicode{x2014}$but they do not appear to have been studied systematically. In this paper, we use a "relaxed" version of $P$-partitions to both survey and unify results. Our technique shows that the zig-zag Eulerian polynomials also capture the distribution of "big returns" over the set of (up-down) alternating permutations, as first observed by Coons and Sullivant. We develop recurrences for refined versions of the relevant generating functions, which evoke similarities to recurrences for the classical Eulerian polynomials. We conclude with a literature survey and open questions.
BibTeX
@inproceedings{petersen2024zig,
  author = {T. Kyle Petersen and Yan Zhuang},
  title = {{Zig-zag Eulerian polynomials}},
  booktitle = {European},
  year = {2024},
  doi = {10.1016/j.ejc.2024.104073},
}
Figure