Convexity in $\{0,1\}^n$

Question

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?

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