Abstract
We apply the graph container method to prove a number of counting results for the Boolean lattice P(n). In particular, we: Give a partial answer to a question of Sapozhenko estimating the number of t error correcting codes in P(n), and we also give an upper bound on the number of transportation codes; Provide an alternative proof of Kleitman's theorem on the number of antichains in P(n) and give a two-coloured analogue; Give an asymptotic formula for the number of (p, q)-tilted Sperner families in P(n) Prove a random version of Katona's t-intersection theorem. In each case, to apply the container method, we first prove corresponding supersaturation results. We also give a construction which disproves two conjectures of Ilinca and Kahn on maximal independent sets and antichains in the Boolean lattice. A number of open questions are also given.
Original language | English (US) |
---|---|
Pages (from-to) | 845-872 |
Number of pages | 28 |
Journal | Random Structures and Algorithms |
Volume | 49 |
Issue number | 4 |
DOIs | |
State | Published - Dec 1 2016 |
Keywords
- Boolean lattice
- Sperner families
- container method
- enumeration problems
- error correcting codes
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics