Master course:
Probabilistic and extremal combinatorics

Fall 2013

Brief overview of the course

We will cover selected topics in discrete geometry, additive number theory, Ramsey theory, extremal set theory, and random and extremal graph theory. This includes some of the most attractive results in modern mathematics such as Szemerédi's theorem (on arithmetic progressions in integer subsets of positive density), the Hales-Jewett theorem, bounds on the size of sum-free sets, Kahn and Kalai's counterexample to Borsuk's conjecture (on dissecting sets in d-dimensional space into pieces of strictly smaller diameter) and bounds on the Hadwiger-Nelson problem (of colouring d-dimensional space such that points at distance one receive different colors).
Central to the course are applications of "the probabilistic method", popularized by Pál Erdős in the second half of the twentieth century. That is, we use probabilistic reasoning to obtain (often extremely elegant and short) proofs of statements that seemingly have nothing to do with probability. We will also cover the use of some other methods, including algebraic ones. More specifically, the tools we will cover include the Lovász local lemma, Alon's Nullstellensatz, Szemerédi's regularity lemma, the basic first and second moment methods, Martingale and other concentration inequalities.

Time and location

The course takes place on Tuesdays 14:00 - 16:45 at the VU campus in Amsterdam.
The first lecture is in week 38, on Tuesday 17 September 2013.

The location of the lectures is as follows. Week 38: HG-01A05, weeks 39, 40: WN-M655, week 41-43: HG-04A04, week 44: WN-M143, week 45-48: WN-M623, week 49, 50: WN-F647. (HG = "hoofdgebouw", WN = "W & N gebouw")

Lecturers

Ross J. Kang and Tobias Müller will each present roughly half of the lectures.

Examination

Homework exercises and a written examination (re-examination as oral exam). Homework counts for 50% of the final grade.

The exam will took place on 10 December 2013, 14:00-16:30, room WN-F647.

List of examinable topics

Statement and proof: Erdos-Ko-Rado theorem; Frankl-Wilson theorem; Exponential lower bound on chromatic number of d-space; Counterexample to Borsuk's conjecture; Sperner's theorem; Turan's theorem; Erdos-Stone theorem; crossing number inequality; Erdos-Szekeres upper bound recurrence and Erdos probabilistic lower bound for 2-colour graph Ramsey numbers; Schur's theorem assuming graph Ramsey's theorem; Erdos' construction of graphs with arbitrarily high girth and chromatic number; Diananda and Yap upper bound for sum-free sets in finite groups assuming Kneser's theorem; Erdos' construction of large sum-free sets of integers; Van der Waerden's theorem assuming Hales-Jewett theorem; Triangle removal lemma assuming Szemeredi's regularity lemma; Roth's theorem assuming triangle removal lemma.
Theorem statements only: Ramsey's theorem, full form (multicolour and hypergraphs); Goodman's formula; Erdos and Rado upper bound; Kneser's theorem; Hales-Jewett theorem and density version; Szemeredi's theorem; Szemeredi's regularity lemma.

Practice Exam

For your convenience we have made a practice exam. You can find it here. Solutions can be found here.

The real exam

The written exam can be found here, and solutions can be found here.

Literature

• N. Alon and J. H. Spencer. The probabilistic method, 3rd ed. Wiley-Interscience, 2008. ISBN 978-0-470-17020-5.


• S. Jukna. Extremal Combinatorics, 2nd ed. Springer-Verlag, 2011. ISBN 978-3-642-17363-9.


• J. Matousek. Thirty-three miniatures, Student Mathematical Library, American Mathematical Society, ISBN 987-0-8218-4977-4


• Selected research articles to be determined during the course.

Weekly schedule

• 17 September: general introduction to extremal combinatorics and the probabilistic method. Erdos-Ko-Rado theorem (Alon+Spencer page 13).


