Tópicos Especiais em Algoritmos e Combinatória (CPS846) - 2019/2


Programa de Engenharia de Sistemas e Computação


Esta é a página preliminar do curso de Combinatória Extremal e Probabilística (CPS846).




Professor: Fábio Botler



Ementa preliminar:

Teoria de Ramsey; Teoria Extremal de Grafos; Grafos Aleatórios; Lema de Regularidade.


Horário das aulas:

Início: 24/06/2019
2a. e 4a., 15-17h

Sala: H-310A

Programação esperada:

Junho
24Introdução, exemplos, definições básicas
26Definições básicas, Teorema de Ramsey Infinito, Teorema de Schur Intinito
Julho
1 - 3Teorema de Ramsey Finito, Teorema de Schur Finito
8 - 10Teorema de Van der Waerden
15 - 17Teorema de Turán
22 - 24Teorema de Erdos-Stone
29 - 31Colóquio Brasileiro de Matemática
Agosto
5 - 7Grafos Aleatórios
12 - 14Mais Grafos Aleatórios
19 - 21Lema de Regularidade de Szemerédi
26 - 28Aplicações do Lema de Szemerédi
Setembro
2 - 4Professor em conferência
9 - 11Mais Aplicações do Lema de Szemerédi

Entregas de trabalhos:

14 de agostoTrabalho 1
11 de setembroTrabalho 2

Bibliografia

Notas

IMBUZEIRO, R.; MORRIS, R.
Extremal and Probabilistic Combinatorics, 2012.

Mota, G. O. Notas, 2011.

ALON, N.; Spencer, J.
The Probabilistic Method, 3rd edition,Wiley, 2008.

BOLLOBÁS, B.
Modern Graph Theory, 2nd edition, Springer, 2002.

FRIEZE, A.; KAROŃSKI, M.
Introduction to random graphs, Cambridge University Press, 2016.

Links interessantes

Wikipedia: Mathematical proofs.