THE METHOD OF HYPERGRAPH CONTAINERS

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.

• Publication year

  2018

• Venue

  International Congress of Mathematicans

• Publication date

  2018-01-14

• Fields of study

  Mathematics

• Identifiers
  DOI 10.1142/9789813272880_0172arXiv 1801.04584
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The number of Bh ‐sets of a given cardinality

  2018influential reference
• On the number of union-free families

  2017cited by this paper
• Supersaturated sparse graphs and hypergraphs

  2017influential reference
• On the number of points in general position in the plane

  2017influential reference
• Further applications of the Container Method

  2016influential reference
• Applications of graph containers in the Boolean lattice

  2016cited by this paper
• An exponential-type upper bound for Folkman numbers

  2016influential reference
• Online containers for hypergraphs, with applications to linear equations

  2016cited by this paper
• The number of B3-sets of a given cardinality

  2016cited by this paper
• Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs

  2016cited by this paper
• A Note on Induced Ramsey Numbers

  2016cited by this paper
• The number of subsets of integers with no $k$-term arithmetic progression

  2016cited by this paper
• Multicolour containers and the entropy of decorated graph limits

  2016cited by this paper
• On the number of union-free families

  2016cited by this paper
• Extremal results for random discrete structures

  2016influential reference
• Structure and enumeration theorems for hereditary properties in finite relational languages

  2016cited by this paper
• THE TYPICAL STRUCTURE OF MAXIMAL TRIANGLE-FREE GRAPHS

  2015cited by this paper
• DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS

  2015cited by this paper
• A sharp threshold for van der Waerden's theorem in random subsets

  2015influential reference
• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity

  2015cited by this paper
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers

  2015cited by this paper
• University of Birmingham On the structure of oriented graphs and digraphs with forbidden tournaments or cycles

  2015cited by this paper
• Turán's Theorem for random graphs

  2015cited by this paper
• On the Number of Bh-Sets

  2015influential reference
• The typical structure of graphs with no large cliques

  2014cited by this paper
• Maximum‐size antichains in random set‐systems

  2014cited by this paper
• The number of the maximal triangle‐free graphs

  2014influential reference
• Counting independent sets in graphs

  2014cited by this paper
• Sharp bound on the number of maximal sum-free subsets of integers

  2014cited by this paper
• A random version of Sperner's theorem

  2014cited by this paper
• The Typical Structure of Intersecting Families

  2014cited by this paper
• A Short Proof of the Random Ramsey Theorem

  2014influential reference
• Combinatorial theorems relative to a random set

  2014cited by this paper
• Simple Containers for Simple Hypergraphs

  2014cited by this paper
• Hereditary and Monotone Properties of Graphs

  2013cited by this paper
• Erd˝ os and Arithmetic Progressions

  2013influential reference
• On the KŁR conjecture in random graphs

  2013cited by this paper
• Extremal Results in Random Graphs

  2013cited by this paper
• Erdős and Arithmetic Progressions

  2013cited by this paper
• The typical structure of sparse $K_{r+1}$-free graphs

  2013cited by this paper
• On the Number of Graphs Without Large Cliques

  2013cited by this paper
• Counting sets with small sumset and applications

  2013cited by this paper
• The number of $C_{2l}$-free graphs

  2013cited by this paper
• Hypergraph containers

  2012influential reference
• A refinement of the Cameron–Erdős conjecture

  2012cited by this paper
• Mantel's theorem for random graphs

  2012cited by this paper
• List Colourings of Regular Hypergraphs

  2012cited by this paper
• Independent sets in hypergraphs

  2012influential reference
• Counting sum-free sets in abelian groups

  2012influential reference
• The number of Ks,t‐free graphs

  2011cited by this paper
• Random sum-free subsets of abelian groups

  2011cited by this paper
• The number of Km,m-free graphs

  2011influential reference
• A Non-linear Lower Bound for Planar Epsilon-nets

  2010cited by this paper
• Ramsey properties of random discrete structures

  2010cited by this paper
• Ramsey properties of random discrete structures

  2010influential reference
• Combinatorial theorems in sparse random sets

  2010cited by this paper
• Szemerédi's Regularity Lemma for Matrices and Sparse Graphs

  2010cited by this paper
• The typical structure of graphs without given excluded subgraphs

  2009cited by this paper
• The Cameron-Erdös conjecture

  2008influential reference
• The Cameron-Erd˝ os conjecture

  2008cited by this paper
