Monday 8:30-9:50 P.M., Fine Hall
314.
Instructor:
Benny Sudakov, Fine Hall 609,
bsudakov@math.princeton.edu
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.
Grading:
Homeworks - 40%, Take home final exam - 60%
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.
Extremal combinatorics, by S. Jukna.
A course in Combinatorics, by J.H. van Lint and R. Wilson.
Modern graph theory, by B. Bollobas
Proofs from the book, by M. Aigner and G. Ziegler.
Examples illustrating combinatorics and its connection with other areas of
mathematics. Basic graph theory, Eulerian graphs. Pigeon-hole principle: Few quick example, Lemma of
Dirichlet, Erdos-Szekeres bound on longest increasing/decreasing subsequence. Double counting.
Sperner lemma and
fixed point theorem of Brouwer. Ramsey Theorem for graphs and set systems.
Finding convex polygon among points in the plane. Upper bound for k-colored Ramsey numbers of triangle.
Lower bound for Ramsey numbers and the power of
counting. Ramsey theory for integers, theorems of Schur and van der Waerden.
Density of subsets of integers not containing cubes. Turan's theorem: statement and first application.
Turan's theorem: two proofs and its application to number of edges in permutation graphs.
Turan numbers for general graphs, theorem
of Erdos-Stone. Maximum number of edges in graph with no 4-cycles.
Maximum number of edges in graph with no fixed complete bipartite subgraph K_{t,s} and application of this results to
additive number theory. Probabilistic methods: elementary tools; tournaments with Schutte property, i.e., every k players
are beaten by somebody; 2-colorability of uniform hypergraphs; Linearity of expectation with application to
sum-free subsets.
Probabilistic methods: graphs with large girth and large chromatic number.
Three famous results on finite sets: Sperner theorem and its application to
Littlewood-Offord problem. Theorem of Bollobas on set-pairs.
Three famous results on finite sets: Erdos-Ko-Rado theorem.
Knezer graphs, Application of Borsuk-Ulam theorem to
chromatic number of Knezer graphs.
Algebraic methods: Even-odd town problem, Fischer's inequality,
number of lines through non-collinear set of points, 2-distance sets in R^n.
Algebraic methods: Bound on the number of sets with restricted pairwise intersections,
modular version if restricted intersection problem, counterexample to Borsuk's conjecture.
Spectral techniques: Adjacency matrix of a graph and its eigenvalues,
Eigenvalues of cliques, complete bipartite graph, complement of a graph and a line graph.
Applications: decompositions of K_10 into Petersen graph, Friendship theorem.
Spectral techniques: variational definition of eigenvalues, bounds
on Max Cut, chromatic and independence number, expansion of graphs
using eigenvalues.