Extremal Combinatorics and its Methods
Winter 2015-16
|
Main Page References Course Progress Exercises and Aktive Teilnahme |
|
References
While there will not be a single set of course notes, much of the material for the course can be found in the following sources:
For further reading, you are encouraged to consult either of the texts below:
|
||
| Some assorted notes: |
Course Progress
| Lecture | Topics | References | ||
| Lecture 1 | Ramsey theory: graphs, multiple colours, and infinite graphs. | Diestel, Section 9.1 | ||
| Lecture 2 | Infinite Ramsey proof  , andlower bounds: random colouring, alterations improvement. |
Diestel, Section 11.1 Alon-Spencer, Sections 1.1 and 3.1 |
||
| Lecture 3 | Ramsey's theorem for hypergraphs | Jukna, Section 4.10 | ||
| Lecture 4 | Erdős-Rado proof of hypergraph Ramsey Applications: Happy Ending Problem  |
Fox, 18.315, Lecture 2 Fox, MAT307, Lecture 6 |
||
| Lecture 5 | The Canonical Ramsey Theorem  |
Bollobás, Section 6.2 | ||
| Lecture 6 | Two-colourability of hypergraphs/Property B: Initial upper and lower bounds | Alon-Spencer, Section 1.3 | ||
| Lecture 7 | Two-colourability: random greedy colouring | Pluhár paper Cherkashin-Kozik paper |
||
| Lecture 8 | Van der Waerden's theorem  |
Notes on the proof | ||
| Lecture 9 | Ramsey vs Turán problems Turán's theorem |
Bollobás, Section 4.2 (3rd proof of Theorem 8) | ||
| Lecture 10 | Erdős-Stone-Simonovits theorem (statement) Bipartite Turán problems: Kővári-Sós-Turán and K2,2 |
Notes on Turán theory | ||
| Lecture 11 | Szemerédi Regularity Lemma (statement)  |
Alon-Spencer, Section 17.3 | ||
| Lecture 12 | Using Regularity: Key lemmas Proof of Erdős-Stone  |
Diestel, Sections 7.4 and 7.5 | ||
| Lecture 13 | Completion of Erdős-Stone proof Szemerédi's and Roth's Theorems |
|||
| Lecture 14 | Triangle Removal Lemma Sketch of proof of the Regularity Lemma |
Alon-Spencer, Section 17.3 | ||
| Lecture 15 | Regularity Lemma proof: density increment lemma  |
Alon-Spencer, Section 17.3 | ||
| Lecture 16 | Graphs of high girth and high chromatic number | Alon-Spencer, Probabilistic Lens #3 | ||
| Lecture 17 | Intersecting families and the Erdős-Ko-Rado theorem | Alon-Spencer, Probabilistic Lens #1 | ||
| Lecture 18 | The basic linear algebraic method Oddtown and Fisher's inequality |
Babai-Frankl, Section 1.1 and Exercise 4.1.5 | ||
| Lecture 19 | The non-uniform Ray-Chaudhuri-Wilson and Frankl-Wilson theorems | Babai-Frankl, Section 5.4 and Exercise 5.10.1 | ||
| Lecture 20 | Borsuk's conjecture  |
Babai-Frankl, Section 5.6 | ||
| Lecture 21 | The uniform Ray-Chaudhuri-Wilson theorem Sperner's theorem |
Babai-Frankl, Section 5.11 Fox, MAT 307, Lecture 12 |
||
| Lecture 22 | The Bollobás set-pairs inequality and graph saturation | Babai-Frankl, Section 5.1 | ||
| Lecture 23 | Weak saturation and the skew Bollobás set-pairs inequality | Babai-Frankl, Section 5.1 | ||
| Lecture 24 | The Kruskal-Katona theorem: statement  |
Jukna, Section 10.4 | ||
| Lecture 25 | The Kruskal-Katona theorem: proof | Frankl paper | ||
| Lecture 26 | The Borsuk-Ulam theorem Proof of Kneser's conjecture |
Matoušek, Sections 2.1 and 3.3 | ||
| Lecture 27 | The Continuous and Discrete Ham Sandwich Theorems  |
Matoušek, Section 3.1 | ||
| Lecture 28 | Applications of Ham Sandwich: Necklace splitting  and rainbow convex hulls |
Matoušek, Section 3.2 | ||
| Lecture 29 | Sperner's Lemma | Fox, MAT307, Lecture 3 | ||
| Lecture 30 | Independent transversals | |||
| Lecture 31 | Fair division and the Simmons-Su protocol  |
Su paper | ||
| Lecture 32 | The Crossing Number Inequality and Unit Distances |
Exercises and Aktive Teilnahme
| The exercise sheets will be posted on the course website every Wednesday. You will then present and discuss solutions in the exercise classes of the following week. The written solutions should be submitted at the beginning of the Wednesday lecture. There will usually be four exercises per sheet, for which two solutions, of your choice, will be graded for credit. You are welcome to submit all of your solutions, but please clearly indicate which problems you would like to have graded. If time permits, you will also receive some feedback about the other solutions, but all problems should be discussed during the exercise classes. We encourage you to work in pairs on your homework, and submit one set of solutions per pair. On your submission, please clearly indicate the names of both partners, as well as the author of each solution - you can choose how to divide the writing up of the solutions over the course of the semester, but it should be fairly even (see below). We would recommend that you think about all the problems and discuss them together, rather than just dividing them in two and working only on your own problems individually. To gain the Aktive Teilnahme credit for the course, you are required to meet the following criteria:
|