Author: dgalvin1

We’ve now seen Ramsey’s theorem, which concerns finding monochromatic cliques in graphs, and a generalization to hypergraphs (\(p\)-tuples). Now we move on Van der Waerden’s theorem, a somewhat more difficult result concerning finding monochromatic arithmetic progressions in colorings of the natural numbers. This is Chapter 3 of Reimann and Katz; we’ll go back to Chapter 2, on infinite Ramsey’s theorem, later.

The text doesn’t give a complete, formal proof of finite Van der Waerden. Instead, it discusses a few instances of showing the existence of some small finite Van der Waerden numbers, in a way that (hopefully) gives a good intuition for how a full proof should go.

• Everyone should read Chapter 3, through at least to the middle of page 94 (ignore the occasional reference back to Chapter 2).
•  Everyone should think about Exercise 3.2 (construction of a 2-coloring of \({\mathbb N}\) that fails to have an infinite monochromatic arithmetic progression). Greyson and Joe can tell us about this.
• Here’s another exercise that everyone can think about, and I’ll throw it open to the group to discuss: is there a “soft” way to prove the existence of a 2-coloring of \({\mathbb N}\) that fails to have an infinite monochromatic arithmetic progression, without actually explicitly exhibiting such a coloring? Hint: how does the number of infinite arithmetic progression compare to the number of natural numbers?
• Ted and Anthony can go over the explanation of why the existence of \(W(k,2)\) for every \(k\) implies the existence of  \(W(k,r)\) for every \(k\) and \(r\) (observation 3.1)
• Luca and Ryan can take us through a proof that \(W(3,2)\leq 325\). (Reimann and Katz go through this quite slowly and discursively; Luca and Ryan, in presenting this bound you can assume that we have all read the long discussion, and so you can be more concise. Start with the hypothesis that \(325\) works, and go through the four steps outlined on page 93, to verify that hypothesis. Pictures will help!)

 

Note: I won’t have access to my office next week, so I’ll have no blackboard. So when making a presentation you should use some kind of slides — powerpoint or (preferably, since it is optimized for math) Beamer — that you can share on the screen; or use an app that allows you to share a (virtual) blank page that you can write on in a way that everyone can see.

I’ll begin by discussing the state of the art for diagonal Ramsey numbers. Then we will go on to full-blown Ramsey’s theorem. This is Section 1.6; everyone should read this.

• Section 1.6 starts with a treatment of the case of coloring triples with 2 colors. Bailee and Sean can present on this.
• The section continues with an outline of the induction argument that allows us to extend to sets larger than triples (heading “From triples to \(p\)-tuples”), still with two colors.  Casey and Nick can present on this.
• The section ends with a proof for many colors (heading “A different proof”). Colin and Alex can present on this.

Here’s a fun exercise to think about. Use Ramsey’s Theorem (you’ll need to use the more general statement about coloring \(p\)-tuples, rather than the weaker one about coloring pairs) to prove the following statement: for every \(k\) there is \(N(k)\) such that however \(N(k)\) points are put on a plane, with no three in a line, there is some \(k\) points among the \(N(k)\) that form the vertices of a convex \(k\)-sided polygon.

• Everyone should have a look at Proposition 1.25 (improving the Greenwood and Gleason upper bound on off-diagonal Ramsey numbers by 1, in certain circumstances). We won’t spend much time on this, unless people have questions. It is needed in the proof of Proposition 1.26, so we should at least know the statement and have an idea of its proof.
• Joe will present two arguments for a couple of small exact Ramsey numbers (Proposition 1.26 and 1.27).
• Everyone should read through propositions 1.26 and 1.27, and the discussion afterwards; I’ll make some further comments on this.
• Everyone should think about how a proof for Theorem 1.28 should go; Anthony will tell us about it.
• Ryan will present the proof of Theorem 1.29 (a lower bound for the diagonal Ramsey numbers). Everyone should read this proof, too.

• We’ll start with Greyson presenting the proof of Theorem 1.24 (a binomial coefficient upper bound on the off-diagonal Ramsey numbers).
• Everyone should have a look at Proposition 1.25 (improving the Greenwood and Gleason upper bound on off-diagonal Ramsey numbers by 1, in certain circumstances).
• Luca will present two arguments for a couple of small exact Ramsey numbers (Proposition 1.26 and 1.27); this outlining the proof of Proposition 1.25.
• Everyone should read through propositions 1.26 and 1.27, and the discussion afterwards; I’ll make some further comments on this.
• The book introduces a couple of black boxes. The first is a coloring of a graph on 13 vertices that has neither a red \(K_3\) nor a blue \(K_5\) (arrange the 23 vertices in a circle. Use a red edge to join each vertex to its neighbors immediately to the right and immediately to its left, as well as to the vertices 5 to its right and 5 to its left. All other edges are blue). We’ll talk about how to efficiently verify that this coloring does what it claims to do. The second black box is the Paley graph of order 17, which is claimed not to have a red \(K_4\) nor a blue \(K_4\). We’ll discuss verifying this, too.
• Everyone should think about how a proof for Theorem 1.28 should go.
• Ted will present the proof of Theorem 1.29 (a lower bound for the diagonal Ramsey numbers). Everyone should read this proof, too.

