Topics in Combinatorics - 0366.4996 (Spring 2015)
Grading: I will hand out several sets of exercises which
will be graded.
List of Topics (to be updated during the semester)
Ramsey numbers of bounded degree graphs a-la Graham-Rodl-Rucinski.
Lower bound for Ramsey numbers of bounded degree graphs.
A closer look at r(3,n); the Ajtai-Komlos-Szemeredi upper bound (using
groupies) and a nearly tight lower bound (Krivelevich's approach).
An improved bound for r(4,n), Shearer's proof of r(3,n) and
the Erdos-Hajnal Theorem.
Erdos-Szemeredi Theorem on large homogenous sets in sparse graphs,
Posa's Lemma and Size-ramsey number of the path (Beck's Theorem).
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).
A two-sided variant of dependent random choice lemma, and a quasi-linear
bound for Ramsey numbers of degenerate bipartite graphs
Discrepancy in graphs (Erdos-Spencer Theorem).
Spencer's six standard deviations: upper bound and two lower bounds.
The eigenvalue bound for discrepancy. Beck-Fiala Theorem.
Discrepancy of arithmetic progressions: Beck's upper bound and
Lovasz's lower bound.
Linear and hereditary discrepancy. Linearity testing (BLR Theorem);
a combinatorial proof and a spectral proof.
Testing bipartiteness in dense graphs (Goldreich-Goldwasser-Ron).
A characterization of easily testable subgraphs (Alon).
Testing planarity in sparse graphs using Partition Oracles