Combinatorial Methods - APM 461 / MAT 1302 Winter 2024
This is the page for Combinatorial Methods - APM 461 / MAT 1302 Winter 2024
Lecture: GB 304, Thursdays 11am-12 noon and Fridays 2pm-4pm.
Instructor Office hours: Tuesdays 2pm - 3pm, SF 3324
The class piazza is on the left.
Reference books:
A Course in Combinatorics, van Lint and Wilson
Scribed lecture notes are on the piazza.
Sign up for scribing by claiming a date on the piazza.
For scribe notes - definitions file Download definitions file, sample notes file Download sample notes file (Click on the link, and even if it is slow to load, just click download -- quercus delays because it is trying to compile the latex file and show it).
| Date | Topic |
| Jan 11 | Course overview, Halls' theorem |
| Jan 12 | Matching via determinants, the Schwartz-Zippel lemma, flows and cuts |
| Jan 18 | proof of the max flow min cut theorem |
| Jan 19 | Sperner's theorem, LYM inequality, Dilworth's theorem |
| Jan 25 | the Erdos-Ko-Rado theorem via random necklaces |
| Jan 26 | the number of necklaces, Burnside's lemma, Fermat's little theorem via necklaces, the ballot theorem, Sidon sets |
| Feb 1 | optimal Sidon sets |
| Feb 2 | higher order Sidon sets, max # of edges in K_{2,2} - free bipartite graphs, probabilistic construction, lines vs points graph over a finite field |
| Feb 8 | Ramsey theorem for graphs, probabilistic lower bound |
| Feb 9 | Ramsey theorem for infinite graphs, Ramsey theorem for 3-uniform hypergraphs |
| Feb 15 | Large independent sets, Turan's theorem |
| Feb 16 | Tail bounds for sums of random variables, application to triangle counts in G(n,p) |
| Feb 22 | NO CLASS (reading week) |
| Feb 23 |
NO CLASS (reading week) |
| Feb 29 | Linear algebra over finite fields, odd and even towns |
| Mar 1 | More odd and even towns, the projective plane, statement of Fisher's inequality |
| Mar 7 | Odd-even-town-constructive-Ramsey-graph, proof of Fisher's inequality |
| Mar 8 | 1 and 2-distance sets, Ray-Chaudhuri-Wilson theorem on restricted set intersections |
| Mar 14 | |
| Mar 15 | |
| Mar 21 | |
| Mar 22 | |
| Mar 28 | |
| Mar 29 | NO CLASS (Good Friday) |
| April 4 | |
| April 5 | |
| April 8 - MAKEUP MONDAY | NO CLASS |