Curso - 14 aulas.

In this course we will introduce the student to the basic theorems and proof techniques in extremal graph theory and probabilistic combinatorics. We shall emphasize the close links between these two areas, and provide the background material for modern research fields such as additive combinatorics, monotone and hereditary properties, and graph limits. We also discuss some simple but powerful applications of techniques from functional analysis and linear algebra. The course has no prerequisites. Programa: 1. Ramsey Theory: Finite and infinite versions. Erdös' random proof of the lower bound. Van der Waarden's Theorem. Statement of Szemerédi's Theorem. 2. Extremal Graph Theory: The theorems of Turán, Erdös-Stone and Kovari-Sós-Turán. 3. The Erdös-Renyi Random Graph: Graphs with high girth and chromatic number. Extremal number of C2k. 1st and 2nd moment methods. Janson's inequality. The giant component. 4. Analytic and Algebraic Methods: The Kneser graph and the Borsuk-Ulam Theorem. The Frankl-Wilson inequality and Borsuk's Conjecture. 5. The Szemerédi Regularity Lemma: Statement and applications, e.g., proof of Erdös-Stone, Erdös-Frankl-Rödl. Proof of Roth's Theorem via the triangle-removal lemma. 6. Dependent Random Choice: Applications, including the proof of the Balog-Szemerédi-Gowers Theorem.