# 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
@Emil: it's the same thing. Both {x,y}x{y,z}\{(y,y)} and {x,y}x{x,z}\{(x,x)} are the 3 vertices of a rectangle whose 4th vertex is on the diagonal. –  Yaakov Baruch Feb 25 '11 at 12:03
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