Topics in Combinatorics and Graph Theory - 0366.4771.01

Noga Alon ( nogaa@tau.ac.il )
2nd Semester, 2009-2010 - Wednesday 16-19, Schreiber 006
School of Computer Science
Tel-Aviv University

Procedural Matters:

Desirable background: Basic knowledge of Combinatorics, Graph Theory, Linear Algebra, Probability and the basic elements of Combinatorial Algorithms.
Exercises will be given during the course and their solutions will be graded.

Text books:

Most of the topics covered in the course appear in papers, but some are described (at least to some extent) in the following books.
J. H. van Lint and R. M. Wilson, A course in Combinatorics, 2nd Edition, Cambridge University Press, 2001.
R. Diestel, Graph Theory, 3rd Edition, Springer Verlag, 2005.
N. Alon and J. H. Spencer, The Probabilistic Method, 3rd Edition, Wiley, 2008.

Course syllabus:

I plan to cover several topics in Combinatorics and Graph Theory including their algorithmic aspects and some of their applications in Information Theory and in Theoretical Computer Science. The main specific topics that will be studied include the Shannon capacity of graphs and other invariants of graph powers, the regularity lemma and its applications in Extremal Graph Theory and in Graph Property Testing, Grothendieck-type Inequalities and approximation algorithms for dense graphs, applications of polynomials in Discrete Mathematics.

Course Outline:

  1. Feb. 24:
    Introduction, the Shannon capacity of a graph, the Lovasz Theta Function.
  2. March 3:
    The Shannon capacity of a union.
  3. March 10:
    Dual source coding and chromatic numbers of graph powers.
  4. March 17:
    More on dual source coding.
  5. March 24:
    The Regularity Lemma of Szemeredi.
  6. April 7:
    Applying the regularity lemma; the Ruzsa-Szemeredi theorem, dense sets of integers contain 3-term arithmetic progressions.
  7. April 14:
    An algorithmic version of the regularity lemma using Grothendieck's Inequality.
  8. April 21:
    The cut decomposition method and approximation algorithms for dense graphs.
  9. April 28:
    Graph Property Testing.
  10. May 5:
    Dependent Random Choice
  11. May 12:
    Graph Property Testing via the regularity lemma.
  12. May 26:
    Grothendieck type inequalities and approximation algorithms.
  13. June 2:
    No class: IMU meeting at the Weizmann Institute, see: The 2010 Meeting of the Israel Mathematical Union
  14. June 9:
    Polynomials in Combinatorics, conclusions.

Exercises