Supersaturation in the Boolean lattice

zbMATH Open1316.05119MaRDI QIDQ5262057FDOQ5262057

Authors Andrew P. Dove, Ross J. Kang, Jean-Sébastien Sereni, J. Griggs

Publication date 9 July 2015

Full work available at URL https://arxiv.org/abs/1303.4336

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

symmetric chain decomposition method

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Extremal set theory (05D05)

Abstract: We prove a "supersaturation-type" extension of both Sperner's Theorem (1928) and its generalization by Erdos (1945) to k-chains. Our result implies that a largest family whose size is x more than the size of a largest k-chain free family and that contains the minimum number of k-chains is the family formed by taking the middle (k-1) rows of the Boolean lattice and x elements from the k-th middle row. We prove our result using the symmetric chain decomposition method of de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk (1951).

Recommendations

• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Subsets of posets minimising the number of chains
• Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains
• Supersaturation in posets and applications involving the container method
• On saturated \(k\)-Sperner systems

Cited in

(21)

• Comparable pairs in families of sets
• On the number of monotone sequences
• Supersaturation and stability for forbidden subposet problems.
• A generalization of the independence number
• Families in posets minimizing the number of comparable pairs
• Supersaturation, counting, and randomness in forbidden subposet problems
• Packing and covering k-chain free subsets in Boolean lattices
• Subsets of posets minimising the number of chains
• On some extremal and probabilistic questions for tree posets
• Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
• Set systems containing many maximal chains
• On saturated \(k\)-Sperner systems
• Solution to a problem of Katona on counting cliques of weighted graphs
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Saturating Sperner families
• The number of additive triples in subsets of abelian groups
• Supersaturation in posets and applications involving the container method
• Long symmetric chains in the Boolean lattice
• Structure and supersaturation for intersecting families
• Supersaturation, counting, and randomness in forbidden subposet problems
• Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains

This page was built for publication: Supersaturation in the Boolean lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262057)