When you first make a conjecture you don't know if it will
be important or interesting or both or neither.
In the case below it was solved quickly,
the answer was not interesting, and I doubt
anymore will come of it. But, I did get a blog posting
and some nice exercises for a class out of it.

**Recall**: VDW theorem is the following

For all k, for all c, for all c-colorings of N (the naturals)
there exists a monochromatic arithmetic progression.

I was looking at a variant of this:

**Definition:** An arithmetic sequence is *large*
if it is larger than its least element.
The following are large arithmetic sequences:
(1),
(2, 10),
(4,5,6,7).
The following is NOT large arithmetic sequences:
(100,102,104,...,118).

Note that for any c-coloring of N there is (trivially) a large monochromatic
AP: just take (1).
But what if we start coloring the naturals starting at k?

LVDW CONJECTURE: for all k, for all c, for all coloring c-colorings of
(k,k+1,k+2,...) there exists a large monochromatic AP.

Why do I care? There is a
Large Ramsey Theorem
which is similar and is true.
It is proven from the *infinite Ramsey Theorem*.
It is of interest because this theorem is not provable in
Peano Arithmetic (the associated functions grow faster than any
function definable in PA). This leads to the following questions:
I was hoping that LVDW CONJECTURE was true but ind of PA.

Alas, Andy Parrish (was Brilliant ugrad at UMCP in CS, is now
brilliant grad at UCSD in math) proved LVDW CONJECTURE false.
I leave it as an exercise.

There is a question that remains, though it just be equivalent
to getting bounds on VDW numbers.

**Definition:** Let g:N &rarr N
An arithmetic sequence is *g-large*
if it is larger than g of its least element.

For which sequences of functions f_{c} is the following true:
for all k, for all c, for all coloring c-colorings of
(k,k+1,k+2,...) there exists a f_{c}-large monochromatic AP.

We know there is such a sequence by the ordinary VDW theorem (exercise).

--

Posted By GASARCH to Computational Complexity at 1/12/2009 09:47:00 AM