Container method: Difference between revisions

Revision as of 00:38, 12 February 2022

Revision as of 13:49, 14 February 2022

Line 5:

{{AfC topic|stem}}

The method of (hypergraph) containers is a powerful tool that can help characterize the typical structure and/or answer extremal questions about families of discrete objects with a prescribed set of local constraints. Such questions arise naturally in [[extremal graph theory]], [[additive combinatorics]], [[discrete geometry]], [[coding theory]], and [[Ramsey theory]]; they include some of the most classical problems in the associated fields.

These problems can be expressed as questions of the following form: given a [[hypergraph]] {{math|''H''}} on finite vertex set {{math|''V''}} with edge set {{math|''E''}} (i.e. a collection of subsets of {{math|''V''}} with some size constraints), what can we say about the [[independent set (graph theory)|independent sets]] of {{math|''H''}} (i.e. those subsets of {{math|''V''}} that contain no element of {{math|''E''}})? The hypergraph container lemma provides a method for tackling such questions.

Line 13:

One of the foundational problems of extremal graph theory, dating to work of Mantel in 1907 and [[Turán's theorem|Turán]] from the 1940s, asks to characterize those graphs that do not contain a copy of some fixed [[forbidden subgraph problem|forbidden]] {{math|''H''}} as a subgraph. In a different ___domain, one of the motivating questions in additive combinatorics is understanding how large a set of integers can be without containing a {{math|''k''}}-term [[arithmetic progression]], with upper bounds on this size given by [[Roth's theorem on arithmetic progressions|Roth]] (<math>k=3</math>) and [[Szemerédi's theorem|Szemerédi]] (general {{math|''k''}}).

The method of containers (in graphs) was initially pioneered by Kleitman and Winston in 1980, who bounded the number of lattices.<ref>{{cite journal |last1=Kleitman |first1= Daniel |last2=Winston |first2=Kenneth |title=The asymptotic number of lattices |journal=Annals of Discrete Mathematics |date=1980 |volume=6 |pages=243–249|doi= 10.1016/S0167-5060(08)70708-8 |isbn= 9780444860484 }}</ref> and graphs without 4-cycles<ref>{{cite journal |last1=Kleitman |first1= Daniel |last2=Winston |first2=Kenneth |title=On the number of graphs without 4-cycles |journal=Discrete Mathematics |date=1982 |volume=31 |issue= 2 |pages=167–172|doi= 10.1016/0012-365X(82)90204-7 }}</ref>. Container-style lemmas were independently developed by multiple mathematicians in different contexts, notably including Sapozhenko, who initially used this approach in 2002-2003 to enumerate independent sets in [[regular graphs]]<ref>{{cite journal |last1=Sapozhenko |first1=Alexander |title=The Cameron-Erdos conjecture |journal=Doklady Akademii Nauk |date=2003 |volume=393 |pages=749–752}}</ref> and, sum-free sets in abelian groups<ref>{{cite journal |last1=Sapozhenko |first1=Alexander |title=Asymptotics for the number of sum-free sets in Abelian groups |journal=Doklady Akademii Nauk |date=2002 |volume=383 |pages=454–458}}</ref>, and study a variety of other enumeration problems<ref>{{Citation|last=Sapozhenko|first=Alexander|title=Systems of Containers and Enumeration Problems|date=2005|url=http://dx.doi.org/10.1007/11571155_1|work=Stochastic Algorithms: Foundations and Applications|pages=1–13|place=Berlin, Heidelberg|publisher=Springer Berlin Heidelberg|isbn=978-3-540-29498-6|access-date=2022-02-13}}</ref>.

A generalization of these ideas to a hypergraph container lemma was devised independently by Saxton and Thomason<ref>{{cite journal |last1=Saxton |first1=David |last2=Thomason |first2=Andrew |title=Hypergraph containers |journal=Inventiones Mathematicae |date=2015 |volume=201 |issue=3 |pages=925–992|doi=10.1007/s00222-014-0562-8 |arxiv=1204.6595 |bibcode=2015InMat.201..925S |s2cid=119253715 }}</ref> and Balogh, Morris, and Samotij<ref>{{cite journal |last1=Balogh |first1= József |last2=Morris |first2=Robert|last3=Samotij|first3=Wojciech |title=Independent sets in hypergraphs |journal=Journal of the American Mathematical Society |date=2015 |volume=28 |issue= 3 |pages=669–709|doi= 10.1090/S0894-0347-2014-00816-X |s2cid= 15244650 }}</ref> in 2015, inspired by a variety of previous related work.

Line 36:

The hypergraph container lemma achieves the above container decomposition in two pieces. It constructs a deterministic function {{math|''f''}}. Then, it provides an algorithm that extracts from each independent set {{math|''I''}} in hypergraph {{math|''H''}}, a relatively small collection of vertices <math>S \subset I</math>, called a ''fingerprint'' with the property that <math> S \subset I \subset S \cup f(S)</math>. Then, the containers are the collection of sets <math>S \cup f(S)</math> that arise in the above process, and the small size of the fingerprints provides good control on the number of such container sets.

==Kleitman-WinstonGraph container algorithm==

We first describe a method for showing strong upper bounds on the number of independent sets in a graph; this exposition adapted from a survey of Samotij about the graph container method.<ref>{{cite journal |last1=Samotij |first1= Wojciech |title=Counting independent sets in graphs |journal=European Journal of Combinatorics |date=2015 |volume=48 |pages=5–18|doi= 10.1016/j.ejc.2015.02.005 |s2cid= 15850625 }}</ref> about the graph container method employed by Kleitman-Winston and Sapozhenko.

===Notation===

Line 45:

* The ''max-degree ordering'' of a vertex subset <math> A \subset V</math> is the ordering of the vertices in {{math|''A''}} by their degree in the [[induced subgraph]] <math>G[A]</math>.

===Kleitman-Winston algorithm===

===Algorithm===

The following algorithm gives a small "fingerprint" for every independent set in a graph and a deterministic function of the fingerprint to construct a not-too-large subset that contains the entire independent set