• 24 September: Frankl-Wilson (treatment followed Matousek, "Thirty three miniatures", pages 57-60. A very similar result with a very similar proof is Theorem 14.13 in Jukna. Note Theorem 14.14 implies the Frankl-Wilson Theorem proved in the lecture). Exponential lower bound on the chromatic number of \(d\)-dimensional space (Jukna exercises 14.25, 14.25)
  Homework: At the start of next week's lecture, please hand in your solutions to the following exercises:
  1) Prove that \(r(3,3)=6\).
  2) Prove that \(\chi({\mathbb R}^2) \leq 7\).
  3) Prove that there exists a \(\gamma > 1\) such that \( \frac{{4p\choose 2p-1}}{{4p\choose 0}+\dots+{4p\choose p-1}} > \gamma^p\), for all sufficiently large \(p\).
  4) Finish the proof that there exists a \(\gamma > 1\) such that \(\chi({\mathbb R}^d) > \gamma^d\) for all \(d\). (Hint: use Bertands postulate.)
  5) Watch "\(n\) is a number".


• 1 October: Kahn-Kalai's counterexample to Borsuk's conjecture (treatment followed Matousek, "Thirty-three miniatures", pages 61-65). Two-distance sets (Jukna page 177).
  


• 8 October: Covered Sperner's theorem (A+S 219 and/or Jukna page 111). Turán's theorem (A+S page 95, or Jukna pages 56-59). Start of Erdos-Stone theorem.
  Homework: At the start of the Oct 15 lecture, please hand in your solutions to the following exercises:
  1) Give an example of a \(2\)-distance set in \({\mathbb R}^d\) with \({d+1 \choose 2}\) elements.
  2) Show that if \({\mathcal F} \subseteq 2^{[n]}\) is an antichain and there is a \(k\leq n/2\) such that \(|A| \leq k\) for all \(A\in{\mathcal F}\) then \(|{\mathcal F}| \leq {n \choose k}\).
  3) Show that if \( e(G) \geq \lfloor n^2/4\rfloor + 1\) then \(G\) has at least \(\lfloor n/2\rfloor\) triangles. (Here \(n = v(G)\) as usual.)


• 15 October: Finished proof of Erdos-Stone. This is not in either book, but you can for instance find a proof close to the one presented in the lecture here. Start of crossing number inequality.
  


• 22 October: Proved the crossing number inequality and Szemeredi-Trotter (Jukna chapter 18). Upper bound on unit distances (not in either book, a proof can be found here).
  Homework: At the start of the Oct 29 lecture, please hand in your solutions to the following exercises:
  1) Let \(H\) be a graph, and let \(n > v(H)\) be an integer. Suppose there is a graph on \(n\) vertices and \(t\) edges containing no copy of \(H\), and suppose that \(tk > n^2 \ln n\). Show that there is a coloring of the edges of \(K_n\) by \(k\) colors with no monochromatic copy of \(H\).
  2) Let \(G\) be an arbitrary graph and write \(n = v(G)\). Show that the number of triangles in \(G\) plus the number of triangles in \(\overline{G}\) is at least \( n(n-1)(n-5)/24 \).
  (Here \(\overline{G} = \left(V, {V\choose 2} \setminus E\right)\) denotes the "complement" of \(G\).)
  3) Show that there exists a universal constant \(C\) such that for every pair of natural numbers \(v,e\) with \(4v\leq e \leq {v \choose 2}\) there exists a graph \(G\) with \(v(G)=v, e(G)=e\) and \(\text{cr}(G) \leq C \cdot e^3 / v^2\).


• 29 October: We covered classic quantitative versions of the graph form of Ramsey's Theorem, including the Erdos-Szekeres recurrence, the Erdos lower bound, Spencer's improvement via the Lovasz Local Lemma, Goodman's formula, and the Frankl-Wilson constructive lower bound. Sources of the exposition include the first two lectures of Conlon's course and Section 13.7 of Jukna (2nd ed).


