Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
thank you, my comment is below. –  ak47 Nov 24 '12 at 14:14
add comment

(see the question edit)

share|improve this answer
    
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
    
Answers are not meant to be comments. You should rather edit your answer or use comments. –  Benoît Kloeckner Nov 25 '12 at 20:30
    
I did the modification. –  Benoît Kloeckner Nov 25 '12 at 20:34
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.