Fundamentos de Combinatória
Indução. Contagem básica e contagem por inclusão-exclusão, recorrência (números de Catalan) e funções geradoras. Somatórios, números binomiais, notação assintótica e estimativas. Contagem Dupla (Teorema de Sperner + Problema de Littlewood-Offord). Grafos (noções básicas, árvores, ciclos, grafos bipartidos, emparelhamentos, grafos Eulerianos e Hamiltonianos, grafos planares). Introdução à teoria extremal de grafos (Mantel, Turán e número extremal do ciclo de tamanho 4). Introdução à teoria de Ramsey (festa com 6 pessoas, cota superior para números de Ramsey). Introdução à probabilidade discreta e ao método probabilístico (cota inferior para o número de Ramsey).
Informações Básicas
Carga horária
60
Obrigatória:
- Matousek, J; Nesetril, J, Invitation to Discrete Mathematics, Oxford University Press, 2nd edition, 2008.
- Bona, M; A walk Through Combinatorics: An introduction to Enumeration and Graph Theory, WSPC, 4th edition, 2016.
- Graham, R; Knuth, D; Patashnik, O.;Matemática Concreta. Fundamentos para a Ciência da Computação. Livros Técnicos e Científicos, 1995.
Complementar:
- 1. Cameron, P; Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1st edition, 1994.
- 2. Diestel, R.; Graph Theory, Springer, 5th edition, 2017.
- 3. van Lint, J. H; Wilson, R. M; A Course in Combinatorics, Cambridge University Press, 2nd edition, 2001.
- 4. Bollobás, B; Modern Graph Theory; Springer, 1st edition, 1998.
- 5. Bondy, J.A.; Murty, U. S. R; Graph theory; Springer, 2008