# Introduction to Combinatorics 2011

Janos Pach

Nabil H. Mustafa

### Office Hours

Nabil Mustafa: Monday 3-5pm at MA C1 557.

### Other Material

Videos

Solution Sketches

List of theorems covered in class

Binomial theorem (proved via counting)
Number of even-sized subsets of n elements

e(n/e)^n <= n! <= ne(n/e)^n,  (n choose k) <=(en/k)^k
Principle of Inclusion-Exclusion

Sperner’s Lemma
Brouwer’s Fixed Point Theorem in Two Dimensions
Hedgehog Theorem

Erdos-Ko-Rado Theorem (proved via double counting)
Cayley’s Theorem

Sperner’s Theorem (proved via counting and via induction)
Decomposition into symmetric chains
An upper-bound of n^{1.5} for the unit-distance problem

Erdos-Szekeres Theorem
Dilworth’s Theorem

Erdos-Ko-Rado Theorem (proved via probabilistic method)
Schuette’s Problem

Any graph on n vertices and m edges has a cut of size m/2 (via double counting and via probabilistic method)
Epsilon-net problem: |X|<=2kln(m)  (via double counting and via probabilistic method)

Markov’s Inequality
Chebychev’s Inequality
Lower-bound on the central binomial coefficient

The largest distinct sum set is at most log_2(n) + 1/2 log_2(log_2(n)), where log_2 is logarithm base 2
Crossing Lemma (proved via probabilistic method)
A n^{4/3} bound for point-line incidences

Odd Town Problem (|A_i| odd for all i and |A_i \cap A_j| even for all i not equal to j)
Fisher’s Inequality

Sauer’s Lemma, Vapnik-Chervonenkis Theorem
Larman-Rogers-Seidel Theorem

If m < 2^{k-1} then there exists a two-coloring of the union of m k-sets such that none of them is monochromatic. (proved algorithmic and probabilistic)
Erdos-Szekeres Convex n-Gon Theorem

Notes (With the kind permission of Michael Schaertner.)