Projects per year
Abstract
We apply the graph container method to prove a number of counting results for the Boolean lattice inline image. In particular, we:
Give a partial answer to a question of Sapozhenko estimating the number of t error correcting codes in inline image, 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 inline image and give a two-coloured analogue;
Give an asymptotic formula for the number of (p, q)-tilted Sperner families in inline image;
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
Give a partial answer to a question of Sapozhenko estimating the number of t error correcting codes in inline image, 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 inline image and give a two-coloured analogue;
Give an asymptotic formula for the number of (p, q)-tilted Sperner families in inline image;
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
| Original language | English |
|---|---|
| Pages (from-to) | 845-872 |
| Number of pages | 28 |
| Journal | Random Structures and Algorithms |
| Volume | 49 |
| Issue number | 4 |
| Early online date | 22 Jul 2016 |
| DOIs | |
| Publication status | Published - Dec 2016 |
Fingerprint
Dive into the research topics of 'Applications of graph containers in the Boolean lattice'. Together they form a unique fingerprint.Projects
- 1 Finished
-
EPSRC Fellowship: Dr Andrew Treglown - Independence in groups, graphs and the integers
Engineering & Physical Science Research Council
1/06/15 → 31/05/18
Project: Research Councils