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.

Referências:
[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.

* Ementa básica. O professor tem autonomia para efetuar qualquer alteração.