Peaks and peak-nestings on unit interval graphs
Abstract
Unit interval graphs admit a classical Catalan encoding by area sequences, or equivalently by Dyck paths. We introduce a new statistic on these graphs, called peak-nesting, defined as the largest number of peak-cliques containing a common vertex. Through the correspondence with area sequences, peak-nesting also defines a new statistic on Dyck paths. We construct a bijection between Dyck paths and bicolored Motzkin paths which simultaneously records peak-nesting and the number of peaks. This yields a refinement of Touchard's identity, coefficient formulas involving Dyck paths of given height, and new combinatorial interpretations for several sequences recorded in the OEIS. We study the peak and peak-nesting polynomials over all unit interval graphs and over the subclasses of connected, Abelian, $2$-nested, and reduced unit interval graphs. For these families we obtain closed formulas, recurrences, and, for the symmetric cases, nonnegative expansions in the gamma-basis with explicit combinatorial interpretations. We also investigate questions regarding the location of zeros and the log-concavity of the corresponding coefficient sequences: some of the polynomial families form generalized Sturm sequences, whereas others fail to be real-rooted but appear nevertheless to have log-concave coefficients. Finally, we relate the peak-clique presentation of a unit interval graph to lattice path matroids.
Related
- The λ-chain condition for unit interval determinantal fiber rings
- Proof of a Conjecture of Matherne, Morales, and Selover on Encodings of Unit Interval Orders
- Beyond left-continuity: t-norms on the fuzzy unit interval induced by pairs of t-norms
- From Unit Interval Orders to Totally Nonnegative Matrices: Permanental Inequalities and Bruhat-Increasing Bijections
- Bicoloured-interval and interval-sandwich graphs: two new classes in the tolerance hierarchy
BibTeX
@misc{alexandersson2026peaks,
title = {{Peaks and peak-nestings on unit interval graphs}},
author = {Per Alexandersson and Leonardo Saud Maia Leite},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38084},
eprint = {2609.38084},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38084},
}
RIS
TY - UNPB
TI - Peaks and peak-nestings on unit interval graphs
AU - Per Alexandersson
AU - Leonardo Saud Maia Leite
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38084
UR - https://arxiv.org/abs/2609.38084
AB - Unit interval graphs admit a classical Catalan encoding by area sequences, or equivalently by Dyck paths. We introduce a new statistic on these graphs, called peak-nesting, defined as the largest number of peak-cliques containing a common vertex. Through the correspondence with area sequences, peak-nesting also defines a new statistic on Dyck paths. We construct a bijection between Dyck paths and bicolored Motzkin paths which simultaneously records peak-nesting and the number of peaks. This yields a refinement of Touchard's identity, coefficient formulas involving Dyck paths of given height, and new combinatorial interpretations for several sequences recorded in the OEIS. We study the peak and peak-nesting polynomials over all unit interval graphs and over the subclasses of connected, Abelian, $2$-nested, and reduced unit interval graphs. For these families we obtain closed formulas, recurrences, and, for the symmetric cases, nonnegative expansions in the gamma-basis with explicit combinatorial interpretations. We also investigate questions regarding the location of zeros and the log-concavity of the corresponding coefficient sequences: some of the polynomial families form generalized Sturm sequences, whereas others fail to be real-rooted but appear nevertheless to have log-concave coefficients. Finally, we relate the peak-clique presentation of a unit interval graph to lattice path matroids.
ER -