Course: MCS 591, Advanced topics in combinatorial theory: Graph theory and Algorithms
Call no: TBA
Time: MWF 1100-1150pm
Place: 304 Taft Hall

Professor: Dhruv Mubayi
Office: 620 SEO
Tel: 3-8036
E-mail: mubayi@math.uic.edu
Course Web Page: http://www.math.uic.edu/~mubayi/591/591Spring10.html

Office Hours: M, F 2-3 and by appointment

The course will cover a selection of topics in graph theory with a focus on algorithmic aspects. It should be of interest to students in both mathematics and theoretical computer science.
A possible list of topics include:

  • planar graphs, including Kuratowski's Theorem, Lipton-Tarjan separators and treewidth
  • matching theory, including the Gallai-Edmonds Decomposition
  • graph coloring with a focus on recent advances in equitable coloring (Kierstead-Kostochka algorithmic proof of the Hajnal-Szemeredi theorem and a recent hypergraph version of Kierstead-Mubayi)
  • list coloring and stable matching algorithms (Galvin's theorem)
  • algorithmic extremal graph theory including the algorithmic Szemeredi regularity Lemma (Alon-Duke-Lefmann-Rodl-Yuster), and recent efficient algorithms for the Zarankiewicz and Bipartite Ramsey Problems (Mubayi-Turan); classical topics like the Ruzsa-Szemeredi (6,3) theorem and Szemeredi's theorem for arithmetic progressions
  • applications of the regularity lemma to property testing
  • pseudo-random graphs and their applications and constructions; recent developments for hypergraphs
  • the recent algorithmic Lovasz Local Lemma (Moser-Tardos)

    • Prerequisites: Familiarity with the material covered in MCS 423 (Graph Theory), MCS 401 (algorithms) and the mathematical maturity of an advanced graduate student.

    Text: Diestel, Graph Theory, 3rd edition 2005, Springer-Verlag, Heidelberg. This will be our basic reference text and we will frequently use other sources, mainly papers that I will let you know about.

    Grade: Your grade will be based on homework, and some class presentations.

    Homework 1, Due Friday January 22
    Chapter 1: 3, 7, 19, 23, 24
    Homework 1 Solutions

    Homework 2, Due MONDAY February 8 (NOTE THE EXTENSION)
    Chapter 2: 4, 5, 6, 13, 17, 18, 21
    Homework 2 Solutions

    MONDAY Feb 15 NO CLASS -- FURLOUGH DAY: Please read the proofs of Lemma 3.5.1 (carefully) and Theorem 3.5.2

    Homework 3, Due Friday February 26 (almost 3 weeks)
    Chapter 3: 7, 11 part (i), 16, 17, 25
    Homework 3 Solutions

    MONDAY MARCH 8 NO CLASS -- FURLOUGH DAY:

    Homework 4, Due Friday March 12
    Chapter 4: 5, 12, 20, 23, and finish the proof of the Alon-Seymour-Thomas proof from class, i.e., let C be a planar cycle with vertices v0,v1, v2, ..., v2k=v0 in clockwise order. Suppose that there are no shortcuts between two vertices in C that use vertices in D which is the subgraph consisting of C and everything inside it. Prove that there are k disjoint paths from {v0, .. vk} to {vk, .. v2k}
    I will be adding more homework to this set so start early.

    Added problems: Chapter 5: 6, 10

    Homework 5, Due Friday April 2
    Chapter 5: 16, 28, 36, 37, Maybe more later

    MONDAY MARCH 29 NO CLASS -- FURLOUGH DAY:

    Homework 6, Due Friday April 16
    Chapter 7: 5, 14, 15, 16, 38, 39

    Homework 7, Due Friday April 30
    Chapter 9: 8, 9, 10, 12
    Chapter 10: 1, 8