Timeline for Density in van der Waerden's theorem
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 9, 2012 at 16:37 | vote | accept | Pace Nielsen | ||
| Apr 7, 2012 at 3:42 | answer | added | domotorp | timeline score: 6 | |
| Jan 28, 2012 at 4:14 | comment | added | Kevin P. Costello | It's not quite the same problem, but you may want to take a look at "Finite Analogs of Szemeredi's Theorem" by Raff and Zeilberger (math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/szemeredi.html ), where they look at questions along the lines of "How dense can a set be and still avoid progressions of length $k$ having difference at most $D$". | |
| Jan 17, 2012 at 19:43 | comment | added | Pace Nielsen | It is not hard to see that $g(k)=max_c \{g_c(k)\}$ is bounded below by a linear function in $k$. Just consider the coloring where we take $k−1$ terms of one color, followed by $k−1$ terms in the other color, etc.... This proves that $g(k)≥2k-2$. | |
| Jan 17, 2012 at 19:28 | comment | added | Pace Nielsen | Mark, that is exactly what I had in mind (in the case when we restrict ourselves to only 2 colors). So by "gap" I meant the distance between term consecutive terms in the arithmetic progression. To give a few concrete examples: if k=2 then the worst minimum gap (for an arbitrary coloring) is eventually 2, since the worse case is "color even numbers one color, and color odd numberss the other color." So the spacing in the smallest arithmetic progression is 2. (Note: In any other coloring the minimum gap in a 2-term arithmetic progression is 1.) | |
| Jan 14, 2012 at 8:24 | comment | added | user6976 | As I understand the minimal gap is this: given a coloring $c$ and $k$, $g_c(k)$ is the minimal step of a $k$-term monochromatic arithmetic progression. Question: what can be the growth of $g_c(k)$ (for a given $c$). In particular, what can be the maximal possible growth? One upper bound is given by the van der Waerden proof (and does not depend on $c$), for example, but that does not seem to be optimal. For example, I am not even sure that $g_c(k)$ cannot always have a linear upper bound (depending on $c$). Of course the OP may have a different question in mind. | |
| Jan 14, 2012 at 6:03 | comment | added | Greg Martin | Can you clarify what you mean by "minimal gaps"? I imagine it might be possible, for every integer $G$, to construct a two-coloring of an arbitrarily long interval that has no $k$-term progression with gaps less than $G$. | |
| Jan 13, 2012 at 20:19 | answer | added | Igor Rivin | timeline score: 0 | |
| Jan 13, 2012 at 19:35 | history | edited | Pace Nielsen |
edited tags
|
|
| Jan 13, 2012 at 19:30 | history | rollback | Pace Nielsen |
Rollback to Revision 1
|
|
| Jan 13, 2012 at 19:12 | history | edited | Micah Milinovich |
edited tags
|
|
| Jan 13, 2012 at 18:56 | history | asked | Pace Nielsen | CC BY-SA 3.0 |