Non-degenerate Hilbert cubes in random sets

Sándor, Csaba

Journal de théorie des nombres de Bordeaux, Tome 19 (2007) no. 1, pp. 249-261.

Une légère modification de la démonstration du lemme des cubes de Szemerédi donne le résultat plus précis suivant : si une partie $S$ de $\{1,\cdots ,n\}$ vérifie $\left|S\right|\ge \frac{n}{2}$, alors $S$ contient un cube de Hilbert non dégénéré de dimension $\lfloor {log}_2{log}_{2}n-3\rfloor$. Dans cet article nous montrons que dans un ensemble aléatoire avec les probabilités $\mathrm{Pr}\{s\in S\}=1/2$ indépendantes pour $1\le s\le n$, la plus grande dimension d’un cube de Hilbert non dégénéré est proche de ${log}_2{log}_{2}n+{log}_2{log}_2{log}_{2}n$ presque sûrement et nous déterminons la fonction seuil pour avoir un $k$-cube non dégénéré.

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.

[1] N. Alon, J. Spencer, The Probabilistic Method. Wiley-Interscience, Series in Discrete Math. and Optimization, 1992. | MR | Zbl

[2] A. Godbole, S. Janson, N. Locantore, R. Rapoport, Random Sidon Seqence. J. Number Theory 75 (1999), no. 1, 7–22. | MR | Zbl

[3] D. S. Gunderson, V. Rödl, Extremal problems for Affine Cubes of Integers. Combin. Probab. Comput 7 (1998), no. 1, 65–79. | MR | Zbl

[4] R. L. Graham, B. L. Rothchild, J. Spencer, Ramsey Theory. Wiley-Interscience, Series in Discrete Math. and Optimization, 1990. | MR | Zbl

[5] N. Hegyvári, On the dimension of the Hilbert cubes. J. Number Theory 77 (1999), no. 2, 326–330. | MR | Zbl