The method of hypergraph containers
From MaRDI portal
Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Abstract: In this survey we describe a recently-developed technique for bounding the number (and controlling the typical structure) of finite objects with forbidden substructures. This technique exploits a subtle clustering phenomenon exhibited by the independent sets of uniform hypergraphs whose edges are sufficiently evenly distributed; more precisely, it provides a relatively small family of 'containers' for the independent sets, each of which contains few edges. We attempt to convey to the reader a general high-level overview of the method, focusing on a small number of illustrative applications in areas such as extremal graph theory, Ramsey theory, additive combinatorics, and discrete geometry, and avoiding technical details as much as possible.
Recommendations
Cited in
(40)- Groups with few maximal sum-free sets
- On the singularity of random symmetric matrices
- Triangle-free subgraphs of hypergraphs
- Independent sets in algebraic hypergraphs
- Multicolor chain avoidance in the Boolean lattice
- On the number of sets with a given doubling constant
- Online containers for hypergraphs, with applications to linear equations
- A short nonalgorithmic proof of the containers theorem for hypergraphs
- Hypergraph containers
- Towards the Kohayakawa-Kreuter conjecture on asymmetric Ramsey properties
- Extremal problems in hypergraph colourings
- An efficient container lemma
- Ramsey goodness of clique versus paths in random graphs
- The Typical Structure of Gallai Colorings and Their Extremal Graphs
- Simple containers for simple hypergraphs
- Stochastic Algorithms: Foundations and Applications
- On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
- On the smallest singular value of symmetric random matrices
- Counting configuration-free sets in groups
- Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]‐decorated containers
- On an extremal problem for locally sparse multigraphs
- Counting numerical semigroups by Frobenius number, multiplicity, and depth
- An asymmetric container lemma and the structure of graphs with no induced 4-cycle
- Turán theorems for even cycles in random hypergraph
- Probabilistic hypergraph containers
- Ramsey numbers and the Zarankiewicz problem
- Counting arcs in \(\mathbb{F}_q^2\)
- A new bound for A(A + A) for large sets
- More on rainbow cliques in edge-colored graphs
- Counting independent sets in percolated graphs via the Ising model
- A refined graph container lemma and applications to the hard-core model on bipartite expanders
- Counting independent sets in structured graphs
- Short proof of the hypergraph container theorem
- On the evolution of structure in triangle-free graphs
- Enumeration of intersection graphs of x-monotone curves
- Rational exponents for cliques
- Counting sparse induced subgraphs in locally dense graphs
- Random Turán theorem for expansions of spanning subgraphs of tight trees
- The codegree Turán density of tight cycles
- Multipartite nearly orthogonal sets over finite fields
This page was built for publication: The method of hypergraph containers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5122147)
