Applications of graph containers in the Boolean lattice

József Balogh, Andrew Treglown, Adam Zsolt Wagner

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)845-872
Number of pages28
JournalRandom Structures and Algorithms
Volume49
Issue number4
DOIs
StatePublished - Dec 1 2016

Keywords

  • Boolean lattice
  • Sperner families
  • container method
  • enumeration problems
  • error correcting codes

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Applications of graph containers in the Boolean lattice'. Together they form a unique fingerprint.

  • Cite this