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
| CREATOR | Zoltán Lóránt Nagy, Balázs Patkós |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 26 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.29385