|
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:
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, 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