• A probabilistic counting lemma for complete graphs

  2007cited by this paper
• Influence of cultivation temperature on the ligninolytic activity of selected fungal strains

  2006influential reference
• Systems of Containers and Enumeration Problems

  2005cited by this paper
• The number of graphs without forbidden subgraphs

  2004cited by this paper
• ASYMPTOTIC ENUMERATION OF Kn-FREE GRAPHS

  2004influential reference
• Counting sumsets and sum-free sets modulo a prime

  2004cited by this paper
• For Which Densities are Random Triangle-Free Graphs Almost Surely Bipartite?

  2003cited by this paper
• A sharp threshold for random graphs with a monochromatic triangle in every edge coloring

  2003cited by this paper
• Extremal Uncrowded Hypergraphs

  2003cited by this paper
• SOME RECENT RESULTS ON EXTREMAL PROBLEMS IN GRAPH THEORY (Results)

  2002cited by this paper
• О числе независимых множеств в расширителях@@@On the number of independent sets in extenders

  2001influential reference
• A Density Version of the Hales-Jewett Theorem

  2001cited by this paper
• On the number of independent sets in expanders

  2001cited by this paper
• On triangle-free random graphs

  2000influential reference
• Degrees and choice numbers

  2000cited by this paper
• Sharp thresholds of graph properties, and the -sat problem

  1999cited by this paper
• A Sharp Threshold for k-Colorability

  1999cited by this paper
• An Extremal Problem For Random Graphs And The Number Of Graphs With Large Even-Girth

  1998cited by this paper
• Szemerédi's regularity lemma for sparse graphs

  1997influential reference
• OnK4-free subgraphs of random graphs

  1997cited by this paper
• ON K4-FREE SUBGRAPHS OF RANDOM GRAPHS

  1997cited by this paper
• Rado Partition Theorem for Random Subsets of Integers

  1997cited by this paper
• On Schur Properties of Random Subsets of Integers

  1996influential reference
• Arithmetic progressions of length three in subsets of a random set

  1996cited by this paper
• Projections of Bodies and Hereditary Properties of Hypergraphs

  1995cited by this paper
• On Uncrowded Hypergraphs

  1995cited by this paper
• Turán's Extremal Problem In Random Graphs: Forbidding Odd Cycles

  1995cited by this paper
• Turán's Extremal Problem in Random Graphs: Forbidding Even Cycles

  1995cited by this paper
• Threshold functions for Ramsey properties

  1995influential reference
• Random Graphs with Monochromatic Triangles in Every Edge Coloring

  1994cited by this paper
• Restricted colorings of graphs

  1993influential reference
• On the Number of Databases and Closure Operations

  1991cited by this paper
• Maximal Independent Subsets in Steiner Systems and in Planar Sets

  1991influential reference
• Independent sets in regular graphs and sum-free subsets of finite groups

  1991influential reference
• A density version of the Hales-Jewett theorem

  1991cited by this paper
• On the Number of Sets of Integers With Various Properties

  1990cited by this paper
• ɛ-nets and simplex range queries

  1987cited by this paper
• Large triangle-free subgraphs in graphs withoutK4

  1986influential reference
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent

  1986cited by this paper
• Some Old and New Problems in Combinatorial Geometry

  1984cited by this paper

• Some recent results in Ramsey theory

  2026cites this paper
• Counting Independent Sets in Percolated Graphs via the Ising Model

  2025cites this paper
• Asymptotic enumeration via graph containers and entropy

  2025cites this paper
• On the number of sum-free subsets of the square grid

  2025cites this paper
• (Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence

  2025cites this paper
• On the evolution of structure in triangle-free graphs

  2025cites this paper
• Polynomial Property Testing

  2025cites this paper
• On an extremal problem for locally sparse multigraphs

  2024cites this paper
• Lower tails for triangles inside the critical window

  2024cites this paper
• A Refined Graph Container Lemma and Applications to the Hard‐Core Model on Bipartite Expanders

  2024cites this paper
• Counting sparse induced subgraphs in locally dense graphs

  2024cites this paper
• A new bound for A(A + A) for large sets

  2024cites this paper
• Rational Exponents for Cliques

  2024cites this paper
• Short proof of the hypergraph container theorem

  2024cites this paper
• Towards an optimal hypergraph container lemma

  2024cites this paper
• Clustering in typical unit-distance avoiding sets

  2024cites this paper
• Tree Posets: Supersaturation, Enumeration, and Randomness

  2024cites this paper
• Counting independent sets in structured graphs

  2024cites this paper
• Enumeration of Intersection Graphs of x-Monotone Curves

  2024cites this paper
• New Graph and Hypergraph Container Lemmas with Applications in Property Testing

  2024cites this paper
• Counting Arcs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {F}}_q^2$$\end{document}Fq2

  2024cites this paper
