Bounds on Van der Waerden Numbers and Some Related Functions
| dc.creator | Brown, Tom | |
| dc.creator | Landman, Bruce M. | |
| dc.creator | Robertson, Aaron | |
| dc.date | 2007-06-29 | |
| dc.date.accessioned | 2026-07-07T08:13:09Z | |
| dc.date.available | 2026-07-07T08:13:09Z | |
| dc.description | For positive integers $s$ and $k_1, k_2, ..., k_s$, let $w(k_1,k_2,...,k_s)$ be the minimum integer $n$ such that any $s$-coloring $\{1,2,...,n\} \to \{1,2,...,s\}$ admits a $k_i$-term arithmetic progression of color $i$ for some $i$, $1 \leq i \leq s$. In the case when $k_1=k_2=...=k_s=k$ we simply write $w(k;s)$. That such a minimum integer exists follows from van der Waerden's theorem on arithmetic progressions. In the present paper we give a lower bound for $w(k,m)$ for each fixed $m$. We include a table with values of $w(k,3)$ which match this lower bound closely for $5 \leq k \leq 16$. We also give an upper bound for $w(k,4)$, an upper bound for $w(4;s)$, and a lower bound for $w(k;s)$ for an arbitrary fixed $k$. We discuss a number of other functions that are closely related to the van der Waerden function. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/0706.4420 | |
| dc.identifier | http://arxiv.org/abs/0706.4420 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132699 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D10 | |
| dc.title | Bounds on Van der Waerden Numbers and Some Related Functions | |
| dc.type | text |