Lecturers
Office Hours
Nabil Mustafa: Monday 3-5pm at MA C1 557.
Problem Sets
- Exercise 1.pdf
- Exercise 2.pdf
- Exercise 3.pdf
- Exercise 4.pdf
- Exercise 5.pdf
- Exercise 6.pdf
- Exercise 7.pdf
- Exercise 8.pdf
- Exercise 9.pdf
- Exercise 10.pdf
- Exercise 11.pdf
- Exercise 12.pdf
- chargeur.JPG
Other Material
Videos
Solution Sketches
- Solutions to Exercise 1.pdf
- Solutions to Exercise 2.pdf
- Solutions to Exercise 3.pdf
- Solutions to Exercise 4.pdf
- Solutions to Exercise 5.pdf
- Solutions to Exercise 6.pdf
- Solutions to Exercise 7.pdf
- Solutions to Exercise 8.pdf
- Solutions to Exercise 9.pdf
- Solutions to Exercise 10.pdf
- Solutions to Exercise 11.pdf
- Solutions to Exercise 12.pdf
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.)