Introdução à Combinatória

1. Basic graph theory:  Hamilton  cycles (Dirac’s  theorem),  Hall’s matching  theorem, chromatic  number,  planar  graphs (Euler’s formula, number of edges, the 5-colour theorem).
2.  Extremal graph theory: Turán’s theorem,  the Kovári–Sós–Turán theorem,  extremal numbers of trees, the Erdös–Stone  theorem,  stability  and supersaturation.
3. Extremal set  theory: Sperner’s theorem,  Erdös–Ko–Rado,  Kruskal–Katona.
4.  Ramsey theory: Ramsey’s theorem  (finite and infinite versions for graphs and hypergraphs),  Schur’s theorem,  van der Waerden’s theorem,  graph Ramsey theory.
5. Random graphs and the probabilistic method: basic properties of the Erdös–Rényi random  graph  (e.g.,  thresholds  for subgraph  containment, connectivity,  discussion of the giant component),  and applications  (the existence of graphs with large girth and chromatic number, lower bounds on the extremal number of cycles, lower bounds on Ramsey numbers). The Lovász Local Lemma, the FKG and Janson  inequalities,  dependent random  choice.
6. Szemerédi’s  regularity lemma, and applications: e.g., the  Erdös–Stone  theorem, the triangle  removal lemma, Roth’s theorem,  Ramsey–Turán numbers.

[1] N. Alon and J. H. Spencer. The probabilistic method, 3rd edition, Wiley, New York, 2008.
[2] B. Bollobas, Modern Graph Theory (Graduate Texts in Mathematics), Springer-Verlag, New York, 1998.