Combinatória Extremal e Probabilística - Avançada 2023/3 - CPS744


Programa de Engenharia de Sistemas e Computação


Professor: Fábio Botler

Sala: H-304B

Ementa preliminar:

Teoria Extremal dos Conjuntos; Teoria Extremal dos Grafos; Teoria de Ramsey; Método Probabilístico; Método da Regularidade; Método dos Contêiners.


Horário das aulas:

Início: 25/09/2023
3a. e 5a., 10-12h

Programação esperada:

Junho
26 Anticadeias e Sistemas de Bollobás
28 Famílias intersectantes
Outubro
3 - 5 Álgebra Linear e famílias intersectantes
10 Famílias intersectantes
12 Feriado: Nossa senhora aparecida
17 Teorema de Erdos e Stone
19 Estabilidade
24 Turán em Hipergrafos
26 Supersaturação para hipergrafos
31 Teorema de Andrásfai, Erdos e Sós
Novembro
2 Feriado: Finados
7 Limiares cromáticos e Números extremais de ciclos pares
9 Construções de grafos sem C4
14 Teoria de Ramsey aditiva
16 Teorema de Van der Waerden
21 - 23 Número de Ramsey para grafos
28 - 30 Não haverá aula
Dezembro
5 Números de Ramsey para hipergrafos
7 - 12 Lema Local de Lovász
14 Desigualdades de Janson
19 Escolha Aleatória Dependente


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