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

  • $\begingroup$ $(x,y)$ should be $(y,x)$, right? $\endgroup$ – Emil Jeřábek Feb 25 '11 at 11:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Feb 25 '11 at 13:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Feb 25 '11 at 14:01
  • 8
    $\begingroup$ 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. $\endgroup$ – Peter Shor Feb 25 '11 at 14:29
  • 4
    $\begingroup$ @Emil: it's Turán's theorem: en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem $\endgroup$ – 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$.

  • $\begingroup$ $\lambda$ is the Lebesgue measure on the real line? $\endgroup$ – Beni Bogosel Feb 28 '11 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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