Inequality involving size of nodes & min degree of graph. - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T04:45:42Z http://mathoverflow.net/feeds/question/77315 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77315/inequality-involving-size-of-nodes-min-degree-of-graph Inequality involving size of nodes & min degree of graph. circuits 2011-10-06T00:04:52Z 2011-10-07T15:19:30Z <p>Context: <a href="http://www.sciencedirect.com/science/article/pii/S0019995882904776" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0019995882904776</a></p> <p>Lemma 1 on 3rd page.</p> <p>Question excerpted / rewritten as follows:</p> <p>(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.</p> <p>mindegree(G'=(V',E')) = minimum degree of any vertex in G.</p> <p>Given: V' is a subset V, E' is a subset of E; d = mindegree((V',E'))</p> <p>Prove: |V'| >= 2^d</p> <p>Thanks!</p> http://mathoverflow.net/questions/77315/inequality-involving-size-of-nodes-min-degree-of-graph/77339#77339 Answer by Tony Huynh for Inequality involving size of nodes & min degree of graph. Tony Huynh 2011-10-06T08:26:42Z 2011-10-07T14:38:12Z <p>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. </p> <p>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 &lt; \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. </p> http://mathoverflow.net/questions/77315/inequality-involving-size-of-nodes-min-degree-of-graph/77427#77427 Answer by Joe Fitzsimons for Inequality involving size of nodes & min degree of graph. Joe Fitzsimons 2011-10-07T06:42:02Z 2011-10-07T06:42:02Z <p>$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'$.</p> <p>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.</p> http://mathoverflow.net/questions/77315/inequality-involving-size-of-nodes-min-degree-of-graph/77458#77458 Answer by Ryan O'Donnell for Inequality involving size of nodes & min degree of graph. Ryan O'Donnell 2011-10-07T15:19:30Z 2011-10-07T15:19:30Z <p>I think the "official" reference for this fact is Section 4 of the following paper of Chung, Furedi, Graham, and Seymour:</p> <p><a href="http://www.math.ucsd.edu/~ronspubs/88_06_induced_cube.pdf" rel="nofollow">http://www.math.ucsd.edu/~ronspubs/88_06_induced_cube.pdf</a></p>