Second meeting of Week 4

We’ll go back now to Chapter 2, on infinite Ramsey’s theorem, and its connection (via Konig’s tree lemma) to finite Ramsey’s theorem.

Everyone should read Chapter 2, through at least to the middle of page 48. There’s one substantial theorem in this span, namely Theorem 2.1 (although it’s not really too different from Theorem 1.31, finite Ramsey’s theorem, and is in fact a little easier, since one has much less “bookkeeping” to do to make the proof work. Section 2.2 through the middle of page 48 is mostly definitions (of partially ordered sets, tree orders, et cetera.).

Theorem 2.1 is proven by induction, with the base case being the obvious infinite pigeon-hole principle — if infinitely many pigeons arrange themselves among only finitely many pigeon holes, then at least one of the pigeon-holes will end up with infinitely many pigeons. I think it’s much more instructive to start with the base case \(p=2\). So: Greyson and Joe can present the proof of the following (the case [/latex]p=2[/latex] of Theorem 2.1): if the edges of an infinite complete graph are colored with finitely many colors, then the graph has an infinite complete subgraph all of whose edges have the same color. Then Luca and Sean can present the induction step that completes the proof of Theorem 2.1.

Then we’ll move onto to partial orders (to lay the groundwork for deducing finite results from infinite ones). As I said earlier, everyone should read through all the background on partial orders and tree-orders, and we can discuss and points that are confusing during the live meeting. Bailee and Anthony can first explain what it means for a partial order to be a tree (in the partial order sense), and then present Exercise 2.3 (connecting this concept to trees in the graph-theoretic sense); then Ted and Ryan can present Konig’s lemma (Theorem 2.6).

 

Tuesday of week 4 – red group

For Tuesday, everyone should read up through the end of Section 3.1, and do all the exercises. In general when reading mathematics it is a good idea to have paper to hand, to draw pictures and verify claims. This section is one of those situations where it is not a good idea — it is absolutely essential.

At the end of last time, we saw the “AP focussing” argument used to show that for each \(k\), \(W(k,2)\) exists, assuming that \(W(k-1,r)\) exists for every \(r\). Next, we will move onto to the argument that \(W(3,3)\) is finite. This requires a new ingredient, because now we need to focus three monochromatic APs of length 2 (all of different colors) on a single, final focal point. Casey can present this.

The argument that \(W(3,3)\) is finite generalizes to show that \(W(3,r)\) is finite, for every \(r\). Ted can present this.

The last special case we’ll consider is \(W(4,3)\) (requiring focussing three monochromatic APs of length 3, all of different colors, on a single, final focal point). Colin can present this.

We should now be in a position to understand what’s going on in the proof of the general statement, that for each particular choice of \(k\) and \(r\), \(W(k,r)\) is finite (under the inductive hypothesis that \(W(k-1,r’)\) is finite for every \(r’\)). Bailee can present this.

Tuesday of Week 4 — blue group

For Tuesday, everyone should read up through the end of Section 3.1, and do all the exercises. In general when reading mathematics it is a good idea to have paper to hand, to draw pictures and verify claims. This section is one of those situations where it is not a good idea — it is absolutely essential.

At the end of last time, we saw the “AP focussing” argument used to show that \(W(3,2)\) exists. To make sure that we fully understand that argument before moving on, we should start on Tuesday by using the same argument to show that for each \(k\), \(W(k,2)\) exists, assuming that \(W(k-1,r)\) exists for every \(r\). I’ll  present this (it is very quick — a valid upper bound is easy to justify using the same process that justified \(W(3,2)\leq 5\cdot 65\). The right picture fully explains the proof).

Next, we will move onto to the argument that \(W(3,3)\) is finite. This requires a new ingredient, because now we need to focus three monochromatic APs of length 2 (all of different colors) on a single, final focal point. Nick can present this.

The argument that \(W(3,3)\) is finite generalizes to show that \(W(3,r)\) is finite, for every \(r\). Sean can present this.

The last special case we’ll consider is \(W(4,3)\) (requiring focussing three monochromatic APs of length 3, all of different colors, on a single, final focal point).  Alex can present this.

We should now be in a position to understand what’s going on in the proof of the general statement, that for each particular choice of \(k\) and \(r\), \(W(k,r)\) is finite (under the inductive hypothesis that \(W(k-1,r’)\) is finite for every \(r’\)). Henry can present this.

Reading for the second meeting of week three

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

 

Reading/exercises for Tuesday of Week 3

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.

Thursday of week 2, blue group

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

Friday of week 2, red group

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

Tuesday of week 2, red group

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

Tuesday of Week 2, Blue group

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

Red group — Friday 9.30 week 1

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.