Inequality involving size of nodes & min degree of graph. - MathOverflow

Inequality involving size of nodes & min degree of graph.

2011-10-06T00:04:52Z

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!

Answer by Tony Huynh for Inequality involving size of nodes & min degree of graph.

2011-10-06T08:26:42Z

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.

Answer by Joe Fitzsimons for Inequality involving size of nodes & min degree of graph.

2011-10-07T06:42:02Z

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

Answer by Ryan O'Donnell for Inequality involving size of nodes & min degree of graph.

2011-10-07T15:19:30Z

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