• Multipartite nearly orthogonal sets over finite fields

  2024cites this paper
• An Approximate Counting Version of the Multidimensional Szemerédi Theorem

  2023cites this paper
• Nearly All 𝑘-SAT Functions Are Unate

  2023cites this paper
• More on rainbow cliques in edge-colored graphs

  2023cites this paper
• Ramsey numbers and the Zarankiewicz problem

  2023cites this paper
• Two-round Ramsey games on random graphs

  2023cites this paper
• Random Tur\'an theorem for expansions of spanning subgraphs of tight trees

  2023influential citation
• Turán theorems for even cycles in random hypergraph

  2023influential citation
• Nearly all k-SAT functions are unate

  2022cites this paper
• On Higher Dimensional Point Sets in General Position

  2022cites this paper
• Nearly all $k$-SAT functions are unate

  2022cites this paper
• Counting numerical semigroups by Frobenius number, multiplicity, and depth

  2022cites this paper
• Algorithmic Applications of Hypergraph and Partition Containers

  2022influential citation
• Counting arcs in $\mathbb F_q^2$

  2022cites this paper
• What does a typical metric space look like?

  2021cites this paper
• On an extremal problem for locally sparse multigraphs

  2021influential citation
• Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]‐decorated containers

  2021cites this paper
• Enumerating k-SAT functions

  2021cites this paper
• Near Optimal Distributed Learning of Halfspaces with Two Parties

  2021cites this paper
• Paley-like graphs for the Ramsey number $r(C_4,K_t)$

  2021cites this paper
• New results on some Erdős-Ko-Rado-type problems

  2021cites this paper
• Probabilistic hypergraph containers

  2021influential citation
• Triangle-Free Subgraphs of Hypergraphs

  2021influential citation
• Extremal problems in hypergraph colourings

  2020cites this paper
• At most $3.55^n$ stable matchings

  2020cites this paper
• Ramsey goodness of trees in random graphs

  2020cites this paper
• A new bound for $A(A + A)$ for large sets

  2020cites this paper
• On the smallest singular value of symmetric random matrices

  2020cites this paper
• Induced subgraphs of bounded treewidth and the container method

  2020cites this paper
• At most 4.47 n stable matchings.

  2020cites this paper
• Random Van der Waerden Theorem

  2020cites this paper
• Triangle-Free Subgraphs of Hypergraphs

  2020cites this paper
• INDEPENDENT SETS IN HYPERGRAPHS AND RAMSEY OF GRAPHS

  2019cites this paper
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems

  2019cites this paper
• The Typical Structure of Sets With Small Sumset

  2019cites this paper
• An efficient container lemma

  2019cites this paper
• Ramsey Goodness of Paths in Random Graphs

  2019cites this paper
• Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility

  2019cites this paper
• Four‐term progression free sets with three‐term progressions in all large subsets

  2019cites this paper
• On the singularity of random symmetric matrices

  2019cites this paper
• Multicolor chain avoidance in the Boolean lattice

  2019cites this paper
• University of Birmingham Independent sets in hypergraphs and Ramsey properties of graphs and the integers

  2019cites this paper
• Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties

  2018cites this paper
• Groups with few maximal sum-free sets

  2018cites this paper
• Independent sets in algebraic hypergraphs

  2018cites this paper
• A short nonalgorithmic proof of the containers theorem for hypergraphs

  2018cites this paper
• On the number of sets with a given doubling constant

  2018cites this paper
• An asymmetric container lemma and the structure of graphs with no induced $4$-cycle

  2018influential citation
• A new lower bound on Hadwiger-Debrunner numbers in the plane

  2018cites this paper
• The number of independent sets in an irregular graph

  2018cites this paper
• The Typical Structure of Gallai Colorings and Their Extremal Graphs

  2018cites this paper
• A generalized Turán problem in random graphs

  2018cites this paper
• Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers

  2017cites this paper
• European Journal of Combinatorics

  year unknowncites this paper
• Combinatorial theorems relative to sparse sets

  year unknowncites this paper