Math 581EA
Advanced Methods in Combinatorics
László Lovász and Katalin Vesztergombi
Autumn 2002, Monday/Wednesday 12:30-1:50
Methods from algebra and probability applied to combinatorial
problems: rank arguments, eigenvalues of graphs, elements of
semidefinite optimization; the probabilistic method: first moment and
second moment, local lemma, FKG inequality. Applications to extremal
combinatorics, graph coloring, and other combinatorial problems.
The course uses only elementary linear algebra and probability, and
some basic knowledge in graph theory.
Recommended literature:
- Noga Alon, Joel H. Spencer: The probabilistic method,
Wiley-Interscience series in discrete mathematics and optimization,
John Wiley, New York, 2000.
- Laszlo Babai and Peter Frankl: Linear Algebra Methods in
Combinatorics With Applications to Geometry and Computer Science
(Preliminary Version), Department of Computer Science, The University
of Chicago. See the following website for ordering information:
http://www.cs.uchicago.edu/research/publications/combinatorics