Applications of graph containers in the Boolean lattice

DOI10.1002/RSA.20666MaRDI QIDQ2953701zbMATH OpenOpenAlexFDO

Authors József Balogh, Andrew Treglown, Adam Zsolt Wagner

Publication date 5 January 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.05870, http://pure-oai.bham.ac.uk/ws/files/28561033/BaTrWaFINAL.pdf

zbMATH Keywords

Boolean latticecontainer methodenumeration problemserror correcting codesSperner families

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorics of partially ordered sets (06A07)

Abstract: We apply the graph container method to prove a number of counting results for the Boolean lattice $mathcalP(n)$. In particular, we: (i) Give a partial answer to a question of Sapozhenko estimating the number of $t$ error correcting codes in $mathcalP(n)$, and we also give an upper bound on the number of transportation codes; (ii) Provide an alternative proof of Kleitman's theorem on the number of antichains in $mathcalP(n)$ and give a two-coloured analogue; (iii) Give an asymptotic formula for the number of $(p,q)$-tilted Sperner families in $mathcalP(n)$; (iv) 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.

Recommendations

• Stochastic Algorithms: Foundations and Applications
• Supersaturation in posets and applications involving the container method
• Hypergraph containers
• Independent sets in the middle two layers of Boolean lattice

Cites work

• A new type of coding problem
• A random version of Sperner's theorem
• An extremal problem for two families of sets
• Counting independent sets in graphs
• Counting maximal antichains and independent sets
• Erdős-Ko-Rado in random hypergraphs
• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• scientific article; zbMATH DE number 3230288 (Why is no real title available?)
• scientific article; zbMATH DE number 3065933 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• Intersecting families of discrete structures are typically trivial
• Intersection patterns of convex sets
• Intersection theorems for systems of finite sets
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Kleitman and combinatorics
• Maximal independent sets in bipartite graphs obtained from Boolean lattices
• On a lemma of Littlewood and Offord on the distribution of certain sums
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• On generalized graphs
• On the minimum number of disjoint pairs in a family of finite sets
• On the Nonexistence of Perfect Codes over Finite Fields
• On the number of graphs without 4-cycles
• Optimal codes in the Enomoto-Katona space
• Simple hypergraphs with maximal number of adjacent pairs of edges
• Stochastic Algorithms: Foundations and Applications
• The Asymptotic Number of Lattices
• The number of \(K_{s,t}\)-free graphs
• Tilted Sperner families

Cited in

(13)

• Supersaturation in posets and applications involving the container method
• Arcs in \(\mathbb{F}_q^2\)
• Multicolor chain avoidance in the Boolean lattice
• Independent sets in the middle two layers of Boolean lattice
• Existence thresholds and Ramsey properties of random posets
• Stochastic Algorithms: Foundations and Applications
• Uniform chain decompositions and applications
• On the number of high‐dimensional partitions
• On the number of error correcting codes
• Dedekind's problem in the hypergrid
• Note on the number of antichains in generalizations of the Boolean lattice
• The number of symmetric chain decompositions
• On Dedekind's problem, a sparse version of Sperner's theorem, and antichains of a given size in the Boolean lattice

This page was built for publication: Applications of graph containers in the Boolean lattice

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