Non-degenerate Hilbert cubes in random sets
Journal de Théorie des Nombres de Bordeaux, Volume 19 (2007) no. 1, pp. 249-261.

A slight modification of the proof of Szemerédi’s cube lemma gives that if a set S[1,n] satisfies |S|n 2, then S must contain a non-degenerate Hilbert cube of dimension log 2 log 2 n-3. In this paper we prove that in a random set S determined by Pr{sS}=1 2 for 1sn, 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.

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,,n} vérifie |S|n 2, alors S contient un cube de Hilbert non dégénéré de dimension log 2 log 2 n-3. Dans cet article nous montrons que dans un ensemble aléatoire avec les probabilités Pr{sS}=1/2 indépendantes pour 1sn, 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é.

Received: 2005-11-30
Published online: 2008-12-03
DOI: https://doi.org/10.5802/jtnb.585
@article{JTNB_2007__19_1_249_0,
     author = {Csaba S\'andor},
     title = {Non-degenerate Hilbert cubes in random sets},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux 1},
     volume = {19},
     number = {1},
     year = {2007},
     pages = {249-261},
     doi = {10.5802/jtnb.585},
     zbl = {1126.11014},
     mrnumber = {2332065},
     language = {en},
     url={jtnb.centre-mersenne.org/item/JTNB_2007__19_1_249_0/}
}
Sándor, Csaba. Non-degenerate Hilbert cubes in random sets. Journal de Théorie des Nombres de Bordeaux, Volume 19 (2007) no. 1, pp. 249-261. doi : 10.5802/jtnb.585. https://jtnb.centre-mersenne.org/item/JTNB_2007__19_1_249_0/

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

[2] A. Godbole, S. Janson, N. Locantore, R. Rapoport, Random Sidon Seqence. J. Number Theory 75 (1999), no. 1, 7–22. | MR 1677540 | 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. | MR 1611126 | Zbl 0892.05050

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

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