Detalhes

Nome da Disciplina: COMBINATÓRIA EXTREMAL I

Carga Horária: 60

Créditos: 4

Disciplina Regular: Sim

Princípios e técnicas básicas em Combinatória; Números extremais, Teorema de Mantel e Teorema de Turán; Números extremais de grafos bipartidos, árvores e caminhos; Supersaturação e estabilidade; Teorema de Erdős-Stone; Teorema de Ramsey e variações dos números de Ramsey; Limitantes para o número de Ramsey e Teoria de Ramsey infinita (básico); Teoria de Ramsey em Grafos, Número de Ramsey de caminhos; Métodos probabilísticos: primeiro momento, alteração, segundo momento; Método da concentração, desigualdade de Chernoff; Número tamanho Ramsey de caminhos; Grafos aleatórios: Números extremais de ciclos pares, Conexidade de G(n,p), Funções limiares, Subgrafos pequenos, Teoria de Ramsey em G(n,p); O Método da Regularidade e aplicações.

N. Alon, J. Spencer, The Probabilistic Method, Wiley, 2008.
B. Bollobás, Modern Graph Theory, Springer, 2002.
F. Botler, M. Collares, T. Martins, W. Mendonça, R. Morris, G. Mota, Combinatória, IMPA, 2021.
A. Frieze, M. Karoński, Introduction to random graphs, Cambridge University Press, 2016.
S. Jukna, Extremal Combinatorics With Applications in Computer Science, Springer 2011.