Combinatorial Methods

Course Info

Instructor: Swastik Kopparty (swastik.kopparty@utoronto.ca)
Class Time and Place: Tuesdays 1pm-4pm, HA401
Office Hours: Tuesdays 10:30am-11:30am

Please use the course piazza site for questions.

This course will study assorted basic techniques in combinatorics. Homeworks are on the course quercus site.

Lectures

• Jan 10: Hall's theorem, Max-flow-min-cut
• Jan 17: Bipartite matching via determinants, Dilworth's theorem, Sperner's theorem, LYM inequality, the lattice of linear spaces over Fq (notes)
• Jan 24: Erdos-Ko-Rado, the ballot theorems, fun with necklaces (notes)
• Jan 31: Probabilistic inequalities, triangles in random graphs, K_2,2 freeness, Sidon sets (notes)
• Feb 7: Group actions and counting, Burnside's lemma, applications (notes)
• Feb 14: Ramsey theorem for graphs, infinite Ramsey for graphs, Ramsey for hypergraphs (notes)
• Feb 21: NO CLASS
• Feb 28: additive combinatorics: van der Waerden's theorem, Schur's theorem, Cauchy-Davenport theorem (notes)
Mar 7: Fourier analysis on finite abelian groups, BLR linearity test (notes)
• Mar 14: The sum-product phenomenon in the reals (notes)
• Mar 21: linear algebra methods, oddtown, eventown, 2-distance sets, Fisher's inequality, the projective plane (notes)
• Mar 28: VC dimension, the Sauer-Shelah lemma - 2 proofs (notes)
• April 4: Families of sets with small intersections (notes)