Skip to content
DraconiticResearch
Search Sources API
189,280 studies31 sourcesUpdated 46 min ago
PreprintCC BY 4.0arXiv

An improved lower bound for the van der Waerden number w(3,k)

  • Haitao Cao
Open at sourcePDFDOICite

Abstract

For an integer k≥ 3, let w(3,k) be the least n such that every red-blue coloring of [n] contains either a nontrivial three-term arithmetic progression in blue or a nontrivial k-term arithmetic progression in red. A recent breakthrough of Green proved that w(3,k)≥ kΩ(((log k)/(loglog k))1/3) when k is large, and Hunter later improved the bound to w(3,k)≥ kΩ((log k)/(loglog k)). On the other hand, Green remarked that it is reasonable to believe that w(3,k)≤ kO(log k). We prove that w(3,k)≥ kΩ(log k), which perhaps gives some evidence that kΘ(log k) is the correct order of magnitude.

Related

  1. An improved lower bound for the packing number of the 2-token graph of the cycle
    Luis Manuel Rivera
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. An improved lower and upper bound of the k-limited domination number
    Gordana Radić
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. An Improved Lower Bound for the Complex Grothendieck Constant
    Shengtao Guo, Ethan X. Fang, Junwei Lu
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. An improved upper bound on the chromatic number of the n-dimensional sphere
    A. I. Bikeev, V. A. Voronov, A. M. Raigorodskii
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. An Improved Lower Bound for Packing 203 Equal Spheres in a Unit Cube
    Peng Lu
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{cao2026improved,
  title = {{An improved lower bound for the van der Waerden number $w(3,k)$}},
  author = {Haitao Cao},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.31798},
  eprint = {2609.31798},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.31798},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - An improved lower bound for the van der Waerden number w(3,k)
AU  - Haitao Cao
PY  - 2026
DA  - 2026/09/25
PB  - arXiv
DO  - 10.48550/arxiv.2609.31798
UR  - https://arxiv.org/abs/2609.31798
AB  - For an integer k≥ 3, let w(3,k) be the least n such that every red-blue coloring of [n] contains either a nontrivial three-term arithmetic progression in blue or a nontrivial k-term arithmetic progression in red. A recent breakthrough of Green proved that w(3,k)≥ k^Ω(((log k)/(loglog k))^1/3) when k is large, and Hunter later improved the bound to w(3,k)≥ k^Ω((log k)/(loglog k)). On the other hand, Green remarked that it is reasonable to believe that w(3,k)≤ k^O(log k). We prove that w(3,k)≥ k^Ω(log k), which perhaps gives some evidence that k^Θ(log k) is the correct order of magnitude.
ER  -