# MAT 307: Combinatorics

Time and Place:

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.

Homeworks - 40%, Take home final exam - 60%

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.

• Assignment 1
•
• Assignment 2
•
• Assignment 3
•
• Assignment 4
•
• Assignment 5
•

### Final exam:

There will be take home exam, which can be obtained from Matthew Ferszt (room 306) on Friday, May 11. It is due on Tuesday, May 15 before 3.00 P.M. If I am not in my office at that time slide your exam under the door.

• Final exam
•

### Course Outline (to be updated during the term):

• February 5, 7:

• 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.

• February 12, 14:

• 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.

• February 19, 21:

• 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.

• February 26, 28, March 2:

• 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.

• March 5, 7, 9:

• 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.

• March 12, 14:

• 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.

• April 2, 4 :

• Three famous results on finite sets: Erdos-Ko-Rado theorem. Knezer graphs, Application of Borsuk-Ulam theorem to chromatic number of Knezer graphs.

• April 9, 11 :

• Algebraic methods: Even-odd town problem, Fischer's inequality, number of lines through non-collinear set of points, 2-distance sets in R^n.

• April 16, 18 :

• Algebraic methods: Bound on the number of sets with restricted pairwise intersections, modular version if restricted intersection problem, counterexample to Borsuk's conjecture.

• April 23, 25 :

• 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.

• April 30, May 2 :

• Spectral techniques: variational definition of eigenvalues, bounds on Max Cut, chromatic and independence number, expansion of graphs using eigenvalues.