Non-degenerate Hilbert cubes in random sets. (English) Zbl 1126.11014

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 D. S. Gunderson and 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\).


11B75 Other combinatorial number theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
11P99 Additive number theory; partitions


Zbl 0892.05050
Full Text: DOI Numdam EuDML Link


[1] N. Alon, J. Spencer, The Probabilistic Method. Wiley-Interscience, Series in Discrete Math. and Optimization, 1992. · Zbl 0767.05001
[2] A. Godbole, S. Janson, N. Locantore, R. Rapoport, Random Sidon Seqence. J. Number Theory 75 (1999), no. 1, 7-22. · Zbl 0924.11006
[3] D. S. Gunderson, V. Rödl, Extremal problems for Affine Cubes of Integers. Combin. Probab. Comput 7 (1998), no. 1, 65-79. · Zbl 0892.05050
[4] R. L. Graham, B. L. Rothchild, J. Spencer, Ramsey Theory. Wiley-Interscience, Series in Discrete Math. and Optimization, 1990. · Zbl 0705.05061
[5] N. Hegyvári, On the dimension of the Hilbert cubes. J. Number Theory 77 (1999), no. 2, 326-330. · Zbl 0989.11012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.