98-34: On the Dimension of the Hilbert-Cubes

DIMACS TR: 98-34

On the Dimension of the Hilbert-Cubes

Author: Norbert Hegyvári

ABSTRACT
Let $A$ be a sequence of positive integers with positive density. Then $A\cap\{1, 2, \ldots , n\}$ contains a Hilbert (or combinatorial) cube of dimension $c\log\log n$. We prove that this bound can not be replaced by $c'\sqrt{\log n\log\log n}$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-34.ps.gz

DIMACS Home Page