Introduction to Combinatorics 2011

Office Hours

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

Other Material


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