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


Programa de Engenharia de Sistemas e Computação


Professor: Fábio Botler

Monitoria:

Amanda e Bruno
Grupo de Telegram

Sala: H-310A

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: 28/06/2022
3a. e 5a., 15-17h


Listas

Lista 1: Entregar até 02/08/2022
Lista 2: Entregar até 23/08/2022
Lista 3: Entregar até 13/09/2022


Avaliação

Entregar até 20/09/2022


Programação esperada:

Junho
28 Princípios e técnicas básicas em Combinatória
30 Números extremais, Teorema de Mantel e Teorema de Turán
Julho
5 Números Extremais de grafos bipartidos
7 Números extremais de árvores
12 Números extremais de caminhos
Supersaturação e estabilidade
14 Supersaturação e estabilidade
Teorema de Erdős-Stone
19 Teorema de Ramsey
Variações dos números de Ramsey
21 Um limitante inferior para o número de Ramsey
Um pouco de Teoria de Ramsey infinita.
Teoria de Ramsey em Grafos
26 Número de Ramsey do Pk
28 Espaços de probabilidade
Método probabilístico
Eventos independentes
Agosto
2-5 Não haverá aula
9 Método do primeiro momento
11 Método da alteração
Desigualdade de Markov
16 Método do segundo momento
Desigualdade de Chebychev
18 Não haverá aula
23 Método da concentração, desigualdade de Chernoff
25 Número tamanho Ramsey de caminhos
Grafos aleatórios
30 Números extremais de ciclos pares
Conexidade de G(n,p)
Setembro
1 Funções limiares
Subgrafos pequenos
Teoria de Ramsey em G(n,p)
6 O Método da Regularidade
8 Teorema de Erdős-Stone, Teorema de Roth
13-15 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.
Últimas edições deste curso

2021 2020 2019