8
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Isn't the Cheeger constant of a subgraph always smaller than or equal to the Cheeger constant of a graph? $\endgroup$
    – Seva
    Feb 7, 2012 at 8:39
  • $\begingroup$ @Seva: Consider two copies of the complete graph connected at a single vertex. $\endgroup$ Feb 7, 2012 at 15:02
  • $\begingroup$ On this occasion: are the Cheeger constants of the discrete tori $C_n^r$ known? $\endgroup$
    – Seva
    Feb 8, 2012 at 17:58

1 Answer 1

6
$\begingroup$

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

$\endgroup$

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.