Lecturers
Exam
The exam will be on Monday, June 17th, from 09:15 to 12:00, in CM1. Please be on time.
In the Exam Guide you can find everything you need to know about the exam, but don’t hesitate to ask us anything by email or otherwise.
Here is a practice exam.
Problem Sets
- Problem Set 1 — Solutions — Bonus Solutions
- Problem Set 2 — Solutions — Bonus Solutions
- Problem Set 3 — Solutions — Bonus Solutions
- Problem Set 4 — Solutions — Bonus Solutions
- Problem Set 5
- Problem Set 6 — Solutions — Bonus Solutions
- Problem Set 7 — Solutions — Bonus Solutions
- Problem Set 8 — Solutions — Bonus Solutions
- Problem Set 9 — Solutions
- Problem Set 10 — Solutions
- Problem Set 11
(By the way, please let us know if any solution is unclear, or if you find any mistakes.)
Lectures
Lecture 1: Introduction
► Example of a probability proof: Large bipartite subgraphs.
Online: [MatoušekVondrak-Thm3.3.1-p20] — Books: [AlonSpencer-Thm2.2.1-p16]
► Example of a linear algebra proof: Fisher’s Inequality.
Online: [Penna-Thm2-p6] — Books: [Jukna-Sec7.3]
Lecture 2: Various proofs with linear algebra
► Generalized Fisher’s Inequality:
Online: [Penna-Thm2-p6, Matoušek-Ch4] — Books: [Jukna-Sec7.3]
► Equiangular Lines:
Online: [Matoušek-Ch9]
► Graham-Pollak Theorem:
Online: [Penna-Sec2, Matoušek-Ch8] — Books: [Jukna-Sec13.2]
Lecture 3: Various proofs with the probability method
► Ramsey numbers – upper bound (no probability yet):
Online: [Fox-Lecture5-Thm1-p2] — Books: [BondyMurty-Thm12.9-p313]
► Ramsey numbers – first lower bound:
Online: [MatoušekVondrak-Thm2.1.2-p12, Riordan–Thm1.4-p4] — Books: [AlonSpencer-Prop1.1.1-p1, Diestel-Thm11.1.3-p312]
► Ramsey numbers – second lower bound:
Online: [Riordan-Thm1.6-p5] — Books: [AlonSpencer-Thm3.1.1-p27]
► Graph with large girth and large chromatic number:
Online: [MatoušekVondrak-Thm4.2.1-p22, Riordan-Thm1.23-p8] — Books: [AlonSpencer-p41, Diestel-Thm11.2.2-p317]
Lecture 4: Extremal graph theory
► Turán’s theorem with probabilistic proof:
Online: [Gasarch-Thm2.1] — Books: [AlonSpencer-p95]
► Kővári-Sós-Turán theorem, Alon-Krivelevich-Sudakov theorem and dependent random choice:
Online: [FoxSudakov-Lem2.1&Thm3.1] — Books: [AlonSpencer-p303]
Lecture 5: Extremal set theory
► Oddtown theorem: Online: [Penna-Sec1, Matoušek-Ch3] (Here is a nice discussion on the blog of Tim Gowers)
► Eventown theorem: Online: [Pikhurko-Sec4]
► L-intersecting set systems: Online: [Penna-Sec4, Fox-Sec3] — Books: [Jukna-Sec13.6]
► Ramsey graph construction: [Online: Fox-Sec2, Penna-Sec5] — Books: [Jukna-Sec13.7]
Lecture 6: Distances
► Equilateral sets: Online: [Matoušek-p145(only that page!)]
► Odd-distance sets: Online: [Reference will come after the next lecture…]
► Two-distance sets: Online: [Matoušek-Ch15, Fox-Sec2] — Books: [Jukna-Sec13.5]
► Blokhuis’s improvement: Original paper
Lecture 7: Points and lines
► Crossing lemma and Szemerédi-Trotter theorem: Online: [Terence Tao’s blog] — Books: [Jukna-Sec18.5, AlonSpencer-p285]
► Sum and product sets: Online: [Terence Tao’s blog] — Books: [Jukna-Thm25.13]
Lecture 8-10: Eigenvalues of graphs
Notes for lectures 8, 9, and 10 – Might still be changed a little. Please let Frank know if you find any mistakes or if anything is unclear.
Lecture 11-13: The regularity method
Notes for lectures 11,12, and 13. Please let Bartosz know if you find any mistakes or if anything is unclear.
Texts
Work in progress – more references will appear here as we use them.
Online notes:
- Paolo Penna – Linear Algebra Methods in Combinatorics (course at Zurich with nice notes)
- Jacob Fox – Combinatorics (course at MIT, 11&13 are probability, 15-17 linear algebra, 18-22 eigenvalues)
- Matoušek-Vondrak – The Probabilistic Method (lecture notes based on Alon-Spencer)
- Jakub Závodný – Probabilistic Combinatorics (Oliver Riordan’s course at Oxford)
Books:
- Jukna – Extremal Combinatorics (LA, P, GE) – Draft available on author’s website.
- Matoušek – 33 Miniatures (LA, GE) – Draft available on author’s website.
- Alon-Spencer – The Probabilistic Method (P)
- Diestel – Graph Theory, 4th edition (P, RL) – Electronic edition available on author’s website.
- Bondy-Murty – Graph Theory, 2nd edition (P, RL)
LA = proofs with linear algebra, P = proofs with probability, GE = graph eigenvalues, RL = regularity lemma
Details
The course covers probabilistic and algebraic methods in discrete mathematics. The order of topics is:
Linear algebra proofs of discrete theorems
Probability proofs of discrete theorems
Eigenvalues of graphs
Szemerédi regularity and applications
There is no required textbook, but we suggest various online texts and books. The exam is written.
Feel free to email with any questions.
