FOM: 37:Adjacent Ramsey Theory/more
friedman at math.ohio-state.edu
Wed Mar 24 23:45:25 EST 1999
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.
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
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
Also, my series of self contained postings (only) is archived at
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
ADJACENT RAMSEY THEORY
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^(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 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).
More information about the FOM