__MAT 218C:
Topics in Discrete Mathematics__

**Time and Place:**
Monday/Wednesday 2.00-3.50 P.M., MS 5233. First class: Monday, October 3

**Instructor:**

Benny Sudakov,
MS 7911, bsudakov@math.ucla.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.

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

###
Assignments:

Assignment 1
Assignment 2
Assignment 3
###
Course Outline (to be updated during
the term):

*
Examples illustrating combinatorics and its connection with other areas of
mathematics. Pigeon-hole principle: Few quick example, Lemma of
Dirichlet, Erdos-Szekeres bound on longest increasing/decreasing subsequence.
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: two proofs and its application to probability theory and the 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; 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. 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.
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. Applications: Friendship theorem.
variational definition of eigenvalues, bounds on Max Cut, chromatic and independence number, expansion of graphs using eigenvalues.
*