Topics in Extremal Combinatorics - 0366.4996 (Fall 2021)
Grading: I will hand out several sets of exercises which
will be graded.
Lecture Notes
Home Assignments
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).