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:
Published online:
DOI: 10.5802/jtnb.585
Csaba Sándor 1

1 Institute of Mathematics Budapest University of Technology and Economics Egry J. u. 1., H-1111 Budapest, Hungary
@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},
     pages = {249--261},
     publisher = {Universit\'e Bordeaux 1},
     volume = {19},
     number = {1},
     year = {2007},
     doi = {10.5802/jtnb.585},
     zbl = {1126.11014},
     mrnumber = {2332065},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.585/}
}
TY  - JOUR
TI  - Non-degenerate Hilbert cubes in random sets
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2007
DA  - 2007///
SP  - 249
EP  - 261
VL  - 19
IS  - 1
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.585/
UR  - https://zbmath.org/?q=an%3A1126.11014
UR  - https://www.ams.org/mathscinet-getitem?mr=2332065
UR  - https://doi.org/10.5802/jtnb.585
DO  - 10.5802/jtnb.585
LA  - en
ID  - JTNB_2007__19_1_249_0
ER  - 
%0 Journal Article
%T Non-degenerate Hilbert cubes in random sets
%J Journal de Théorie des Nombres de Bordeaux
%D 2007
%P 249-261
%V 19
%N 1
%I Université Bordeaux 1
%U https://doi.org/10.5802/jtnb.585
%R 10.5802/jtnb.585
%G en
%F JTNB_2007__19_1_249_0
Csaba Sándor. 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/articles/10.5802/jtnb.585/

[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

Cited by Sources: