# A puzzle about finding three points $(x,y)$, $(x,z)$ and $(y,z)$ in a subset of a square.

I was asked (by myself) to give a proof of the following seemingly simple geometric statement, but after thinking a little I now suspect it could be less elementary than I thought (or am I being silly?). Does anybody know it, and can give an answer or a reference to it? Of course, I'm quite sure it should fit within a larger theory in combinatorics or in probability, but an elementary answer would be appreciated.

Let $S$ be a (say open) subset of a square $[0,1]^2$ with Lebesgue measure $|S|>1/2$. Then, there exists a rectangle with a vertex on the diagonal, and the other three vertices in $S$ (in other words, there are three points of $S$ of the form $(x,y)$, $(x,z)$ and $(y,z)\\$).

The constant $1/2$ cannot be lowered, as the example of the subset $S^* :=(0,1/2)\times(1/2,1)\cup(1/2,1)\times(0,1/2)$ shows (for any three points $x,y,z$ in $[0,1]$, at least 2 of them are both either smaller or larger than $1/2$, so the corresponding pair is not in $S^*$.

• $(x,y)$ should be $(y,x)$, right? – Emil Jeřábek Feb 25 '11 at 11:41
• Yaakov is right, but this does not mean that orientation does not matter. A red triangle $(x,y)$, $(y,z)$, $(z,x)$ does not give a rectangle. – Emil Jeřábek Feb 25 '11 at 13:54
• Having said that, I believe that some old theorem says that a finite undirected triangle-free graph has to have edge density at most 1/2. Maybe the underlying idea (which I can't recall ATM) could be used here as well. – Emil Jeřábek Feb 25 '11 at 14:01
• Here's a strategy. (1) Prove it for squares of a $2n \times 2n$ checkerboard. (2) Use compactness and limits to show this implies it for a general open set S. – Peter Shor Feb 25 '11 at 14:29
• @Emil: it's Turán's theorem: en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem – JBL Feb 25 '11 at 15:40

Let $S(x)=\{y\mid(x,y)\in S\}$ and $S^{-1}(y)=\{x\mid(x,y)\in S\}$, and let $\lambda_n$ denote the Lebesgue measure on $[0,1]^n$. We have
\begin{align*} \int_S(\lambda_1S(x)+\lambda_1S^{-1}(y))\,dx\,dy &=\int_S\lambda_1S(x)\,dx\,dy+\int_S\lambda_1S^{-1}(y)\,dx\,dy\\ &=\int(\lambda_1S(x))^2\,dx+\int(\lambda_1S^{-1}(y))^2\,dy\\ &\ge\left(\int\lambda_1S(x)\,dx\right)^2+\left(\int\lambda_1S^{-1}(y)\,dy\right)^2\\ &=2(\lambda_2S)^2>\lambda_2S=\int_S1\,dx\,dy, \end{align*}
hence there exists $(x,z)\in S$ such that $\lambda_1S(x)+\lambda_1S^{-1}(z)>1$. This implies $S(x)\cap S^{-1}(z)\ne\varnothing$, i.e., there exists $y$ such that $(x,y),(y,z)\in S$.
• $\lambda$ is the Lebesgue measure on the real line? – Beni Bogosel Feb 28 '11 at 12:19