Combinatorics, Probability and Computing



Paper

A Note on a Question of Erdos and Graham


J. SOLYMOSI a1p1 1
a1 Department of Mathematics, University of California in San Diego, 9500 Gilman Drive, La Jolla CA 92093-0112, USA (e-mail: solymosi@math.ucsd.edu)

Article author query
solymosi j   [Google Scholar] 
 

Abstract

We give a quantitative proof that, for sufficiently large $N$, every subset of $[N]^2$ of size at least $\delta N^2$ contains a square, i.e., four points with coordinates $\{(a,b),(a+d,b),(a,b+d),(a+d,b+d)\}$.

(Published Online March 3 2004)
(Received August 29 2002)
(Revised November 17 2002)


Correspondence:
p1 Present address: Department of Mathematics, University of British Columbia, BC, Vancouver V6T 1Y4, Canada (e-mail: solymosi@math.ubc.ca).


Footnotes

1 Supported by the Berlin–Zürich European Graduate Program ‘Combinatorics, Geometry, and Computation’ and by MTA SZTAKI.