Monochromatic Hilbert cubes and arithmetic progressions

MaRDI QIDQ2415085zbMATH OpenFDO

Authors József Balogh, Mikhail Lavrov, George Shakan, Adam Zsolt Wagner

Publication date 20 May 2019

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

Full work available at URL https://arxiv.org/abs/1805.08938, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p22

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

Mathematics Subject Classification ID

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

Abstract: The Van der Waerden number $W(k,r)$ denotes the smallest $n$ such that whenever $[n]$ is $r$--colored there exists a monochromatic arithmetic progression of length $k$. Similarly, the Hilbert cube number $h(k,r)$ denotes the smallest $n$ such that whenever $[n]$ is $r$--colored there exists a monochromatic affine $k$--cube, that is, a set of the form${\displaystyle }$left{x_0 + sum_{b in B} b : B subseteq A ight}${\displaystyle }$ for some $|A|=k$ and $x_{0}inmathbbZ$. We show the following relation between the Hilbert cube number and the Van der Waerden number. Let $kgeq3$ be an integer. Then for every $epsilon>0$, there is a $c>0$ such that ${\displaystyle }$h(k,4) ge min{W(lfloor c k^2 floor, 2), 2^{k^{2.5-epsilon}}}.${\displaystyle }$ Thus we improve upon state of the art lower bounds for $h(k,4)$ conditional on $W(k,2)$ being significantly larger than $2^k$. In the other direction, this shows that the if the Hilbert cube number is close its state of the art lower bounds, then $W(k,2)$ is at most doubly exponential in $k$. We also show the optimal result that for any Sidon set $AsubsetmathbbZ$, one has ${\displaystyle }$left|left{sum_{b in B} b : B subseteq A ight} ight| = Omega( |A|^3) .${\displaystyle }$

Review text

Summary: The Van der Waerden number \(W(k,r)\) denotes the smallest \(n\) such that whenever \([n]\) is \(r\)-colored there exists a monochromatic arithmetic progression of length \(k\). Similarly, the Hilbert cube number \(h(k,r)\) denotes the smallest \(n\) such that whenever \([n]\) is \(r\)-colored there exists a monochromatic affine \(k\)-cube, that is, a set of the form \[\left\{x_0 + \sum_{b \in B} b : B \subseteq A\right\}\] for some \(|A|=k\) and \(x_0 \in \mathbb{Z}\). We show the following relation between the Hilbert cube number and the Van der Waerden number. Let \(k \geqslant 3\) be an integer. Then for every \(\epsilon >0\), there is a \(c > 0\) such that \[h(k,4) \geqslant \min\{W(\lfloor c k^2\rfloor, 2), 2^{k^{2.5-\epsilon}}\}. \] Thus we improve upon state of the art lower bounds for \(h(k,4)\) conditional on \(W(k,2)\) being significantly larger than \(2^k\). In the other direction, this shows that if the Hilbert cube number is close to its state of the art lower bounds, then \(W(k,2)\) is at most doubly exponential in \(k\). We also show the optimal result that for any Sidon set \(A \subset \mathbb{Z}\), one has \[\left|\left\{\sum_{b \in B} b : B \subseteq A\right\}\right| = \Omega(|A|^3).\]

Recommendations

• Two extensions of Hilbert's cube lemma
• Bounds on some van der Waerden numbers
• Quantitative forms of a theorem of Hilbert
• Hilbert cubes in arithmetic sets
• New lower bounds for van der Waerden numbers

Cites work

• A Construction for Partitions Which Avoid Long Arithmetic Progressions
• A new lower bound for van der Waerden numbers
• A new proof of Szemerédi's theorem
• A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
• Additive combinatorics
• An application of Lovász' local lemma-A new lower bound for the van der Waerden number
• An improved lower bound for Folkman's theorem
• Bounds for the disjoint unions theorem
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• Improved algorithms for colorings of simple hypergraphs and applications
• Long arithmetic progressions in sumsets: Thresholds and bounds
• Monochromatic sumsets
• On sets of integers containing k elements in arithmetic progression
• Optimal inverse Littlewood-Offord theorems
• Quantitative forms of a theorem of Hilbert
• Short proofs of some extremal results
• Some of my favorite problems in Ramsey theory

Cited in

(8)

• Quantitative forms of a theorem of Hilbert
• Hilbert cubes in progression-free sets and in the set of squares
• Hilbert cubes meet arithmetic sets
• The largest projective cube-free subsets of \(\mathbb{Z}_{2^n}\)
• Two extensions of Hilbert's cube lemma
• On Monochromatic Arithmetic Progressions Having Odd Step
• Two extensions of Hilbert's cube lemma
• Extremal problems in hypergraph colourings

This page was built for publication: Monochromatic Hilbert cubes and arithmetic progressions

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