Tópicos Especiais em Algoritmos e Combinatória - 2020/2


Programa de Engenharia de Sistemas e Computação


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


Professor: Fábio Botler

Sala virtual: Google Meet

Ementa preliminar:

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


Horário das aulas:

Início: 08/07/2020
4a. e 6a., 15-17h


Listas

As listas deverão ser entregues até a data determinada, podem ser enviadas por email, porém é preferível que seja entregue, ainda que posteriormente, também a versão em papel. Sugerimos digitar a lista. Veja, por exemplo, o Overleaf.

Lista 1: Entregar até 19/08/2020
Lista 2: Entregar até 30/09/2020 solução da questão 1


Programação esperada:

Julho
8 Introdução, exemplos, definições básicas - quadro
10 Teorema de Ramsey - quadro
15 Teorema de Schur - quadro
17 Probabilidade e limitantes inferiores para o número de Ramsey - quadro
22 Teorema de Van der Waerden - quadro
24 Teorema de Mantel - quadro
29 Teorema de Turán - quadro
31 Desigualdade de Jensen e subgrafos com grau mínimo próximo da densidade - quadro
Agosto
5 Teorema de Erdos-Stone - quadro - prova organizada
7 Teorema de Erdos-Simonovits - quadro - prova organizada
12 Teorema de Andrasfai-Erdos-Sos, grafos aleatórios, e
grafos com cintura e número cromático arbitrários (Parte 1) - quadro
14 Threshold para a existência de triângulos - quadro - prova organizada
19 Threshold para a existência do K_4 com uma aresta extra - quadro
21 A desigualdade FKG e triâgulos em G(n, p) com p=c/n - quadro
26 A desigualdade de Janson e conexidade em G(n, p) - quadro
28 Conexidade de G(n, p) e pares regulares - quadro
Setembro
2 Lema de Imersão, Lema de Regularidade de Szemerédi - quadro
4 Aplicações do Lema de Szemerédi:
Teorema de Erdos-Stone, e Lema de Remoção de Triângulos - quadro
9 Teorema de Roth, Números de Ramsey-Turán - quadro
11 Números de Ramsey-Turán, Partições e refinamentos - quadro
16 O Lema de Regularidade - quadro
23 - 25Apresentação de trabalho
30 - 02/10Apresentação de trabalho


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.

Ronald L. Graham, Donald E. Knuth, Oren Patashnik
Matemática Concreta - Fundamentos para a Ciência da Computação.
Concrete mathematics : a foundation for computer science.
LTC 1995.

Stasys Jukna
Extremal Combinatorics With Applications in Computer Science
Springer 2011.

Links interessantes

Wikipedia: Mathematical proofs.