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

Starting from a question in probability, one is eventually lead to the following optimization problem.

Let $I:=[0,\\, 1],$ and let $A$ be a Lebesgue measurable subset of the $n$-dimensional cube, $A\subset I^n.$ Consider, correspondingly, the set $$\hat A:= \{x\in I^{n+1}:\\, (x_1,\dots,x_n)\in A,\\, (x_2,\dots,x_{n+1})\notin A\}=A\times I\\,\cap\\, I \times A^c.$$

Problem. Maximize the $(n+1)$-dimensional Lebesgue measure of $\hat A$ over all measurable $A\subset I^n$: $$\lambda_n:=\sup_{A\subset I^n}\vert\hat A\vert.$$

If $n=1,$ we have $|\hat A|=|A|(1-|A|),$ whence $\lambda_1=1/4.$ For $n=2$ the maximizing set is the triangle below the diagonal, giving $\lambda_2=1/3.$ The sequence $\lambda_n$ is increasing, and converges to $1/2.$ If $n$ is even, one finds $$\lambda_n=\frac{1}{2}\left(1-\frac{1}{n+1}\right).$$ (I will edit and provide the details of the computation at request). However, as a consequence of a computation by Trotter and Winkler (Ramsey theory and sequences of random variables, Probability, Combinatorics and Computing 7 (1998), 221-238), the formula can't hold true for all odd $n,$ for one has $\lambda_5>\frac{1}{2}\left(1-\frac{1}{6}\right)=5/12.$

I would be very grateful for any suggestion or reference useful to shed light on the case of odd $n.$

share|cite|improve this question
Interesting. Do you know the answer to your question if you replace $[0,1]$ by $\{0,1\}$? – Bjørn Kjos-Hanssen Oct 5 '10 at 7:50
That's a good question (sorry for being late in the answer). I will add some remarks to the question on that. With {0,1}, one finds certain graph theoretic quantities (e.g. independence numbers), that give bounds from below for the case of [0,1] (it is equivalent to take the supremum over the sets $A$ in a finite sigma algebra generated by cubes of size 1/2). However, I do not know the answer for {0,1}; as far as I understand it could be even more difficult. – Pietro Majer Oct 5 '10 at 8:14

Your Answer


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

Browse other questions tagged or ask your own question.