Combinatorics II
1- Ramsey theory: the theorems of van der Waerden, Rado and Hales-Jewett; Ramsey numbers of graphs with bounded degrees; bounds for diagonal, off-diagonal and hypergraph Ramsey numbers; recent progress in Ramsey theory for graphs.
2. The probabilistic method: the giant component, the chromatic number of G(n,p), the local lemma, the Rodl nibble, random graph processes, concentration inequalities, dependent random choice.
3. Algebraic and topological methods: the polynomial method (the combinatorial nullstellensatz, the Kakeya conjecture in finite fields); the modular Frankl-Wilson inequality and applications (disproof of Borsuk’s conjecture, constructive lower bounds for Ramsey numbers, the chromatic number of the plane); applications of the Borsuk-Ulam theorem.
4. Additive combinatorics: sum-sets (theorems of Cauchy-Davenport and Freiman), the Balog-Szemerédi-Gowers theorem, sum-free sets (Cameron-Erdos conjecture), Roth’s theorem, discussion of Szemerédi’s theorem.
5. The method of containers for hypergraphs: extremal and Ramsey-type problems in G(n,p), counting and typical structure of H-free graphs, Folkman numbers, induced Ramsey numbers, constructions in discrete geometry.
[2] L. Babai and P. Frankl. – Linear algebra methods in combinatorics, Departament of Computer Science, University of Chicago, versão preliminar, 1991.
[3] B. Bollogás. – Modern Graph Theory (Graduate Texts in Mathematics), Springer-Verlag, New York, 1998.
[4] J. Matousek. – Thirty-three miniatures (mathematical and algorithmic applications of linear algebra), AMS, 2010.
[5] T. Tao and V. Vu. – Additive combinatorics, Cambridge Studies in Advanced Mathematics, CUP, 2006.
