Non-degenerate Hilbert cubes in random sets

Sándor, Csaba

doi:10.5802/jtnb.585

Sándor, Csaba ¹

¹ Institute of Mathematics Budapest University of Technology and Economics Egry J. u. 1., H-1111 Budapest, Hungary

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

Abstract
Résumé

A slight modification of the proof of Szemerédi’s cube lemma gives that if a set $S \subset [1, n]$ satisfies $| S | \geq \frac{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 {s \in S} = \frac{1}{2}$ for $1 \leq s \leq 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.

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, \dots, n}$ vérifie $| S | \geq \frac{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 {s \in S} = 1 / 2$ indépendantes pour $1 \leq s \leq 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é.

MR Zbl

DOI: 10.5802/jtnb.585

Author's affiliations:

Sándor, Csaba ¹

¹ 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 = {S\'andor, Csaba},
     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 = {http://archive.numdam.org/articles/10.5802/jtnb.585/}
}

TY  - JOUR
AU  - Sándor, Csaba
TI  - Non-degenerate Hilbert cubes in random sets
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2007
SP  - 249
EP  - 261
VL  - 19
IS  - 1
PB  - Université Bordeaux 1
UR  - http://archive.numdam.org/articles/10.5802/jtnb.585/
DO  - 10.5802/jtnb.585
LA  - en
ID  - JTNB_2007__19_1_249_0
ER  -

%0 Journal Article
%A Sándor, Csaba
%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 http://archive.numdam.org/articles/10.5802/jtnb.585/
%R 10.5802/jtnb.585
%G en
%F 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. http://archive.numdam.org/articles/10.5802/jtnb.585/

References
Cited by

[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

Cited by Sources: