24
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ $(x,y)$ should be $(y,x)$, right? $\endgroup$ Feb 25, 2011 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$ Feb 25, 2011 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$ Feb 25, 2011 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, 2011 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, 2011 at 15:40

1 Answer 1

30
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ $\lambda$ is the Lebesgue measure on the real line? $\endgroup$ Feb 28, 2011 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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