Programa de Mestrado: Extremal and Probabilistic Combinatorics - Aula 05 - Parte 01

Описание: Programa de Mestrado: Extremal and Probabilistic Combinatorics
Aula 05 - Parte 01

Professor: Robert Morris

Página do Programa: http://www.impa.br

Download dos Vídeos: http://video.impa.br/index.php?page=p...

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.

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.

IMPA - Instituto de Matemática Pura e Aplicada ©
http://www.impa.br | http://video.impa.br  
 
Os direitos sobre todo o material deste canal pertencem ao Instituto de Matemática Pura e Aplicada, sendo vedada a utilização total ou parcial do conteúdo sem autorização prévia e por escrito do referido titular, salvo nas hipóteses previstas na legislação vigente.

The rights over all the material in this channel belong to the Instituto de Matemática Pura e Aplicada, and it is forbidden to use all or part of it without prior written authorization from the above mentioned holder, except in the cases prescribed in the current legislation.