A New Lower Bound for van der Waerden Numbers
| Autor: | Blankenship, Thomas, Cummings, Jay, Taranchuk, Vladislav |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.ejc.2017.10.007 |
| Popis: | In this paper we prove a new recurrence relation on the van der Waerden numbers, $w(r,k)$. In particular, if $p$ is a prime and $p\leq k$ then $w(r, k) > p \cdot \left(w\left(r - \left\lceil \frac{r}{p}\right\rceil, k\right) -1\right)$. This recurrence gives the lower bound $w(r, p+1) > p^{r-1}2^p$ when $r \leq p$, which generalizes Berlekamp's theorem on 2-colorings, and gives the best known bound for a large interval of $r$. The recurrence can also be used to construct explicit valid colorings, and it improves known lower bounds on small van der Waerden numbers. Comment: 9 pages, 1 table. Article has been accepted into the European Journal of Combinatorics |
| Databáze: | arXiv |
| Externí odkaz: |
|