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

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?

-
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. –  Benoît Kloeckner Nov 25 '12 at 20:36
thanks. please see my edited first question. –  ak47 Nov 25 '12 at 22:07

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

-
thank you, my comment is below. –  ak47 Nov 24 '12 at 14:14

(see the question edit)

-
The equivalence you ask for in the case of R^n is easy and can be found on many sources (see Pisier, "The volume of convex bodies and Banach space Geometry" p. 4. You must take $\lambda =|A|^{1/n}(|A|^{1/n}+|B|^{1/n})^{-1}$`. –  juan Nov 24 '12 at 16:31