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.

    •