Last updated 31 January 2010.
Extremal results are not only interesting in their own right, but are also useful in applications because sometimes one can already draw valuable conclusions from the combinatorial basis of a problem with deeper mathematical structure. In that case, the most easily accessible graph-theoretical properties are often the values of the graph parameters, such as the number of edges, diameter, size of the largest set of pairwise non-adjacent vertices, etc. It is therefore useful to understand what other properties are already implied once certain graph parameters lie in certain ranges.
This course will cover the following general areas. Although the topics are organized around central results, there will be particular emphasis on completely understanding the methods used to prove them.
Week 1 | Classical theorems of Turán and Ramsey, with applications. |
Week 2 | Bipartite Turán problems. |
Week 3 | Algebraic constructions of extremal Turán graphs. |
Weeks 4-5 | Statement of Szemerédi's Regularity Lemma, and applications. |
Week 6 | Density increment arguments, and proof of Regularity Lemma. |
Week 7 | Stability arguments. Wed Feb 24 class cancelled. |
Week 8 | Sperner's Theorem and Littlewood-Offord Lemma; results of Bollobás and Erdős-Ko-Rado. Mon Mar 1 class cancelled. |
Spring break | No meetings on Mon Mar 8 or Wed Mar 10. |
Week 9 | Kruskal-Katona and Sauer-Shelah. |
Week 10 | Sunflower Lemma. |
Week 11 | Linear algebra in Extremal Set Theory: Fisher, Oddtown, and Graham-Pollack. |
Week 12 | Frankl-Wilson Theorem and applications. |
Week 13 | Second half of student presentations. |
Week 14 | Lovasz-Kneser Theorem; dependent random choice. |
Week 15 | Median orders; continuous arguments. |
You are visitor number since 10 January 2010. |