Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers
type: Item
instance of: scholarly article
title: Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers
zbMATH Open document ID: 1244.05225
author: Mark Lotts
author: John Rabung
published in: The Electronic Journal of Combinatorics
publication date: 2012-06-12T00:00:00Z
full work available at URL: v19i2p35
review text: Summary: For integers \(k\) and \(l\), each greater than 1, suppose that \(p\) is a prime with \(p \equiv 1 \pmod k\) and that the \(k^{\text{th}}\)-power classes \(\mod p\) induce a coloring of the integer segment \([0,p-1]\) that admits no monochromatic occurrence of \(l\) consecutive members of an arithmetic progression. Such a coloring can lead to a coloring of \([0,(l-1)p]\) that is similarly free of monochromatic \(l\)-progressions, and, hence, can give directly a lower bound for the van der Waerden number \(W(k,l)\). \textit{P.R. Herwig}, \textit{M.J.H. Heule}, \textit{P.M. van Lambalgen}, and \textit{H. van Maaren} [ibid. 14, No. 1, Research paper R6, 18 p. (2007; Zbl 1115.05092)] have devised a technique for splitting and ``zipping'' such a coloring of \([0,p-1]\) to yield a coloring of \([0,2p-1]\) which, for even values of \(k\), is sometimes extendable to a coloring of \([0,2(l-1)p]\) where both new colorings still admit no monochromatic \(l\)-progressions. Here we derive a fast procedure for checking whether such a zipped coloring remains free of monochromatic \(l\)-progressions, effectively reducing a quadratic-time check to a linear-time check. Using this procedure we find some new lower bounds for van der Waerden numbers.
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6045728
zbMATH Keywords: van der Waerden numbers
MaRDI profile type: Publication
Recommended article: A new method to construct lower bounds for van der Waerden numbers
Recommended article: A new lower bound for van der Waerden numbers
Recommended article: New lower bounds for van der Waerden numbers
Recommended article: Lower bounds on van der Waerden numbers: randomized- and deterministic-constructive
Recommended article: Q4906936
Recommended article: A lower bound for off-diagonal van der Waerden numbers
Recommended article: On the existence of a reasonable upper bound for the van der Waerden numbers
Recommended article: An improved bound in Vizing's conjecture
Recommended article: Primitive Recursive Bounds for Van Der Waerden Numbers
Recommended article: Bounds on some van der Waerden numbers
description: scientific article; zbMATH DE number 6045728