Non-degenerate Hilbert cubes in random sets

Csaba Sándor[1]

  • [1] 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 (2007)

  • Volume: 19, Issue: 1, page 249-261
  • ISSN: 1246-7405

Abstract

top
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 { s ∈ S } = 1 2 for 1 ≤ s ≤ 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.

How to cite

top

Sándor, Csaba. "Non-degenerate Hilbert cubes in random sets." Journal de Théorie des Nombres de Bordeaux 19.1 (2007): 249-261. <http://eudml.org/doc/249953>.

@article{Sándor2007,
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.},
affiliation = {Institute of Mathematics Budapest University of Technology and Economics Egry J. u. 1., H-1111 Budapest, Hungary},
author = {Sándor, Csaba},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {Hilbert cube; subset sum; random set},
language = {eng},
number = {1},
pages = {249-261},
publisher = {Université Bordeaux 1},
title = {Non-degenerate Hilbert cubes in random sets},
url = {http://eudml.org/doc/249953},
volume = {19},
year = {2007},
}

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
PB - Université Bordeaux 1
VL - 19
IS - 1
SP - 249
EP - 261
AB - 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.
LA - eng
KW - Hilbert cube; subset sum; random set
UR - http://eudml.org/doc/249953
ER -

References

top
  1. N. Alon, J. Spencer, The Probabilistic Method. Wiley-Interscience, Series in Discrete Math. and Optimization, 1992. Zbl0767.05001MR1140703
  2. A. Godbole, S. Janson, N. Locantore, R. Rapoport, Random Sidon Seqence. J. Number Theory 75 (1999), no. 1, 7–22. Zbl0924.11006MR1677540
  3. D. S. Gunderson, V. Rödl, Extremal problems for Affine Cubes of Integers. Combin. Probab. Comput 7 (1998), no. 1, 65–79. Zbl0892.05050MR1611126
  4. R. L. Graham, B. L. Rothchild, J. Spencer, Ramsey Theory. Wiley-Interscience, Series in Discrete Math. and Optimization, 1990. Zbl0705.05061MR1044995
  5. N. Hegyvári, On the dimension of the Hilbert cubes. J. Number Theory 77 (1999), no. 2, 326–330. Zbl0989.11012MR1702212

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.