Combinatória Extremal e Probabilística - 2021/2 - COS743


Programa de Engenharia de Sistemas e Computação


Professor: Fábio Botler

Monitoria:

João e Wanderson
Grupo de Telegram

Sala virtual: Google Meet

Ementa preliminar:

Teoria Extremal de Grafos; Teoria de Ramsey; Métodos Probabilísticos; Grafos Aleatórios; Lema de Regularidade.


Horário das aulas:

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


Listas

Lista 1: Entregar até 03/09/2021
Lista 2: Entregar até 24/09/2021
Lista 3: Entregar até 22/10/2021


Avaliação

Entregar até 05/11/2021


Programação esperada:

Agosto
11 - Quadro Princípios e técnicas básicas em Combinatória
13 - Quadro Números extremais, Teorema de Mantel e Teorema de Turán
18 - Quadro Números Extremais de grafos bipartidos
20 - Quadro Números extremais de árvores
25 - Quadro Números extremais de caminhos
Supersaturação e estabilidade
27 - Quadro Supersaturação e estabilidade
Teorema de Erdős-Stone
Setembro
1 - Quadro Teorema de Ramsey
Variações dos números de Ramsey
3 - Quadro Um limitante inferior para o número de Ramsey
Um pouco de Teoria de Ramsey infinita.
8 - Quadro Teoria de Ramsey em Grafos
10 - Quadro Número de Ramsey do Pk
15 O número extremal do C5
17 - Quadro O problema do final feliz, espaços de probabilidade
22 - Quadro Método probabilístico
Eventos independentes
24 - Quadro Método do primeiro momento
29 - Quadro Método do primeiro momento
Outubro
1 - Quadro Método da alteração
Desigualdade de Markov
6 - Quadro Método do segundo momento
Desigualdade de Chebychev
8 - Quadro Método da concentração, desigualdade de Chernoff
13 - Quadro Número tamanho Ramsey de caminhos
13 - Quadro Grafos aleatórios
15 - Quadro Números extremais de ciclos pares
Conexidade de G(n,p)
20 - Quadro Funções limiares
Subgrafos pequenos
Teoria de Ramsey em G(n,p)
22 - Quadro O Método da Regularidade
27 - Quadro Teorema de Erdős-Stone, Teorema de Roth
29 Não haverá aula.
Novembro
3-5 Semana de prova


Bibliografia

Botler, Collares, Martins, Mendonça, Morris, Mota
Combinatória, 2021.

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.