how is convexity defined in a subset $A \subset \{0,1\}^n$? furthermore, is there any extention of the Brunn-Minkowski inequality for subsets of $\{0,1\}^n$? thanks.

Edit (previously posted as an answer) thank you for the reference article of Ollivier and Villani. I have a few misunderstanding though, regarding Brunn-Minkowski in $R^n$ and {0,1}$^n$(the hyperplane).

  1. Edit - this is the corrected question: In $R^n$, there is a claim that it is enough to show that $$ |\lambda A+(1-\lambda)B| \geq |A|^{\lambda}|B|^{1-\lambda}, \forall 0 \leq \lambda \leq 1 $$ in order to conclude BM (Brunn-Minkowski) inequality: $$|A+B|^{1/n} \geq |A|^{1/n} + |B|^{1/n} $$ However, I couldn't think of how to prove it. Is it a trivial claim? How can someone prove it?

  2. In Ollivier and Villani's paper, it handles $M$, the middle points between a and b in the hypercube. I don't understand how can we expand this theory for $M'=\frac{1}{4}A+\frac{3}{4}B$, for example. we need it, I think, in order to conclude the real BM inequality in hypercube.

  3. I feel there is a basic difference between BM inequality in $R^n$ and in the hypercube: in $R^n$ we claim $|A+B|^{1/n} \geq |A|^{1/n} + |B|^{1/n}$, with 1/n power-factor is quite intuitive since volume of balls in $R^n$ is $\sim r^n$. but balls in hyperplane don't grow that way... so, I assume the formula of the MB inequality should look different: $$ \phi(|A+B|) \geq \phi(|A|)+\phi(|B|) $$. Is there any idea of how $\phi$ should look like?

  • 1
    $\begingroup$ Concerning point 2: this issue is raised in the paper. What you ask is an open question, as far as I know. concerning 3: what do you mean by $A+B$ in the hypercube? I think the form you use for the Euclidean BM inequality is not suitable for metric generalizations. $\endgroup$ Nov 25, 2012 at 20:36

1 Answer 1


If you want a stable notion of convexity, you can ask for` $C\subset \{0,1\}^n$ to be convex that for all $x,y\in C$, every minimal path between $x$ and $y$ is contained in $C$.

Concerning the Brunn-Minkowski inequality in the hypercube, there is a recent result of Ollivier and Villani :

"A curved Brunn-Minkowski inequality on the discrete hypercube, Or: What is the Ricci curvature of the discrete hypercube?" SIAM J. Discr. Math. 26 (2012), n°3, 983--996. (paper available e.g. on Yann Ollivier's web page).

The result is as follows: call midpoint of $x$ and $y$ any point that lies on a minimal path between them and is halfway (if $d(x,y)$ is even) or as close as halfway as possible (otherwise). For all $A,B\subset \{0,1\}^n$, the set $M$ of midpoints of pairs $(a,b)\in A\times B$ has cardinal bounded below: $$ \ln |M| \ge \frac12 \ln |A| + \frac12 \ln|B| +\frac1{16n} d(A,B)^2.$$


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.