## Topics in Extremal Combinatorics - 0366.4996 (Fall 2021)

### Instructor: Asaf Shapira

Grading: I will hand out several sets of exercises which will be graded.

## Tentative list of topics (to be updated during the semester)

• Lecture 1: Ramsey numbers of bounded degree graphs a-la Graham-Rodl-Rucinski.
• Lecture 2: Lower bound for Ramsey numbers of bounded degree graphs.
• Lecture 3: A closer look at r(3,n); the Ajtai-Komlos-Szemeredi upper bound (using groupies) and a nearly tight lower bound (Krivelevich's approach).
• Lecture 4: An improved bound for r(4,n), Shearer's proof of r(3,n) and the Erdos-Hajnal Theorem.
• Lecture 5: Erdos-Szemeredi Theorem on large homogenous sets in sparse graphs, Posa's Lemma and Size-ramsey number of the path (Beck's Theorem).
• Lecture 6: Posa's Theorem on Hamiltonicity of random graphs. Dependent random choice method: some basic applications and an imporved bound for Ramsey numbers of bounded degree bipartite graphs (Conlon-Fox-Sudakov).
• Lecture 7: A two-sided variant of dependent random choice lemma, and a quasi-linear bound for Ramsey numbers of degenerate bipartite graphs (Kostochka-Sudakov). Discrepancy in graphs (Erdos-Spencer Theorem).
• Lecture 8: Spencer's six standard deviations: upper bound and two lower bounds. The eigenvalue bound for discrepancy. Beck-Fiala Theorem.
• Lecture 9: Discrepancy of arithmetic progressions: Beck's upper bound and Lovasz's lower bound.
• Lecture 10: Linear and hereditary discrepancy. Linearity testing (BLR Theorem); a combinatorial proof and a spectral proof.
• Lecture 11: Testing bipartiteness in dense graphs (Goldreich-Goldwasser-Ron). A characterization of easily testable subgraphs (Alon).
• Lecture 12: Testing planarity in sparse graphs using Partition Oracles (Hassidim-Kelner-Nguyen-Onak).