Skip to main content
added 107 characters in body
Source Link
Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24

Given $\delta>0$ and positive integers $k$, write $h(\delta;k)$ for the smallest $N$ such that for any $S\subset [N]:=\{1,\dots,N\}$ of size $\ge \delta N$, there exists non-zero integers $n_0,d_1,\dots,d_k$ such that $n_0+\sum_{i\in I}d_i\in S$ for all $I\subset [k]$ (these sums need not all be distinct, in fact, they may be any $k$-term arithmetic progression).

It occurs to me that there is a short proof that for any fixed $\delta$, that $h(\delta;k)$ grows superexponentially as $k\to \infty$ (i.e., for any $C$, we have $h(\delta;k)>C^k$ for all large $k$).

Is such a bound recorded in the literature? I am aware of the work of Gunderson, Rodl, and Siderenko (e.g., "Extremal problems for sets forming Boolean algebras and complete partite hypergraphs"), but their bounds fixate on when $k$ is fixed and $\delta\to 0$.

Given $\delta>0$ and positive integers $k$, write $h(\delta;k)$ for the smallest $N$ such that for any $S\subset [N]:=\{1,\dots,N\}$ of size $\ge \delta N$, there exists integers $n_0,d_1,\dots,d_k$ such that $n_0+\sum_{i\in I}d_i\in S$ for all $I\subset [k]$.

It occurs to me that there is a short proof that for any fixed $\delta$, that $h(\delta;k)$ grows superexponentially as $k\to \infty$ (i.e., for any $C$, we have $h(\delta;k)>C^k$ for all large $k$).

Is such a bound recorded in the literature? I am aware of the work of Gunderson, Rodl, and Siderenko (e.g., "Extremal problems for sets forming Boolean algebras and complete partite hypergraphs"), but their bounds fixate on when $k$ is fixed and $\delta\to 0$.

Given $\delta>0$ and positive integers $k$, write $h(\delta;k)$ for the smallest $N$ such that for any $S\subset [N]:=\{1,\dots,N\}$ of size $\ge \delta N$, there exists non-zero integers $n_0,d_1,\dots,d_k$ such that $n_0+\sum_{i\in I}d_i\in S$ for all $I\subset [k]$ (these sums need not all be distinct, in fact, they may be any $k$-term arithmetic progression).

It occurs to me that there is a short proof that for any fixed $\delta$, that $h(\delta;k)$ grows superexponentially as $k\to \infty$ (i.e., for any $C$, we have $h(\delta;k)>C^k$ for all large $k$).

Is such a bound recorded in the literature? I am aware of the work of Gunderson, Rodl, and Siderenko (e.g., "Extremal problems for sets forming Boolean algebras and complete partite hypergraphs"), but their bounds fixate on when $k$ is fixed and $\delta\to 0$.

Source Link
Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24

Lower bounds for the density variant of the Hilbert cube problem

Given $\delta>0$ and positive integers $k$, write $h(\delta;k)$ for the smallest $N$ such that for any $S\subset [N]:=\{1,\dots,N\}$ of size $\ge \delta N$, there exists integers $n_0,d_1,\dots,d_k$ such that $n_0+\sum_{i\in I}d_i\in S$ for all $I\subset [k]$.

It occurs to me that there is a short proof that for any fixed $\delta$, that $h(\delta;k)$ grows superexponentially as $k\to \infty$ (i.e., for any $C$, we have $h(\delta;k)>C^k$ for all large $k$).

Is such a bound recorded in the literature? I am aware of the work of Gunderson, Rodl, and Siderenko (e.g., "Extremal problems for sets forming Boolean algebras and complete partite hypergraphs"), but their bounds fixate on when $k$ is fixed and $\delta\to 0$.