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

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

Lemma 1 on 3rd page.

Question excerpted / rewritten as follows:

(V,E) = a graph on {0,1}^n, where there is an edge between x, x' iff (x,x') differ in exactly one coordinate. I.e., |V| = 2^n, |E| = 2^n * n /2.

mindegree(G'=(V',E')) = minimum degree of any vertex in G.

Given: V' is a subset V, E' is a subset of E; d = mindegree((V',E'))

Prove: |V'| >= 2^d

Thanks!

share|improve this question
add comment

3 Answers

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

share|improve this answer
add comment

Let $G'=(V',E')$ be a counterexample with $|V'|+|E'|$ 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'$. If $\delta_0 < \delta_1$, then deleting any edge of $G_1$ does not change the minimum degree of $G'$. Thus, by choice of $G'$, we have $\delta_0=\delta_1$. By minimality, we have that $|V(G_0)| \geq 2^{\delta_0}$ and that $|V(G_1)| \geq 2^{\delta_1}$. Therefore, $|V(G')| \geq 2^{\delta_0+1}$. But $\delta \leq \delta_0+1$, which contradicts that $G'$ is a counterexample.

share|improve this answer
add comment

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

share|improve this answer
    
It looks like they prove something slightly stronger in fact. Namely $|V'| \geq 2^d$' where $d$ is the average degree of $G$. –  Tony Huynh Oct 8 '11 at 5:32
add comment

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.