Non-degenerate Hilbert cubes in random sets

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, Tome 19 (2007) no. 1, pp. 249-261

Abstract (VO)

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.

Résumé

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é.

Détail

DOI : 10.5802/jtnb.585