FOM: 37:Adjacent Ramsey Theory/more

[Harvey Friedman]

This is the 37th in a series of self contained postings to fom covering a
wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98
10:53PM
16:Logical Equations, etc.  4/17/98  1:25PM
16':Errata  4/28/98  10:28AM
17:Very Strong Borel statements  4/26/98  8:06PM
18:Binary Functions and Large Cardinals  4/30/98  12:03PM
19:Long Sequences  7/31/98  9:42AM
20:Proof Theoretic Degrees  8/2/98  9:37PM
21:Long Sequences/Update  10/13/98  3:18AM
22:Finite Trees/Impredicativity  10/20/98  10:13AM
23:Q-Systems and Proof Theoretic Ordinals  11/6/98  3:01AM
24:Predicatively Unfeasible Integers  11/10/98  10:44PM
25:Long Walks  11/16/98  7:05AM
26:Optimized functions/Large Cardinals  1/13/99  12:53PM
27:Finite Trees/Impredicativity:Sketches  1/13/99  12:54PM
28:Optimized Functions/Large Cardinals:more  1/27/99  4:37AM
28':Restatement  1/28/99  5:49AM
29:Large Cardinals/where are we? I  2/22/99  6:11AM
30:Large Cardinals/where are we? II  2/23/99  6:15AM
31:First Free Sets/Large Cardinals  2/27/99  1:43AM
32:Greedy Constructions/Large Cardinals  3/2/99  11:21PM
33:A Variant  3/4/99  1:52PM
34:Walks in N^k  3/7/99  1:43PM
35:Special AE Sentences  3/18/99  4:56AM
35':Restatement  3/21/99  2:20PM
36:Adjacent Ramsey Theory  3/23/99  1:00AM

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of self contained postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

FAVORITE SELF CONTAINED POSTINGS: 21, 25, 27, 31, 32, 34, 35', 37.

We have added Theorems 6 and 7 with 2 colors to posting 36. So this
supersedes 36.

ADJACENT RAMSEY THEORY
by
Harvey M. Friedman
March 25, 1999

We start with the following easy consequence of the infinite Ramsey theorem.

THEOREM 1. Let k,r >= 1 and F:Z+^k into [0,r]. There exists x_1 < ... <
x_k+1 such that F(x_1,...,x_k) = F(x_2,...,x_k+1).

We consider (x_1,...,x_k) and (x_2,...,x_k+1) to be "adjacent."

Note that this is logically "simpler" than the infinite Ramsey theorem in
that its conclusion is purely existential.

And also consider the following easy consequence of the finite Ramsey theorem.

THEOREM 2. For all k,r >= 1 there exists n in Z+ such that the following
holds. Let F:[1,n]^k into [1,r]. There exists x_1 < ... < x_k+1 such that
F(x_1,...,x_k) = F(x_2,...,x_k+1).

We now define the adjacent Ramsey numbers as follows. R(k,r) is the least n
such that Theorem 2 holds.

THEOREM 3. For all k >= 1, R(k,2) = 2k+1.

What about R(k,r)? Let 2^[b](k) be an exponential stack of b 2's with k on
top. THus 2^[1](k) = 2^k.

THEOREM 4. Let b >= 1. For all sufficiently large k, R(k,3) > 2^[b](k).

It looks like we can give a reasonable bound on how large k has to be in
Theorem 4 as a function of k. However, to get a really good bound, we need
to do further investigation.

THEROEM 5. For all b >= 1 there exists k such that the following holds. For
all sufficiently large r >= 1, R(k,r) > 2^[b](r).

Again, it looks like we can give a reasonable bound k in terms of b and how
large r has to be in terms of b. This also needs further investigation.

But the main point is that for 3 colors (r = 3), this most bare bones form
of Ramsey's theorem already has an iterated exponential blowup.

We can also use two colors if we look for adjacent triples. Thus we
consider the following easy consequence of the usual infinte Ramsey theorem
for 2 colors:

And so we also consider the following easy consequence of the finite Ramsey
theorem.

THEOREM 6. For all k,r >= 1 there exists n in Z+ such that the following
holds. Let F:[1,n]^k into [1,r}. There exists x_1 < ... < x_k+2 such that
F(x_1,...,x_k) = F(x_2,...,x_k+1) = F(x_3,...,x_k+2).

And we define the triple adjacent Ramsey numbers as follows. R'(k,r) is the
least n such that Theorem 6 holds.

THEOREM 7. Let b >= 1. For all sufficiently large k, R'(k,2) > 2^[b](k).