Skip to main content
1 of 3
Pietro Majer
  • 60.5k
  • 4
  • 122
  • 269

Maximizing the volume in a family of subset of a cube

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$ increasing, converging 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 result 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.$

Pietro Majer
  • 60.5k
  • 4
  • 122
  • 269