Is the Cheeger constant of an induced subgraph of a cube at most 1?

2012-02-06T22:39:26Z

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$

Answer by Eric Naslund for Is the Cheeger constant of an induced subgraph of a cube at most 1?

2012-02-07T15:58:31Z

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

Is the Cheeger constant of an induced subgraph of a cube at most 1? - MathOverflow

Is the Cheeger constant of an induced subgraph of a cube at most 1?

Answer by Eric Naslund for Is the Cheeger constant of an induced subgraph of a cube at most 1?