Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Chromatic Number
diophantine approximation
Subscribe
Academic
Publications
Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation
Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation,10.1112/blms/bdp126,Bulletin of The London Mathematical Socie
Edit
Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation
(
Citations: 4
)
BibTex

RIS

RefWorks
Download
Yuval Peres
,
Wilhelm Schlag
Let ${n_k}$ be an increasing lacunary sequence, i.e., $n_{k+1}/n_k>1+r$ for some $r>0$. In 1987, P. Erdos asked for the
chromatic number
of a graph $G$ on the integers, where two integers $a,b$ are connected by an edge iff their difference $ab$ is in the sequence ${n_k}$. Y. Katznelson found a connection to a
Diophantine approximation
problem (also due to Erdos): the existence of $x$ in $(0,1)$ such that all the multiples $n_j x$ are at least distance $\delta(x)>0$ from the set of integers. Katznelson bounded the
chromatic number
of $G$ by $Cr^{2}\log r$. We apply the Lov\'asz local lemma to establish that $\delta(x)>cr\log r^{1}$ for some $x$, which implies that the
chromatic number
of $G$ is at most $Cr^{1} \log r$. This is sharp up to the logarithmic factor.
Journal:
Bulletin of The London Mathematical Society  BULL LOND MATH SOC
, vol. 42, no. 2, pp. 295300, 2010
DOI:
10.1112/blms/bdp126
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
blms.oxfordjournals.org
)
(
arxiv.org
)
(
www.math.uchicago.edu
)
Citation Context
(3)
...result, Theorem 1.1, was obtained in 1999 and presented in a lecture [
14
] at the IAS, Princeton...
Yuval Peres
,
et al.
Two Erdos problems on lacunary sequences: Chromatic number and Diophan...
...It seems that essentially the same special case was used by Peres and Schlag in their paper on Lacunary sequences [
19
]...
Wesley Pegden
.
Highly nonrepetitive sequences: winning strategies from the local lemm...
...Those methods can be applied even if the rational number p/q is replaced by an arbitrary real number a> 1. See, e.g., some recent work [1,4,7,
12
] on this problem...
Artūras Dubickas
.
Powers of Rational Numbers Modulo 1 Lying in Short Intervals
References
(12)
The Probabilistic Method
(
Citations: 2202
)
Noga Alon
,
Joel Spencer
Published in 1992.
Chromatic Numbers of Cayley Graphs on Z and Recurrence
(
Citations: 11
)
Y. Katznelson
Journal:
Combinatorica
, vol. 21, no. 2, pp. 211219, 2001
Distance Graphs with Finite Chromatic Number
(
Citations: 14
)
Imre Z. Ruzsa
,
Zsolt Tuza
,
Margit Voigt
Journal:
Journal of Combinatorial Theory  JCT
, vol. 85, no. 1, pp. 181187, 2002
PROBLEMS AND RESULTS ON 3CHROMATIC HYPERGRAPHS AND SOME RELATED QUESTIONS
(
Citations: 143
)
P. ERDOS
,
L. LOVÁSZ
Published in 1975.
Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions
(
Citations: 212
)
Harry Furstenberg
Journal:
Journal D Analyse Mathematique  J ANAL MATH
, vol. 31, no. 1, pp. 204256, 1977
Sort by:
Citations
(4)
Nonrepetitive sequences on arithmetic progressions
Jaroslaw Grytczuk
,
Jakub Kozik
,
Marcin Witkowski
Journal:
Computing Research Repository  CORR
, vol. abs/1102.5, 2011
Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation
(
Citations: 4
)
Yuval Peres
,
Wilhelm Schlag
Journal:
Bulletin of The London Mathematical Society  BULL LOND MATH SOC
, vol. 42, no. 2, pp. 295300, 2010
Highly nonrepetitive sequences: winning strategies from the local lemma
(
Citations: 1
)
Wesley Pegden
Published in 2010.
Powers of Rational Numbers Modulo 1 Lying in Short Intervals
Artūras Dubickas
Journal:
Results in Mathematics  RESULTS MATH
, vol. 57, no. 1, pp. 2331, 2010