A subexponential upper bound for van der Waerden numbers W(3,k)

DOI10.37236/9704MaRDI QIDQ2030760zbMATH OpenOpenAlexFDO

Authors Tomasz Schoen

Publication date 7 June 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.02877

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Roth's theoremSzemerédi's theorem on arithmetic progressions

Mathematics Subject Classification ID

Ramsey theory (05D10) Arithmetic progressions (11B25)

Abstract: We show an improved upper estimate for van der Waerden number $W(3,k):$ there is an absolute constant $c>0$ such that if $1,dots,N=XcupY$ is a partition such that $X$ does not contain any arithmetic progression of length $3$ and $Y$ does not contain any arithmetic progression of length $k$ then ${\displaystyle }$Nle exp(O(k^{1-c})),.${\displaystyle }$

Review text

Summary: We show an improved upper estimate for van der Waerden number \(W(3,k)\): there is an absolute constant \(c>0\) such that if \(\{1,\dots,N\}=X\cup Y\) is a partition such that \(X\) does not contain any arithmetic progression of length \(3\) and \(Y\) does not contain any arithmetic progression of length \(k\) then \[N\leqslant \exp(O(k^{1-c}))\,.\]

Recommendations

• scientific article; zbMATH DE number 1545450
• Arithmetic progressions in sumsets
• New lower bounds for van der Waerden numbers
• On sets without k-term arithmetic progression
• Two new van der Waerden numbers: \(w(2;3,17)\) and \(w(2;3,18)\)

Cites work

• A Construction for Partitions Which Avoid Long Arithmetic Progressions
• A lower bound for off-diagonal van der Waerden numbers
• A new proof of Szemerédi's theorem
• A polynomial bound in Freiman's theorem.
• A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
• Additive combinatorics
• Additive structures in sumsets
• An application of Lovász' local lemma-A new lower bound for the van der Waerden number
• Arithmetic progressions in sumsets
• Bounds on some van der Waerden numbers
• scientific article; zbMATH DE number 5181747 (Why is no real title available?)
• Improved bound in Roth's theorem on arithmetic progressions
• Logarithmic bounds for Roth's theorem via almost-periodicity
• New bounds on cap sets
• On Certain Sets of Integers
• On Roth's theorem on progressions
• On sets of integers containing k elements in arithmetic progression
• On triples in arithmetic progression
• Tight bounds on additive Ramsey-type numbers

Cited in

(11)

• On the power of random greedy algorithms
• An upper bound for van der Waerden-like numbers using \(k\) colors
• Monochromatic strictly ascending waves and permutation pattern waves
• On combinatorial upper bounds for van der Waerden numbers W(3;r)
• scientific article; zbMATH DE number 1545450 (Why is no real title available?)
• scientific article; zbMATH DE number 833595 (Why is no real title available?)
• scientific article; zbMATH DE number 7478541 (Why is no real title available?)
• New lower bounds for van der Waerden numbers
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Improved lower bounds for van der Waerden numbers
• Some new bounds and values for van der Waerden-like numbers

This page was built for publication: A subexponential upper bound for van der Waerden numbers \(W(3,k)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2030760)