2
$\begingroup$

Context: http://www.sciencedirect.com/science/article/pii/S0019995882904776

Lemma 1 on 3rd page.

Question excerpted / rewritten as follows:

Let $G=(V,E)$ be the $n$-dimensional hypercube. That is $V=\{0,1\}^n$ and $x$ and $y$ are adjacent if and only if they differ in exactly one coordinate. Let $H=(V',E')$ be a subgraph of $G$ and suppose that $d$ is the minimum degree of $H$. Prove that $|V'| \geq 2^d$.

Thanks!

$\endgroup$
2
$\begingroup$

$G$ above corresponds to an $n$-dimensional hypercube, so $G'=(V',E')$ is necessarily a subgraph of the hypercube. Let $v$ be any vertex in $V'$ (and hence also in $V$). Note that in a hypercube the number of vertices a distance $D$ in the $\ell^1$ norm from $v_0$ has exactly $D$ edges which lead to vertices a distance $D-1$ from $v$ and $n - D$ vertices a distance $D+1$ from $v$. Since $v \in V'$, at least $d$ vertices at distance $1$ from $v$ must be in $V'$. At distance 2 there are $d(d-1)$ incoming edges, but each site has only $2$ edges which connect to sites a distance $1$ from $v$, and hence there must be at least $d(d-1)/2 = \binom{d}{2}$ vertices a distance 2 from $v$. Now assume there are at least $\binom{d}{D}$ vertices in $V'$ that are a distance $D$ from $v$. Then there are $\binom{d}{D}(d-D)$ edges connecting these vertices to vertices $D+1$ from $v$. However each of these has at most $D+1$ edges connecting to vertices $D$ from $v$, and hence there is at least $\binom{d}{D}\frac{d-D}{D+1} = \binom{d}{D+1}$ vertices at distance $D+1$. Thus, by induction, there are at least $\sum_{D=0}^{d} \binom{d}{D} = 2^d$ vertices in $V'$.

A trivial example to show this bound is tight is to take a hypercube of dimension $d$ on the boundary of the original hypercube, as this has exactly $2^d$ vertices and has degree $d$ for all vertices.

$\endgroup$
1
$\begingroup$

I think the "official" reference for this fact is Section 4 of the following paper of Chung, Furedi, Graham, and Seymour:

http://www.math.ucsd.edu/~ronspubs/88_06_induced_cube.pdf

$\endgroup$
  • 1
    $\begingroup$ It looks like they prove something slightly stronger in fact. Namely $|V'| \geq 2^d$' where $d$ is the average degree of $G$. $\endgroup$ – Tony Huynh Oct 8 '11 at 5:32
1
$\begingroup$

Let $G'=(V',E')$ be a counterexample with $|V'|$ minimum and then with the dimension of the hypercube in which $G'$ lives minimum. Let $G_0$ and $G_1$ be the subgraphs of $G'$ induced by the vertices of $G'$ with first component $0$ and $1$ respectively. Note that neither $G_0$ nor $G_1$ is empty, else $G'$ sits in a hypercube of lower dimension.

Now let $\delta_0$ and $\delta_1$ be the minimum degrees of $G_0$ and $G_1$ respectively, and let $\delta$ be the minimum degree of $G'$. Note that both $\delta_0$ and $\delta_1$ are at least $\delta-1$. By minimality, we have that $|V(G_0)| \geq 2^{\delta_0} \geq 2^{\delta-1}$ and that $|V(G_1)| \geq 2^{\delta_1} \geq 2^{\delta-1}$. Therefore, $|V(G')| \geq 2^{\delta}$, which contradicts that $G'$ is a counterexample.

$\endgroup$
  • $\begingroup$ Do we really need that $\delta_0=\delta_1$ [I did not ubderstand the proof if this in the case when the minimal degree vertuces in $G_0$ have edges to $G_1$]? It looks that it suffices to use that both of them are at least $\delta-1$. $\endgroup$ – Fedor Petrov Aug 15 '17 at 17:54
  • $\begingroup$ @FedorPetrov Yes, it looks like you are right. I simplified the argument as suggested. Thanks! $\endgroup$ – Tony Huynh Aug 15 '17 at 18:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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