MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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^*$.

share|cite|improve this question
$(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: – JBL Feb 25 '11 at 15:40
up vote 30 down vote accepted

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$.

share|cite|improve this answer
excellent, thank you – Pietro Majer Feb 25 '11 at 16:47
$\lambda$ is the Lebesgue measure on the real line? – Beni Bogosel Feb 28 '11 at 12:19
Ok. I got it now. Thank you. – Beni Bogosel Feb 28 '11 at 12:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.