Programa de Mestrado 2012: Extremal and Probabilistic Combinatorics

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.

Vídeos

Extremal and Probabilistic Combinatorics

Robert Morris

Aula 01 - 11.01.2012 - DOWNLOAD: parte1parte2
Aula 02 - 13.01.2012 - DOWNLOAD: parte1parte2
Aula 03 - 18.01.2012 - DOWNLOAD: parte1parte2
Aula 04 - 23.01.2012 - DOWNLOAD: parte1parte2
Aula 05 - 25.01.2012 - DOWNLOAD: parte1parte2
Aula 06 - 27.01.2012 - DOWNLOAD: parte1parte2
Aula 07 - 01.02.2012 - DOWNLOAD: parte1parte2
Aula 08 - 03.02.2012 - DOWNLOAD: parte1parte2
Aula 09 - 06.02.2012 - DOWNLOAD: parte1parte2
Aula 10 - 08.02.2012 - DOWNLOAD: parte1parte2
Aula 11 - 13.02.2012 - DOWNLOAD: video
Aula 12 - 15.02.2012 - DOWNLOAD: parte1parte2
Aula 13 - 24.02.2012 - DOWNLOAD: parte1parte2
Aula 14 - 27.02.2012 - DOWNLOAD: parte1parte2 - FINAL

________________________________________________________________________________

AVISO: Devido ao alto consumo de conexões, as transferências da página de vídeo estão limitadas
a 1 download ativo por pessoa. Caso deseje baixar mais de 1 vídeo, primeiro aguarde o
download anterior ser concluído.

________________________________________________________________________________