The lattice of antichains of intervals: Dyck paths, level sets, and sweep dimension
Abstract
The Clarke-Cormack-Burkowski lattice ℰn is the lattice of antichains of intervals of the chain {0,1,…,n−1}, the algebraic structure underlying minimal-interval semantics, a query semantics used in information retrieval. We give an explicit, elementary anti-isomorphism between ℰn minus its top element and the Stanley lattice of Dyck words of semilength n+1 (an anti-isomorphism whose existence is implicit in work of Ferrari and Munarini), under which the rank of an antichain is binomn+12 minus the area of the associated Dyck word. Hence the rank generating function of ℰn∖{⊤} is the reverse of the Carlitz-Riordan q-Catalan polynomial. Using a local limit theorem for the area of random-walk excursions, we confirm unconditionally an asymptotic formula of Takács: the size λn of the largest level set of ℰn satisfies λn∼κ 4n+1/(n+1)3, where κ≈1.0807. Finally, for the antichains of intervals of an arbitrary finite poset P we study the sweep dimension, the minimum number of linear orders needed to separate every interval from every element outside it. It equals the Dushnik-Miller dimension of the lattice of convex subsets of P, it is the least k for which P maps into ℝk so that every interval is the preimage of an upper orthant, and it lies between max(2,w) and 2w, where w is the width of P, both bounds being tight. Antichains of intervals embed, preserving joins, into k-dimensional staircase regions.
Related
- Simplicial Complexes of Antichains in Root Posets and Related Combinatorics of Dyck Paths
- Assouad--Nagata dimension of systolic complexes with almost flat intervals
- Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotics Aspects and Borges's Theorem
- Lattice points close to a smooth curve and squarefull numbers in short intervals. II
- Lattice paths on snake graphs for q-deformed rationals
BibTeX
@misc{boldi2026lattice,
title = {{The lattice of antichains of intervals: Dyck paths, level sets, and sweep dimension}},
author = {Paolo Boldi and Sebastiano Vigna},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41385},
eprint = {2610.41385},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41385},
}
RIS
TY - UNPB
TI - The lattice of antichains of intervals: Dyck paths, level sets, and sweep dimension
AU - Paolo Boldi
AU - Sebastiano Vigna
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41385
UR - https://arxiv.org/abs/2610.41385
AB - The Clarke-Cormack-Burkowski lattice ℰ_n is the lattice of antichains of intervals of the chain {0,1,…,n−1}, the algebraic structure underlying minimal-interval semantics, a query semantics used in information retrieval. We give an explicit, elementary anti-isomorphism between ℰ_n minus its top element and the Stanley lattice of Dyck words of semilength n+1 (an anti-isomorphism whose existence is implicit in work of Ferrari and Munarini), under which the rank of an antichain is binomn+12 minus the area of the associated Dyck word. Hence the rank generating function of ℰ_n∖{⊤} is the reverse of the Carlitz-Riordan q-Catalan polynomial. Using a local limit theorem for the area of random-walk excursions, we confirm unconditionally an asymptotic formula of Takács: the size λ_n of the largest level set of ℰ_n satisfies λ_n∼κ 4^n+1/(n+1)^3, where κ≈1.0807. Finally, for the antichains of intervals of an arbitrary finite poset P we study the sweep dimension, the minimum number of linear orders needed to separate every interval from every element outside it. It equals the Dushnik-Miller dimension of the lattice of convex subsets of P, it is the least k for which P maps into ℝ^k so that every interval is the preimage of an upper orthant, and it lies between max(2,w) and 2w, where w is the width of P, both bounds being tight. Antichains of intervals embed, preserving joins, into k-dimensional staircase regions.
ER -