Here’s the plan for Tuesday, June 16, for the Red group:

• Everyone:
  * Re-read the proof of Theorem 1.16 — the basic proof strategy will re-appear in later proofs of more expansive Ramsey-type theorems. It will be very helpful to start the proof by taking (with hindsight) \(N=2^{2k}\); that way, once you have (once) verified that \(\lceil (2^m-1)/2 \rceil = 2^{m-1}\) for any natural number \(m\), you get to avoid all the messy algebra at the end of the proof.
  * Do exercise 1.18 (which is essentially the Bolzano-Weierstrass theorem for finite sequences).
  * Think about the following much harder variant of exercise 1.18: part of that exercise asks you to show that there is a sequence of reals of length \(k^2\) that has neither an increasing nor a decreasing subsequence of length \(k+1\). Show that this is best possible, that is, show that every sequence of reals of length \(k^2+1\) has either an increasing or a decreasing subsequence of length \(k+1\).
  * Study the proof of Theorem 1.19 (Ramsey’s theorem for colouring pairs, with many colors).
  * Read Section 1.4, through at least to the proof of Theorem 1.24.
• Individual assignments:
  * For both parts of exercise 1.18, and the harder variant, I’ll throw it open to anyone who wants to volunteer ideas.
  * Proof of Theorem 1.19 (Ramsey’s theorem about finding a monochromatic \(k\)-clique, when colouring with \(r\) colours): Bailee.
  * Exercise 1.20 (Schur’s theorem, a cute application of Ramsey’s theorem): Casey.
  * Theorem 1.23 (another proof of Ramsey’s theorem, that uses “off-diagonal” Ramsey numbers): Colin.
  * Theorem 1.24 (getting better upper bounds for Ramsey numbers, using the result of Theorem 1.23): Greyson. (We may not get to this on Tuesday).

Here’s the plan for Tuesday, June 16, for the Blue group:

• Everyone:
  * Re-read the proof of Theorem 1.16 — the basic proof strategy will re-appear in later proofs of more expansive Ramsey-type theorems. It will be very helpful to start the proof by taking (with hindsight) \(N=2^{2k}\); that way, once you have (once) verified that \(\lceil (2^m-1)/2 \rceil = 2^{m-1}\) for any natural number \(m\), you get to avoid all the messy algebra at the end of the proof.
  * Do exercise 1.18 (which is essentially the Bolzano-Weierstrass theorem for finite sequences).
  * Think about the following much harder variant of exercise 1.18: part of that exercise asks you to show that there is a sequence of reals of length \(k^2\) that has neither an increasing nor a decreasing subsequence of length \(k+1\). Show that this is best possible, that is, show that every sequence of reals of length \(k^2+1\) has either an increasing or a decreasing subsequence of length \(k+1\).
  * Study the proof of Theorem 1.19 (Ramsey’s theorem for colouring pairs, with many colors).
  * Read Section 1.4, through at least to the proof of Theorem 1.24.
• Individual assignments:
  * For both parts of exercise 1.18, and the harder variant, I’ll throw it open to anyone who wants to volunteer ideas.
  * Proof of Theorem 1.19 (Ramsey’s theorem about finding a monochromatic \(k\)-clique, when colouring with \(r\) colours): Sean.
  * Exercise 1.20 (Schur’s theorem, a cute application of Ramsey’s theorem): Nick.
  * Theorem 1.23 (another proof of Ramsey’s theorem, that uses “off-diagonal” Ramsey numbers): Henry.
  * Theorem 1.24 (getting better upper bounds for Ramsey numbers, using the result of Theorem 1.23): Alex. (We may not get to this on Tuesday).

Here’s the plan for Friday for the Red group:

