Non-degenerate Hilbert cubes in random sets (Q2642767): Difference between revisions

A \(k\)-cube \(H\subseteq\{1,\ldots,n\}\) has the form \(\{a_0+\sum_{i\in I}a_i: I\subseteq\{1,\dots,k\}\}\) with \(a_0,a_1,\ldots,a_k\in\{1,\dots,n\}\). It is called non-degenerate if \(| H| =2^k\). By \textit{D. S. Gunderson} and \textit{V. Rödl}'s refinement [Comb. Probab. Comput. 7, 65--79 (1998; Zbl 0892.05050)] of Szemerédi's cube lemma, each set \(S\subseteq\{1,\ldots,n\}\) with \(| S| \geq n/2\) contains a \(\lfloor\log_2\log_2n-3\rfloor\)-cube. In the paper under review, the author shows that in a random set \(S\) with Pr\((s\in S)=1/2\) for all \(s=1,\dots,n\), \(\max\{k:S\) contains a non-degenerate \(k\)-cube\} is almost everywhere nearly \(\log_2\log_2n+\log_2\log_2\log_2n\).