SoSe 22: The container method
Tibor Szabo, Leticia Mattos
Additional information / Pre-requisites
Prerequisites: Basic discrete probability and extremal combinatorics (Theorem's of Ramsey, Sperner, Turan, and Erdos and Stone) is necessary; the completion of Discrete Mathematics II is helpful. The time of the course is flexible and will be discussed.
close
Comments
The container method is a powerful enumeration technique developed by Balogh-Morris-Samotij and Saxton-Thomason for the number of independent sets in hypergraphs that satisfy certain regularity conditions. As many problems in Combinatorics can be put in the framework of counting independent sets in certain hypergraphs, this method has numerous applications, and in this course we will focus on them. Some of the most central applications involve studying the threshold for the validity of classical results (like Turán's theorem and Szemeredi's Theorem) in their respective randomized setups. For these we will also give an introduction to random graphs (and more generally, discrete structures), thresholds, and concentration inequalities. If time permits, we will also discuss the entropy method, another powerful counting technique.
The topics we plan to cover include:
- Random graphs (basics, thresholds, concentration inequalities)
- The (hyper) graph container theorem and its variants (Kleitman-Winston, Balogh-Morris-Samotij and Saxton-Thomasen)
- Extremal Combinatorics in random discrete structures (Sum-free sets, Theorems of Sperner, Turán, Ramsey and Szemerédi)
- Counting graphs without forbidden structures (even-cycle-free graphs, maximum triangle-free graphs)
- Entropy: basics, Brégman's theorem, the coin-weighing problem, independent sets in regular bipartite graphs
close
Suggested reading
Bibliography:
Independent sets in hypergraphs: https://arxiv.org/pdf/1204.6530.pdf
Hypergraph containers: https://arxiv.org/abs/1204.6595
Lecture notes of Balogh: https://faculty.math.illinois.edu/~jobal/595_spring2019.html
Lecture notes of Morris: https://www.ime.usp.br/~spschool2016/wp-content/uploads/2016/07/Morris.pdf
Galvin's notes on entropy: https://www3.nd.edu/~dgalvin1/pdf/Kalamazoo_entropy.pdf
An asymmetric container lemma and the structure of graphs with no induced 4-cycles: https://arxiv.org/pdf/1806.03706.pdf
The number of C_{2k}-free graphs: https://arxiv.org/pdf/1309.2927.pdf
Notes of Radhakrishnan on entropy: https://www.tcs.tifr.res.in/~jaikumar/Papers/EntropyAndCounting.pdf
close14 Class schedule
Regular appointments