[Computational Complexity] A Complete History of the LVDW conjecture
- View SourceWhen 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 fc is the following true: for all k, for all c, for all coloring c-colorings of (k,k+1,k+2,...) there exists a fc-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