Department of Mathematics

Topics in Discrete Mathematics

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

Lecturer: Prof. Benny Sudakov

Wednesday 4-6, HG E 33.3

Assistant: Shagnik Das

Wednesday 3-4, ML J 37.1

Course Description:

The aim of the course is to introduce students to Combinatorics, a fundamental mathematical discipline as well as an essential component of many mathematical areas. While in the past many of the basic combinatorial results were obtained by ingenuity and detailed reasoning, the modern theory has grown out of this early stage and often relies on deep, well-developed tools. The course will cover over a dozen virtually independent topics, chosen to illustrate several such techniques. This is an ultimate fun course, showcasing the gems of modern Combinatorics.

This course is aimed at third year undergraduates and masters students who have already taken basic courses in Combinatorics.

Sample Reading List:

There is no single book which covers all the topics in this course.  Among the sources that were used are the following books:


Course Syllabus:

These notes are from a previous edition of this course. This semester's course may deviate somewhat from the notes.

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

Subject Topics
 Introduction Combinatorics and its connections to other areas
Basic graph theory and Eulerian graphs
Pigeonhole principle: quick examples, Lemma of Dirichlet, Erdos-Szekeres bound on monotone subsequences
Double counting
Sperner's Lemma and Brouwer's Fixed Point Theorem
 Ramsey Theory
Ramsey's Theorem for graphs and set systems
Finding a convex polygon among points in a plane
Upper bound for k-coloured Ramsey numbers of triangles
Lower bound for Ramsey numbers
Ramsey theory for integers: Schur's theorem and van der Waerden's theorem
Density of subsets of integers not containing cubes
 Turan Theory
Two proofs and the number of edges in permutation graphs
Erdos-Stone theorem
Turan numbers of bipartite graphs, and applications to number theory
 Probabilistic Method
Elementary tools
Tournaments with the Schutte property
2-colourability of uniform hypergraphs
Linearity of expectation and sum-free subsets
Graphs with large girth and large chromatic number
 Finite Sets
 Sperner's Theorem, and the Littlewood-Offord problem
Bollobas' theorem on pairs of sets
The Erdos-Ko-Rado Theorem
Knezer graphs, and their chromatic numbers
 Algebraic Techniques
Even-odd town problem
Fisher's inequality
The number of lines through non-collinear points
2-distance sets in R^n
Set systems with restricted pairwise intersections
Counterexample to Borsuk's conjecture
 Spectral Techniques
Adjacency matrix of a graph and its eigenvalues
Eigenvalues of cliques, complete bipartite graphs, complements of graphs and a line graph
Applications: decomposition of K_10 into Petersen graphs, Friendship theorem
Variational definition of eigenvalues
Bounds on Max-Cut, chromatic and independence numbers
Expander graphs

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