The Discrete Math Toolkit
MAT1306, Spring 2022
Course Info
Instructor: Swastik Kopparty (swastik.kopparty@utoronto.ca)
Class Time and Place: Wednesdays 1pm-4pm, SK720
Office Hours: Wednesdays 10am-11am (on Zoom)
Please use the course piazza site for questions.
This course will study assorted basic tools in the discrete math toolkit.
Homeworks are on the course quercus site.
Lectures
- Jan 12: Hall's theorem, Max-flow-min-cut, Dilworth's theorem
- Jan 19: Sperner's theorem, LYM inequality, Shadows, Entropy, Shearer's lemma, Weak Kruskal-Katona
- Jan 26: colex order, compressions, Kruskal-Katona
- Feb 2: Erdos-Ko-Rado, t-intersecting families, Ramsey's theorem - finite and infinite
- Feb 9: Lower bounds for Ramsey numbers, Ramsey numbers for hypergraphs, Dense bipartite graphs have many K_{s,t}'s
- Feb 16: Probabilistic methods - basic probability inequalities, the basic probabilistic method, the method of alterations, variance, various examples
- Feb 23: NO CLASS
- March 2: More on the probabilistic method - girth vs edges (Moore bound), girth vs chromatic number, quasirandomness
- March 9: quasirandom graphs, edges in C4-free graphs, the projective plane graph
- March 16: linear algebra methods, restricted set intersections, Ray-Chaudhuri-Wilson, Frankl-Wilson, geometric applications
- March 23: VC dimension, Sauer-Shelah lemma, epsilon-nets
- March 30: Discrepancy - combinatorial discrepancy, Beck-Fiala, basic probabilistic bound, Spencer's theorem
- April 6: Entropy