
Lecturer: Prof. Benny Sudakov
Wednesday 46, HG E 33.3
Assistant: Shagnik Das
Wednesday 34, 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, welldeveloped 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:
Assignments:
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, ErdosSzekeres 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 kcoloured 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 ErdosStone theorem Turan numbers of bipartite graphs, and applications to number theory 
Probabilistic Method 
Elementary tools Tournaments with the Schutte property 2colourability of uniform hypergraphs Linearity of expectation and sumfree subsets Graphs with large girth and large chromatic number 
Finite Sets 
Sperner's Theorem, and the LittlewoodOfford problem Bollobas' theorem on pairs of sets The ErdosKoRado Theorem Knezer graphs, and their chromatic numbers 
Algebraic Techniques 
Evenodd town problem Fisher's inequality The number of lines through noncollinear points 2distance 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 MaxCut, 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