Monday, Wednesday 3:00-4.50 P.M., MS 5148.
First class - January 7
Instructor:
Benny Sudakov, MS 7911,
bsudakov@math.ucla.edu
Course description:
Combinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. While in the past many of the basic combinatorial results were obtained mainly by ingenuity and detailed reasoning, the modern theory has grown out of this early stage and often relies on deep, well-developed tools.
One of the main general techniques that played a crucial role in the development of Combinatorics was the application of algebraic methods. The most fruitful such tool is the dimension argument. Roughly speaking, the method can be described as follows. In order to bound the cardinality of of a discrete structure A one maps its elements to vectors in a linear space, and shows that the set A is mapped to linearly independent vectors. It then follows that the cardinality of A is bounded by the dimension of the corresponding linear space. This simple idea is surprisingly powerful and has many famous applications.
This course provides a gentle introduction to Algebraic methods, illustrated by examples and focusing on basic ideas and connections to other areas. The topics covered in the class will include (but are not limited to):
Basic dimension arguments, Spaces of polynomials and tensor product methods, Eigenvalues of graphs and their application, the Combinatorial Nullstellensatz and the Chevalley-Warning theorem. Applications such as: Solution of Kakeya problem in finite fields, counterexample to Borsuk's conjecture, chromatic number of the unit distance graph of Euclidean space, explicit constructions of Ramsey graphs and many others.
Text books:
Most of the topics covered in the course appear in the books and surveys listed below (especially the first two).
Linear algebra methods in combinatorics, by L. Babai and P. Frankl, Department of Computer Science, University of Chicago, preliminary version, 1992.
Combinatorial Nullstellensatz,
by N. Alon, Combinatorics, Probability and Computing 8 (1999), 7-29.
download from : http://www.math.tau.ac.il/~nogaa/PDFS/publications.html
Tools from higher algebra, by N. Alon,
in : "Handbook of Combinatorics", R.L. Graham, M. Grötschel and L.
Lovàsz, eds, North Holland (1995), Chapter 32, pp. 1749-1783.
download from : http://www.math.tau.ac.il/~nogaa/PDFS/publications.html
Tools from linear algebra, by Chris Godsil,
in : "Handbook of Combinatorics", R.L. Graham, M. Grötschel and L.
Lovàsz, eds, North Holland (1995), Chapter 31.
download from : http://quoll.uwaterloo.ca/mine/Notes/index.html
Introduction: Rules and Clubs, Lindstrom Theorem,
Points in Euclidean space with only two distances, Kakeya problem in finite fields,
Consistent edge-colorings of
complete graph, Number of lines determined by non-colinear points in the plane,
Non-uniform Fisher's inequality
Set systems with restricted intersections:
theorems of Ray-Chaudhuri-Wilson and Frankl-Wilson
Applications of intersection theorems:
Explicit constructions of Ramsey graphs,
Chromatic number of the unit distance graph of Euclidean space, Counterexample to Borsuk's conjecture.
Convexity:
Radon lemma and Helly's theorem, Existence of Centerpoint,
Colorful Caratheodory Theorem, Tverbergs theorem.
Eigenvalues: definition, simple properties, computation for few basic
families of graphs. Applications:
Decomposition of K_10 into Petersen's graphs, Friendship theorem.
Variational definition of eigenvalues and applications to interlacing,
bounding independence number, chromatic number, max cut. Expansion and spectral gap.
Chevalley-Warning theorem and its applications:
3-regular subgraphs of 4-regular graphs, Davenport constants of
abelian groups, Blocking sets in Affine hyperplanes, Zero sum sets
and Erdos-Ginzburg-Ziv lemma.
Tensor product methods: Definition of the wedge product and its
properties, application of wedge products in Extremal set theory, Helly type theorems for
finite sets, number of edges in saturated graphs. Schwartz lemma and subspaces in general position,
application of wedge products to prove Bollobas-type theorems for vector spaces.
Combinatorial Nullstellensatz, Bounds on the size of the sum of two subsets in
Z_p: Cauchy-Davenport theorem and Erdos-Heilbronn conjecture.
Covering cubes by hyperplanes. List chromatic number, applications of Combinatorial Nullstellensatz to graph colorings.