Back to Search
Start Over
A new lower bound for van der Waerden numbers.
- Source :
-
European Journal of Combinatorics . Mar2018, Vol. 69, p163-168. 6p. - Publication Year :
- 2018
-
Abstract
- 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 ≤ k then w ( r , k ) > p ⋅ w r − r p , k − 1 . This recurrence gives the lower bound w ( r , p + 1 ) > p r − 1 2 p when r ≤ 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01956698
- Volume :
- 69
- Database :
- Academic Search Index
- Journal :
- European Journal of Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 126870923
- Full Text :
- https://doi.org/10.1016/j.ejc.2017.10.007