• Everyone: Read Section 1.3; do exercises 1.14 (easy), 1.18 and 1.20 (both moderate). You could also think about the following much harder variant of exercise 1.18: part of that exercise asks you to show that there is a sequence of reals of length \(k^2\) that has neither an increasing nor a decreasing subsequence of length \(k+1\). Show that this is best possible, that is, show that every sequence of reals of length \(k^2+1\) has either an increasing or a decreasing subsequence of length \(k+1\).
• Greyson: present exercise 1.8.
• Bailee: present a proof that the complement of a disconnected graph must be connected.
• Ted: present a proof that a graph is bipartite iff it has no odd cycle.
• Casey: present exercise 1.12.
• Colin: present exercise 1.13.
• Luca: present the proof of Theorem 1.16.

Here’s the plan for Thursday for the Blue group:

• Everyone: Read Section 1.3; do exercises 1.14 (easy), 1.18 and 1.20 (both moderate). You could also think about the following much harder variant of exercise 1.18: part of that exercise asks you to show that there is a sequence of reals of length \(k^2\) that has neither an increasing nor a decreasing subsequence of length \(k+1\). Show that this is best possible, that is, show that every sequence of reals of length \(k^2+1\) has either an increasing or a decreasing subsequence of length \(k+1\).
• Henry: present exercise 1.10.
• Joe and Anthony: present these two exercises — show that if G is not connected, then its complement is connected, and show that a graph is bipartite if and only if it has no odd-length cycles.
• Nick: present exercise 1.12.
• Alex: present exercise 1.13.
• Ryan: present proof of Theorem 1.16.

Before the first meeting, you should read up to the end of Section 1.2. Section 1.1 introduces basic terminology about partitions, and introduces the pigeon-hole principle, while Section 1.2 introduces basic terminology about graphs.

It is always good to have pen and paper to hand when reading a math book, so that you can work through examples, and verify for yourself claims made by the author. It is also very helpful to do frequent exercises. As you read Section 1.1, you should think about the following exercises, which we will discuss at the first meeting:

• (1) Exercise 1.4. This and the next two exercises are well-known, and you may have seen them before. As you work on them now, try to focus on solutions that make clear the utility of the pigeon-hole principle: identify clearly what your pigeon-holes are, what your pigeons are, and why the conclusion that there must be two pigeons in the same pigeon-hole solves the problem.
• (2) Related to Exercise 1.4: show that whenever \(n+1\) numbers are chosen from \(\{1,…,2n\}\), some two of them must be relatively prime (have no common factors).
• (3) Also related to Exercise 1.4: show that whenever \(n+1\) numbers are chosen from \(\{1,…,2n\}\), some two of them must have the property that one divides the other.
• (4) (Harder) Let \(m\) be an irrational number between \(0\) and \(1\). Let \(n\) be any natural number. Show that there is a rational number \(p/q\) with \(p, q\geq 1\), \(p < q\), and \(p\), \(q\) having no common factors, such that \(\left|m-\frac{p}{q}\right| \leq \frac{1}{qn}\). (Hint: Think about the numbers \(m, 2m, 3m, \ldots, (n+1)m\). These \(n+1\) irrational numbers each have a fractional part that is between \(0\) and \(1\), so some two of them must have fractional parts that are close to each other.)
• (5) (A cute application of (4)): An infinite orchard has trees arranged in a perfect square grid, with one tree at the center removed. Prove that no matter how thin the trees are, if you are standing at the center then no matter which direction you look, your view to infinity will be obstructed by a tree. (If this is a little vague, here’s a more precise formulation: A lattice point is a point in \({\mathbb R}^2\) with integer coordinates. Suppose that centered at every non-zero lattice point in \({\mathbb R}^2\), a disk of radius \(r\) is drawn. Show that no matter the value of \(r\), every ray through the origin eventually meets one of the discs.)   

And as you read Section 1.2, you should think about the following exercises:

• (6) Exercise 1.8.
• (7) Show that if G is not connected, then its complement is connected.
• (8) Show that a graph is bipartite if and only if it has no odd-length cycles (this is surprisingly tricky).
• (9) Exercise 1.12.
• (10) Exercise 1.13.

Based on availability (constrained by us being in many different times zones), and because of the large number of participants, it seems best to split into two groups. 

Conforming to a long-standing tradition in Ramsey theory, that whenever an object is to be colored with two colors, those colors are red and blue, the two groups will be Red and Blue.

Red: Casey, Greyson, Colin, Bailee, Luca, Ted, meeting Tuesday 9.30-10.45, and (maybe not every week) Friday 9.30-10.45.

Blue: Ryan, Henry, Nicholas, Joe, Anthony, Sean, Alex, meeting Tuesday 3.30-4.45, and (maybe not every week) Thursday 3.30-4.45. 

All meetings will be at https://notredame.zoom.us/j/95453149367, and we will start this coming Tuesday, June 9.