2
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Is this homework? I vote to close. $\endgroup$ May 3, 2013 at 20:23
  • $\begingroup$ If it is a homework, then poorly digested, since one can take $f(m)=1$. $\endgroup$
    – Misha
    May 3, 2013 at 23:28

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – alezok
    May 14, 2013 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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