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 ala GrahamRodlRucinski.

Lecture 2:
Lower bound for Ramsey numbers of bounded degree graphs.

Lecture 3:
A closer look at r(3,n); the AjtaiKomlosSzemeredi 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 ErdosHajnal Theorem.

Lecture 5:
ErdosSzemeredi Theorem on large homogenous sets in sparse graphs,
Posa's Lemma and Sizeramsey 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 (ConlonFoxSudakov).

Lecture 7:
A twosided variant of dependent random choice lemma, and a quasilinear
bound for Ramsey numbers of degenerate bipartite graphs
(KostochkaSudakov).
Discrepancy in graphs (ErdosSpencer Theorem).

Lecture 8:
Spencer's six standard deviations: upper bound and two lower bounds.
The eigenvalue bound for discrepancy. BeckFiala 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 (GoldreichGoldwasserRon).
A characterization of easily testable subgraphs (Alon).

Lecture 12:
Testing planarity in sparse graphs using Partition Oracles
(HassidimKelnerNguyenOnak).