Master course:
Probabilistic and extremal combinatorics
Fall 2016
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 Fridays 10:00 - 12:45 at the UvA campus in Amsterdam, in room SP C1.112.
The first lecture is in week 38, on Friday 23 September 2013.
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 40% of the final grade.
A list of examinable topics is available.
We also have available:
Note that there are some minor differences between the material covered this year and in previous years. Also, the solutions we provide do not always correspond to how the answers should have been written on the exam to get full marks.
The exam of 13 January 2017 and the solutions are now available.
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
- 23 September: General introduction to extremal combinatorics and the probabilistic method. Erdos-Ko-Rado theorem (Alon+Spencer page 13). 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).
- 30 September: Kahn-Kalai's counterexample to Borsuk's conjecture
(treatment followed Matousek, "Thirty-three miniatures", pages 61-65).
Hadwiger-Nelson problem and exponential lower bound on the chromatic number of \(d\)-dimensional space (Jukna exercises 14.25, 14.25).Two-distance sets (Jukna page 177).
Homework: At the start of the 14 October lecture, hand in your solutions to the following exercises. Only hard copy, delivered at the lecture is accepted. (E-mailing solutions is absolutely not accepted.):
1) Prove that in every \(2\)-coloring of the edges of \(K_6\) there is a monochromatic triangle.
2-a) Show that a \(1\)-distance set in \({\mathbb R}^d\) has at most \(d+1\) elements, and show this is sharp. (In all dimensions \(d\).)
2-b) Give an example of a \(2\)-distance set in \({\mathbb R}^d\) with \({d+1 \choose 2}\) elements. (In all dimensions \(d\).)
3) Show that \(\chi({\mathbb R}^2) \leq 7\) by filling in the details of the sketch given in the lecture (or otherwise).
4) Show that \(\chi({\mathbb R}^d) \leq (4d)^{d/2}\) by periodically colouring a suitable dissection or otherwise. (In all dimensions \(d\).)
5) Finish the proof that \(\chi({\mathbb R}^d)\) is exponentially large. That is, show that there exists \(\gamma > 1\) such that \(\chi({\mathbb R}^d) > \gamma^d\) for all \(d\geq 1\). (So not just if \(d\) is of the form \(d=4p\) with \(p\) a large prime. You may assume that the statement holds for all \(d\) of the form \(d=4p\) with \(p\) a large prime.)
Hint: You may use Betrands postulate, stating that for every \(n\geq 1\) there exists a prime \(p\) such that \(n < p \leq 2n\), without proof.
6) Let \(p_1,\dots,p_n \in {\mathbb R}^d\) be such that the pairwise distances between them take at most \(s\) values. Prove that \(n \leq {d+s+1 \choose s}\).
7) Watch n is a number. - 7 October: Statement of Ramsey's theorem. Quantitative versions of 2-colour graph form, including the Erdos-Szekeres upper bound, the Erdos lower bound. Statement of Lovasz Local Lemma and the improved lower bound of Spencer. Discussion of state of the art. Constructive lower bound via a modular form of Frankl-Wilson (Section 13.7 of Jukna). Cartoon summary.
- 14 October:
Mention of r-colour graph Ramsey numbers. Focus on hypergraph
(2-colour) Ramsey numbers. Erdos-Rado bound for 3-uniform case.
Discussion of state of the art and Erdos-Hajnal-Rado conjecture.
Erdos-Hajnal stepping up lemma.
Homework: At the start of the 28 October lecture, 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 general position in \(\mathbb{R}^2\) 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))k\cdot 2^{\ell/2}\) as \(\ell\to\infty\).
4) Assume the followiing: \(\forall p\in(0,1)\) and \(n\in Z^+\), \(R(\ell_1,\ell_2) > n-\binom{n}{\ell_1}p^{\binom{\ell_1}{2}}-\binom{n}{\ell_2}(1-p)^{\binom{\ell_2}{2}}\). Use it to show there is some \(c>1\) for which \(R(3,\ell) = \Omega(\ell^c)\) as \(\ell\to\infty\).
5) For any graph on \(n\) vertices, the number of copies of \(K_3\) plus the number of copies of \(\overline{K_3}\) is at least \(n(n-1)(n-5)/24\). Hint: sum over all vertices and then optimise.
6) Use the constructive Ramsey graph given in lecture to certify that \(R(\ell,\ell) = \ell^{\Omega(\log\ell/\log\log\ell)}\) as \(\ell\to\infty\).
7) \(R^{(k)}(\ell,\ell) \le 2^{\binom{R^{(k-1)}(\ell-1,\ell-1)}{k-1}}\).
8) There exists \(c>0\) such that \(R^{(3)}(\ell)>2^{c\ell^2}\). - 21 October: 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). Introduction to crossing number, crossing number inequality (Jukna Chapter 18).
- 28 October: General lowerbound for \(R(l_1,l_2)\) by by the deletion method. Proof for \(l_1 = 3\). Erdös proof for the lowerbound \(R(3,l) = \Omega(l^2/\log(l)^2)\). Mentioned results by Graver, by Ajtai, Komlós and Szemerédi 1980 and the result by Kim from 1995. (Guest lecture by René Conijn)
- 4 November:
Proof of Szemeredi-Trotter. (Jukna chapter 18) Upper bound on unit distances (not in either book, a proof can be
found here).
Turán's theorem (A+S page 95, or Jukna pages 56-59).
Erdos-Stone-Simonovits theorem (minus one lemma that still needs to be covered). This is not in either book, but you can for instance find a proof close to the
one presented in the lecture here
Homework: At the start of the 18 November lecture, 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 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\).
3) Let \(L\) be a finite set of lines in the plane, such that no three of them pass through a common point (no point is on three lines). Associate a (planar) graph \(G\) with \(L\) in the obvious way: the vertices are the intersection points of the lines, and there is an edge between two intersection points \(p,q\) if they are consecutive on some line. Show that \(\chi(G) \leq 3\).
4) Prove that if \(P\) is a set of points in the plane, \(C\) a set of equal radius circles and \(I(P,C)\) denotes the number of "incidences", i.e. pairs of a point \(p \in P\) and a circle \(c\in C\) such that \(p\) lies on \(c\), then \( I(P,C) = O\left( (|C||P|)^{2/3} + |P| + |C| \right)\).
5) 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.)
- 11 November: No lecture this week!
- 18 November: Last bit of Erdos-Stone-Simonovits. Start of additive number theory. Schur's theorem and proof by
multicolour Ramsey number. Upper bounds on size of largest sum-free
sets, using Kneser's theorem. Proof of Kneser's. Lower bounds on size
of largest sum-free sets, Alon+Kleitman proof, and discussion of
sharpness. Sources include Jukna 25.3, Tao-Vu 6, Alon-Spencer 1.4 and
the internet.
Homework: At the start of the 2 December lecture, hand in your solutions to the following exercises.
1) Show the following are equivalent: (a) Schur's theorem for \(r=2\); (b) if \(\mathbb Z^+\) is 2-coloured, then there are infinitely many monochromatic \(\{x,y,x+y\}\).
2) Show \(\alpha(\mathbb{Z}_{p^n}) = \frac{p+1}{3p}|\mathbb{Z}_{p^n}|\), if \(p\) is an odd prime and \(p=3k+2\).
3) Use Kneser's to show the following. If \(p\) is prime and \(A,B\) non-empty subsets of \(\mathbb{Z}_p\), then \(|A+B| \ge \min\{p,|A|+|B|-1\}\). Use this statement in turn to prove the following. If \(A_1,\dots,A_{p-1}\) are 2-element subsets of \(\mathbb{Z}_p\), then \(A_1+\cdots+A_{p-1}=\mathbb{Z}_p\).
4) If \(\mathbb{Z}^+\) is 2-coloured, does one colour necessarily have an infinitely long arithmetic progression? Justify.
5) Prove the Van der Waerden number \(W(2,3)=9\) (so 2 colours, AP length 3). - 25 November: Statement of Van der Waerden's theorem. Proof of 2-colour 3AP statement. Statement of Hales-Jewett theorem. Proof that HJ implies VdW. Discussion of density Hales-Jewett theorem and polymath1. Sources include Jukna 26.1 and the internet.
- 2 December: Introduction to positional games, and hex in particular. Lovasz Local Lemma. (A+S Sec 5.1). Application of LLL to latin transversals (A+S sec 5.6).
- 9 December:
Discussion of Szemeredi's theorem and the Erdos-Turan conjecture
(including statement of results of Sanders, Elkin, Behrend). Statement
of regularity lemma. Triangle removal lemma. Proof of Roth's theorem
with triangle removal. Proof of triangle removal with regularity.
Homework: At the beginning of next lecture, please hand in solutions to the following exercises, with the solutions to exercises 1 and 2 submitted separately from the solutions to exercises 3 and 4:
1) In the lectures it was shown that one of the two players of the board game Hex has a winning strategy. (See here.) Deduce that on an \(n\times n\) board, the first player has a winning strategy, for all \(n)\). That is, solve the second exercise in the linked file. You can ignore the first exercise in the linked file. (Hint : "strategy stealing")
2) Let \(G = (V, E)\) be a simple graph and suppose each \(v \in V\) is associated with a set \(S(v)\) of colors of size at least \(1000d\), where \(d > 1\). Suppose, in addition, that for each \(v \in V\) and \(c \in S(v)\) there are at most \(d\) neighbors \(u\) of \(v\) such that \(c \in S(u)\). Prove that there is a proper coloring of G assigning to each vertex \(v\) a color from its class \(S(v)\).
3) A strong matching is a set \(M\) of edges such that for any \(m_1,m_2\in M\) there is no edge in the graph between an endpoint of \(m_1\) and an endpoint of \(m_2\). Prove that, for any graph on \(n\) vertices whose edges are the union of \(n\) strong matchings, the number of edges is \(o(n^2)\) as \(n\to\infty\). (Hint: Use regularity.)
4) Use the statement in exercise 3 to prove the following. For any \(\varepsilon > 0\), there exists \(n_0\) such that if \(n\ge n_0\) then every subset of \([n]^2\) of size \(\varepsilon n^2\) contains a triple of the form \((x,y),(x,y+d),(x+d,y)\) where \(d\ne 0\). Hint: In some auxiliary bipartite graph based on the chosen points of \([n]^2\), consider the equivalence classes formed by summing coordinates.