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

It is known that the Cheeger constant of a hypercube graph $Q_n$ is exactly $1$, regardless of its dimension $n$. Is $1$ also an upper bound on the Cheeger constant of nontrivial induced connected subgraphs of $Q_n$?

The Cheeger constant $h(G)$ is also known as the edge expansion or the isoperimetic number.

To indirectly address a comment, here are the Cheeger constants of more graphs:
$h($$Q_n$$) = 1$
$h($$P_n$$) = 1 / \lfloor n / 2 \rfloor$
$h($$C_n$$) = 2 / \lfloor n / 2 \rfloor$
$h($$K_n$$) = \lceil n / 2 \rceil$

share|improve this question
    
Isn't the Cheeger constant of a subgraph always smaller than or equal to the Cheeger constant of a graph? –  Seva Feb 7 '12 at 8:39
    
@Seva: Consider two copies of the complete graph connected at a single vertex. –  Eric Naslund Feb 7 '12 at 15:02
    
On this occasion: are the Cheeger constants of the discrete tori $C_n^r$ known? –  Seva Feb 8 '12 at 17:58

1 Answer 1

up vote 6 down vote accepted

Your conjecture is true, every subgraph of the cube has expansion constant at most $1$.

Proof: Suppose we are given a subgraph $G\subset Q_n$, $n>1$ and cut the cube into $2$ $(n-1)$-dimensional subcubes $A_1,A_2$. (So that $A_1\cup A_2=Q_n$) The key is to notice that each vertex in $A_1$ is connected to one and only one vertex in $A_2$. Then split $G$ into two parts, $G_1=G\cap A_1$ and $G_2=G\cap A_2$. One of these will have size $\leq \frac{|G|}{2}$, suppose it is $G_1$. Because $G_1$ is in $A_1$, it is only connected to vertices in $A_2$, and we have $\partial G_1 \leq |G_1|$. Since the expansion constant is the minimum, we conclude that $$h(G)\leq 1.$$

share|improve this answer

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.