Is the Cheeger constant of an induced subgraph of a cube at most 1? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:18:22Z http://mathoverflow.net/feeds/question/87730 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/87730/is-the-cheeger-constant-of-an-induced-subgraph-of-a-cube-at-most-1 Is the Cheeger constant of an induced subgraph of a cube at most 1? psd 2012-02-06T22:39:26Z 2012-02-08T11:02:29Z <p>It is known that the <a href="http://en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29" rel="nofollow">Cheeger constant</a> of a <a href="http://en.wikipedia.org/wiki/Hypercube_graph" rel="nofollow">hypercube graph</a> $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$?</p> <p>The Cheeger constant $h(G)$ is also known as the <a href="http://en.wikipedia.org/wiki/Expander_graph#Edge_expansion" rel="nofollow">edge expansion</a> or the isoperimetic number.</p> <p>To indirectly address a comment, here are the Cheeger constants of more graphs:<br /> $h($<a href="http://en.wikipedia.org/wiki/Hypercube_graph" rel="nofollow">$Q_n$</a>$) = 1$ <br /> $h($<a href="http://en.wikipedia.org/wiki/Path_graph" rel="nofollow">$P_n$</a>$) = 1 / \lfloor n / 2 \rfloor$ <br /> $h($<a href="http://en.wikipedia.org/wiki/Cycle_graph" rel="nofollow">$C_n$</a>$) = 2 / \lfloor n / 2 \rfloor$ <br /> $h($<a href="http://en.wikipedia.org/wiki/Complete_graph" rel="nofollow">$K_n$</a>$) = \lceil n / 2 \rceil$</p> http://mathoverflow.net/questions/87730/is-the-cheeger-constant-of-an-induced-subgraph-of-a-cube-at-most-1/87808#87808 Answer by Eric Naslund for Is the Cheeger constant of an induced subgraph of a cube at most 1? Eric Naslund 2012-02-07T15:58:31Z 2012-02-08T11:02:29Z <p>Your conjecture is true, every subgraph of the cube has expansion constant at most $1$.</p> <p><em>Proof:</em> 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.$$ </p>