Fundamentos de Combinatória

Informações básicas

Carga horária: 

60h

Ementa: 

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).

 

Bibliografia

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