Department of Mathematics

Algebraic Methods in Combinatorics

Please note that this page is old.
Check in the VVZ for a current information.

Lecturer: Prof. Benny Sudakov

Thursday 13:00-15:00, HG F 3

Assistant: Dániel Korándi

Tuesday 11:00-12:00, CAB G 52

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 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 the Kakeya problem in finite fields, counterexample to Borsuk's conjecture, chromatic number of the unit distance graph of the Euclidean space, explicit constructions of Ramsey graphs, and many others.


Course Syllabus:

We will cover the following topics this semester. This outline may be updated as the term progresses.

Introduction Rules and Clubs
Lindström's theorem
Points in the Euclidean space with only two distances
Kakeya problem in finite fields
Consistent edge-colorings of the complete graph
Number of lines determined by non-collinear points in the plane
Non-uniform Fisher's inequality
Set systems with restricted intersections: Ray-Chaudhuri–Wilson theorem
Frankl–Wilson theorem
Applications of intersection theorems Explicit constructions of Ramsey graphs
Chromatic number of the unit distance graph of the Euclidean space
Counterexample to Borsuk's conjecture
Convexity Radon lemma and Helly's theorem
Existence of Centerpoint
Colorful Carathéodory theorem
Tverberg's theorem
Eigenvalues definition, simple properties, computation for few basic families of graphs
Applications: Decomposition of K_10 into Petersen's graphs
Variational definition of eigenvalues and applications to interlacing, bounding independence number, chromatic number, max cut
Expansion and spectral gap
Bounding matrix ranks and Johnson–Lindenstrauss lemma
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 the Erdős–Ginzburg–Ziv lemma
Combinatorial Nullstellensatz, Bounds on the size of the sum of two subsets in Z_p Cauchy–Davenport theorem and Erdős–Heilbronn conjecture
Covering cubes by hyperplanes
List chromatic number, applications of the Combinatorial Nullstellensatz to graph colorings

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information

© 2016 Mathematics Department | Imprint | Disclaimer | 8 February 2015