# 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