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

Consider a discrete even torus $G=(V,E)$, i.e. the graph on $\lbrace 0,1,\dots,n-1 \rbrace^2$, $n$ even, where two vertices are connected by an edge only if they differ by 1 in only one coordinate, modulo $n$.

$G$ is a bipartite graph. Call $O$ and $E$ the two sets into which the vertex set $V$ is partitioned (consisting of the odd and even vertices, respectively).

Given $A \subset V$, denote by $\partial A$ the vertex boundary of $A$, i.e. the set of all vertices in $V\setminus A$ whose graph distance from $A$ is exactly $1$.

Question: is there any vertex-isoperimetric inequality (VIP) of the form $$\min_{|A|=m, A \subseteq O} |\partial A| \geq f(m),$$ i.e. where the minimum is taken only over the subsets of odd vertices of $V$?

Bonus question: how much can be said in general about the same question, with $G$ being a bipartite regular graph?

share|improve this question
2  
Is this homework? I vote to close. –  Ori Gurel-Gurevich May 3 '13 at 20:23
    
If it is a homework, then poorly digested, since one can take $f(m)=1$. –  Misha May 3 '13 at 23:28
add comment

1 Answer

up vote 3 down vote accepted

The case $n=2$ is the usual discrete cube. Thinking of this as the power set of $[n]$, Harper's theorem tells us that initial segments of the simplicial order (ordering by set size then lexicographically) minimise the vertex boundary. If we want to minimise over odd or even sets then the best possible result we could hope for is true: initial segments of the simplicial order restricted to the odd or even sets minimise vertex boundary in this new setting. This has been rediscovered numerous times independently; see the references in this paper.

In particular, Harper's theorem tells us that Hamming balls minimise vertex boundary. The same result is true in tori of even "side length"; see Bollobás and Leader. Based on the $n=2$ case we would expect the intersection of Hamming balls with the even or odd sets to minimise the vertex boundary for your problem, and I'd be surprised if this wasn't true.

At least one proof of Harper's theorem (via codimension 1 compressions) goes through essentially unchanged to prove the restricted parity version. I'm also told that it can be deduced directly from Harper's theorem itself. So if you want the result for general tori you could try to adapt Bollobás and Leader's proof, or try to deduce the result from the unrestricted case.

I expect the question for general regular bipartite graphs is hard, because good isoperimetric results are only known for very special graphs like grids and cubes.

share|improve this answer
    
Working on this problem I also bumped into a paper of O.Riordan "An Ordering on the Even Discrete Torus" (1998), which strengthens the result of Bollobás and Leader. I strongly believe that the restriction of this order to the set $O$ of odd nodes is the isoperimetric order which tackles my problem. However, I didn't succeed in proving this formally. I also don't see how it follows directly from Harper's theorem, neither how to make the proof work (the "usual compressions" don't seem to be enough), but probably I'm not familiar enough with these techniques, since it isn't my area of expertise. –  Ale Zok May 14 '13 at 20:32
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.