Combinatória I

  1. Teoria dos grafos básica: Árvores, número cromático (teorema de Brooks), grafos planares (fórmula de Euler, número de arestas, teorema das cinco cores), ciclos hamiltonianos (teorema de Dirac), teorema do casamento de Hall.

    2. Teoria extremal dos grafos: Teorema de Turán, teorema de Kovári-Sós-Turán, números extremais de árvores, teorema de Erdos-Stone, estabilidade e supersaturação.

    3. Teoria extremal dos conjuntos: Teoremas de Sperner, Erdos-Ko-Rado e Kruskal-Katona.

    4. Teoria de Ramsey: Teorema de Ramsey (versões finitas e infinitas para grafos e hipergrafos), teorema de Schur, teoria de Ramsey para grafos (por exemplo, cliques contra árvores).

    5. Grafos aleatórios e o método probabilístico: Propriedades básicas do grafo aleatório de Erdos-Rényi (por exemplo, limiares para existência de subgrafos, conexidade, discussão a respeito da componente gigante) e aplicações (existência de grafos com cintura e número cromático grandes, cotas inferiores para o número extremal de ciclos, cotas inferiores para os números de Ramsey). As desigualdades de FKG e Janson, colorindo hipergrafos com duas
    cores.

    6. Lema da regularidade de Szemerédi e aplicações: Por exemplo, teorema de Erdos-Stone, lema da remoção de triângulos, teorema de Roth, números de Ramsey-Turán.

 

Referências:
BOLLOBÁS, B. – Modern Graph Theory, New York : Springer, c1998.
ALON, N., SPENCER, JOEL H. – The Probabilistic Method, 3rd ed. Hoboken, N.J.: Wiley, c2008.