| Topic | Monday | Wednesday | Friday |
|---|---|---|---|
| Counting |
August 27
First principles of counting Keller and Trotter 2.1-2.3 |
August 29
Binomial Theorem/bijections Keller and Trotter 2.4-2.6 |
August 31
Estimation Matousek and Nesetril 3.4-3.5 |
| Inclusion/Exclusion |
September 3
Labor Day: no class |
September 5
Inclusion/Exclusion Keller and Trotter 7.1-7.3 |
September 7
Inclusions/Exclusion Keller and Trotter 7.4-7.5 |
| Intro to Graph Theory |
September 10
First definitions, bipartite and planar graphs Bondy and Murty 1.1-1.2, 1.4-1.7 Bona 11.1-11.2, 12.1 |
September 12
Planar graphs Bona 12.1 Matousek and Nesetril 6.3-6.4 |
September 14
Coloring planar graphs 6 and 5 color theorems Bona 12.3 |
| Spectral Graph Theory |
September 17
Adjacency matrices and walk-counting Bona 10.3-10.4 |
September 19
Walk counting and the spectral radius |
September 21
The Turan function Mantel's Theorem |
| Intro to Extremal Graph Theory |
September 24
5 proofs of Turan's Theorem |
September 26
Ramsey's Theorem |
September 28
Exam 1 |
| First Moment Method |
October 1
Intro to Probabilistic Method Keller and Trotter 10.1-10.2 |
October 3
First Moment Method Keller and Trotter 11.1, 11.4 |
October 5
Alterations Matousek and Vondrak 18-22 |
| Concentration Inequalities |
October 8
Markov's Inequality |
October 10
Chebyshev's Inequality |
October 12
Chernoff Bound |
| Extremal Graph Theory |
October 15
Kovari-Sos-Turan Theorem |
October 17
Projective planes |
October 19
Mid-semester break: no class |
| C_4 free graphs |
October 22
Sidon sets and Cayley graphs |
October 24
Construction of dense Sidon sets and asymptotics for C_4 Turan number |
October 26
Presidential Inauguration Day: no class |
| Ramsey theorems on equations |
October 29
Schur's Theorem and Fermat's last theorem over finite fields |
October 31
van der Waerden's theorem |
November 2
Exam 2 |
| Extremal set theory |
November 5
Erdos-Ko-Rado theorem |
November 7
Even/odd town |
November 9 |
| Spectral graph theory |
November 12
Graham-Pollak theorem |
November 14
Expander-Mixing lemma |
November 16
Hoffman-Singleton theorem |
| November 19
Sum-product estimates |
November 21
Thanksgiving break |
November 23
Thanksgiving break |
|
| Lovasz Local Lemma |
November 26
Lovasz Local Lemma |
November 28
Applications |
November 30
Combinatorial Nullstellensatz |
| December 3
Applications |
December 5
Blakeley-Roy theorem |
December 7
Alon-Boppana-Serre theorem |