Advanced Search

A slight modification of the proof of Szemerédi’s cube lemma gives that if a set $S\subset [1,n]$ satisfies $\left|S\right|\ge \frac{n}{2}$, then $S$ must contain a non-degenerate Hilbert cube of dimension $\lfloor {log}_2{log}_{2}n-3\rfloor$. In this paper we prove that in a random set $S$ determined by $\mathrm{Pr}\{s\in S\}=\frac{1}{2}$ for $1\le s\le n$, the maximal dimension of non-degenerate Hilbert cubes is a.e. nearly ${log}_2{log}_{2}n+{log}_2{log}_2{log}_{2}n$ and determine the threshold function for a non-degenerate $k$-cube.