# 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)