Applications of graph containers in the Boolean lattice1. Issue 4 (22nd July 2016)

• Record Type: Journal Article
• Authors: Balogh, József; Treglown, Andrew; Wagner, Adam Zsolt
• Is Part Of: Random structures & algorithms. Volume 49:Issue 4(2016)
• Page Start: 845
• Page End: 872
• Publication Date: 2016-07-22
• Subjects: container method -- Boolean lattice -- Sperner families -- error correcting codes -- enumeration problems; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20666
• Languages: English
• ISSNs: 1042-9832

Abstract

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. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 845–872, 2016