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