• 5 November: Wrapped up discussion of graph Ramsey numbers, continued to full form of Ramsey's theorem, reformulated in terms of hypergraphs. Proved Erdos-Rado recurrence for 3-uniform, discussed Erdos-Hajnal-Rado conjecture, proved "stepping-up" lemma.
  Homework: At the start of the Nov 12 lecture, please hand in your solutions to the following exercises:
  1) \(R(\ell_1+1,\dots,\ell_r+1) \le 2 + \sum_{i=1}^r(R(\ell_+1,\dots,\ell_i,\dots,\ell_r+1)-1)\).
  2) Every set of five points in \(\mathbb{R}^2\) in general position has a subset forming a convex quadrilateral.
  3) Show Spencer's lower bound (\(e\binom{\ell}{2}\binom{n-2}{\ell-2}2^{1-\binom{\ell}{2}} < 1 \implies R(\ell) > n\)) implies that \(R(\ell) > (\sqrt{2}/e+o(1))\ell\cdot 2^{\ell/2}\).
  4) \(R^{(k)}(\ell) \le 2^{\binom{R^{(k-1)}(\ell-1)}{k-1}}\).
  5) \(\exists c>0 : R^{(3)}(\ell) > 2^{c\ell^2}\).
  


• 12 November: Covered the Mycielski construction (treatment followed D.B.West, introduction to graph theory, pages 205-206) and Erdos' probabilistic construction of graphs with high girth and high chromatic number (A+S p41)


• 19 November: Start of additive combinatorics. Schur's theorem and proof by Ramsey number. Upper bounds on size of largest sum-free sets, using Kneser's theorem. Proof of Kneser's. Chat about lower bounds on size of largest sum-free sets. Hales-Jewett theorem and VdW's theorem as a corollary. Statement and discussion of density Hales-Jewett, including polymath1. Sources include Jukna 25.3, 26.1, Tao-Vu 6, and the internets.
  Homework: At the start of the Nov 26 lecture, please hand in your solutions to the following exercises:
  1) Let \(G_1\) be the graph with a single vertex. Construct \(G_i, i \ge 2\) as follows. Start with the disjoint union of \(G_1,\dots,G_{i-1}\). Then, for every tuple \(s = (v_1,\dots,v_{i-1})\) (with \(v_1\in V(G_1), \dots, v_{i-1}\in V(G_{i-1})\)), add a new vertex joined to every vertex in \(s\). (So \(G_2\) consists of a single edge and \(G_3\) is a 5-cycle.) Show \(G_i\) is triangle-free and has chromatic number \(i\).
  2) Show, using Schur's, that if \(\mathbb{Z}^+\) is \(r\)-coloured, then there are infinitely many monochromatic \(\{x,y,x+y\}\). Conversely, show, by assuming the last statement, that Schur's theorem holds.
  3) Show \(\alpha(\mathbb{Z}_{p^n}) = \frac{p+1}{3p}|\mathbb{Z}_{p^n}|\), if \(p\) is an odd prime and \(p = 3k+2\).
  4) If \(\mathbb{Z}^+\) is \(2\)-coloured, then does one colour class necessarily have an infinitely long arithmetic progression? Justify.
  5) (Solution to be given at the beginning of next class.) Given \(B\subseteq \mathbb{Z}^m\), another subset \(A\subseteq\mathbb{Z}^m\) is a homothet of \(B\) if there exist \(a\in\mathbb{Z}^m\) and \(\lambda\in\mathbb{Z}^+\) such that \(A = a + \lambda B\). If \(\mathbb{Z}^m\) is \(r\)-coloured, then there is guaranteed to be a monochromatic homothet of any finite set \(B\subseteq \mathbb{Z}^m\).
  


• 26 November: Discussion of Szemeredi's theorem and the Erdos-Turan conjecture (including statement of results of Sanders and Behrend). Statement of regularity lemma. Triangle removal lemma. Proof of Roth's theorem with triangle removal. Borrowed from here.
  There is no homework 6, except possibly as optional.


• 3 December: Proof of Szemeredi regularity lemma based on previously linked notes (modulo change of notation and healthy exchange of small arithmetic typos).


• 10 December: The final exam!