Improved lower bounds for van der Waerden numbers

2021/11/01 by Zach Hunter, Hunter, Zach
Computer Science · Mathematics · #05DXX (Primary) #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2111.01099

openalex publication_date 2021/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recently, Ben Green proved that the two-color van der Waerden number w(3,k) is bounded from below by k^b₀(k) where b₀(k) = c₀((log k )/(log log k))^1/3. We prove a new lower bound of k^b(k) with b(k) = (clog k)/(log log k). This is done by modifying Green's argument, replacing a complicated result about random quadratic forms with an elementary probabilistic result.

Related

• New lower bounds for van der Waerden numbers
• A short proof that w(3,k) ≥ (1-o(1))k²
• Lower bounds for multicolor van der Waerden numbers
• How to find the least upper bound on the van der Waerden Number W(r, k) that is some integer Power of the coloring Integer r
• New Lower Bounds for Van der Waerden Numbers