Chain Covers in the Boolean Lattice

Zoltán Lóránt Nagy, Balázs Patkós · 2026

Read Chain Covers in the Boolean Lattice by Zoltán Lóránt Nagy, Balázs Patkós (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29385.txt.

Description

Nagy and Patkós study chain covers in the Boolean lattice, the family of all subsets of an n-element set ordered by inclusion. A chain is a nested sequence of subsets. They ask for the fewest chains so that every strict chain of a given length r appears inside one of them. For length one this is the classical chain-decomposition problem behind Dilworth's and Sperner's theorems.

They work in two regimes. With r fixed and n growing, they bound the needed number of chains between a multinomial quantity M and that quantity times a logarithmic factor. The two bounds thus differ only by that factor. Near the maximal length, where the chain length is n minus a fixed t, they determine the count asymptotically: it is a constant times n factorial. That constant is a limit density tied to smallest sets meeting every subcube of a given dimension.

Catalog record

CREATORZoltán Lóránt Nagy, Balázs Patkós
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.29385

Browse the full library · About the Tower of Babel