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

Syllabus

Scribed lecture notes are on the piazza.

Sign up for scribing by claiming a date on the piazza.

For scribe notes - definitions file, 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