Combinatorial Methods
APM461/MAT1302, Winter 2023
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.
Syllabus and course policies
Lectures
Scribe notes definitions latex file
Scribe notes sample latex file
- 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)