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


Programa de Engenharia de Sistemas e Computação


Professor: Fábio Botler

Monitoria:


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: 27/06/2023
3a. e 5a., 13-15h


Listas

Lista 1: Entregar até 28/07/2023
Lista 2: Entregar até 17/08/2023
Lista 3: Entregar até 13/09/2023


Avaliação

Entregar até 14/09/2023


Programação esperada:

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

2022 2021 2020 2019