Search the site

Table of contents for this issue | Previous article | Next article
Csaba Sándor
Non-degenerate Hilbert cubes in random sets
Journal de théorie des nombres de Bordeaux, 19 no. 1 (2007), p. 249-261, doi: 10.5802/jtnb.585
Article PDF | Reviews MR 2332065 | Zbl 1126.11014

Résumé - Abstract

A slight modification of the proof of Szemerédi’s cube lemma gives that if a set $S\subset [1,n]$ satisfies $|S|\ge \frac{n}{2}$, then $S$ must contain a non-degenerate Hilbert cube of dimension $\lfloor \log _2\log _2n -3\rfloor $. In this paper we prove that in a random set $S$ determined by $\textrm{Pr}\lbrace s\in S\rbrace =\frac{1}{2}$ for $1\le s\le n$, the maximal dimension of non-degenerate Hilbert cubes is a.e. nearly $\log _2\log _2n+\log _2\log _2\log _2n$ 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 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