References are as follows:
No. | Date | Class Summary | Comments |
1 | Jan 13 | Graphs with small clique and independence numbers; useful inequalities | - |
2 | Jan 15 | Discrete probability spaces; union bound; runs of heads | HW1 assigned. |
3 | Jan 20 | Independence of events; random variables; expected value | - |
4 | Jan 22 | Linearity of expectation; k-uniform hypergraphs that are not 2-colorable | - |
5 | Jan 27 | Convexity; Jensen's inequality | - |
6 | Jan 29 | Analysis tricks; sum-free subset example | HW1 due; HW2 assigned. |
7 | Feb 3 | Conditional probabilities and expectations; random walks | - |
8 | Feb 5 | Alterations: dominating sets; derandomization | - |
9 | Feb 10 | Erdos--Ko--Rado; the random graph; randomness as a resource | - |
10 | Feb 12 | Markov's inequality; Large girth and large chromatic number | HW2 due; HW3 assigned. |
11 | Feb 17 | Bollobas's Thm; List chromatic number; degeneracy | - |
12 | Feb 19 | Alon: List chromatic number grows with degeneracy | - |
13 | Feb 24 | Second moment; sets with distinct sums | - |
14 | Feb 26 | Mutual independence; Local Lemma I | HW3 due; HW4 assigned. |
15 | Mar 3 | Local Lemma II (general case and proof) | - |
16 | Mar 5 | Linear forests; linear arboricity of graphs with large girth | - |
17 | Mar 10 | Chernoff-type bounds I | - |
18 | Mar 12 | Chernoff-type bounds II | HW4 due. |
19 | Mar 17 | Hadwiger conjecture; refutation of the Hajos conjecture I | - |
20 | Mar 19 | Refutation of the Hajos conjecture II | - |
21 | Mar 31 | The polynomial method; eventown and oddtown | - |
22 | Apr 2 | Matrix criterion for independence; k-distance sets I | HW5 due. |
23 | Apr 7 | k-distance sets II; Multilinear reduction; Frankl--Wilson Thm | - |
24 | Apr 9 | Combinatorial Nullstellensatz I; Cauchy--Davenport Thm | - |
25 | Apr 14 | Combinatorial Nullstellensatz II; Chevalley--Warning Thm | - |
26 | Apr 16 | Alon--Tarsi Thm | - |
27 | Apr 21 | Alon--Tarsi Application: List chromatic number of (Cn)2 | - |
28 | Apr 23 | - | HW6 due. |