Combinatorics, Probability and Computing


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:

Article author query
solymosi j   [Google Scholar] 


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)

p1 Present address: Department of Mathematics, University of British Columbia, BC, Vancouver V6T 1Y4, Canada (e-mail:


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