Office: Armstrong Hall 408H

Office Hours: TuWThMW 11:30am-12:30pm, and by appointment

Class Meetings: TuTh 10:00am-11:15am in Armstrong Hall 313

References are as follows:

- AS:
*The Probabilistic Method*, N. Alon and J. H. Spencer - MR:
*Graph Colouring and the Probabilistic Method*, M. Molloy and B. Reed - GR:
*Algebraic Graph Theory*, C. Godsil and G. Royle

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 (C_{n})^{2} |
- |

28 | Apr 23 | - | HW6 due. |

milans@math.wvu.edu