# Hypercube problem

$B$ is an n-dimensional hypercube, considered as undirected graph. Let $A$ be a subset of the vertices of $B$ such that $|A| \gt 2^{n-1}$.

Let $H$ is a subgraph of $B$ induced by $A$. Prove that $H$ has at least $n$ edges.

Any help, would be greatly appreciated.

-
Why does it seem like a Ramsey-theory-type problem? –  Jan Dvorak Jan 17 '13 at 18:07
can you explain a bit more :(... –  DiscreteMath'sFan Jan 17 '13 at 18:08
Basically, the original problem in Ramsey theory says that if you have a large enough complete graph and color its edges by $n$ colors, you are destined to find a single-colored complete subgraph of a given size in the graph, for every such size. Namely, every edge-2-colored $K_6$ contains a single-colored $K_3$ (triangle). –  Jan Dvorak Jan 17 '13 at 18:14
I can't find a way how to solve the problem with this... –  DiscreteMath'sFan Jan 17 '13 at 18:14

Temporarily consider one of the $n$ coordinate axes. Your hypercube has $2^{n-1}$ edges parallel to that axis. Since $B$ has more than $2^{n-1}$ vertices, it must have two on the same one of those $2^{n-1}$ edges. So $H$ has an edge parallel to the coordinate axis under consideration. Apply this to all $n$ of the axes.

-
+1 Nice answer! Looks like you wrote $B$ instead of $A$ above. –  polkjh Jan 17 '13 at 18:21
thanks, I will try to solve it with it. If anyone has another ideas, please write them :) –  DiscreteMath'sFan Jan 17 '13 at 18:23
there is simpler combinatoric solution Ill post tommorow (I can not post the solution now since this problem was homework for me and my fellow-students) –  bteo Jan 21 '13 at 16:20

We can build n-dimensional hypercube using two $(n-1)$-dimensional hypercubes. This gives us the vertices set power $|Vn| = 2^{n}$ for the n-dimensional hypercube Gn(Vn, En). Knowing |Vn-1| and |En-1| for (n-1)-dimensional hypercube we know |En| for n-dimensional hypercube. |En| = 2*|En-1| + $2^{n-1}$.

Solving this recurrence relation gives us |En| for any dimension. |En| = $n*2^{n-1}$.

Then we choose at least $(2^{n-1}+1)$ vertices to be in the $A$ subset by choosing at most $(2^{n-1} - 1)$ vertices that wont be in $A$. We know that every vertex in $n$-dimensional hypercube is connected to $n$ edges (or less if we remove some vertices). So removing the maximum of $(2^{n-1} - 1)$ vertices removes no more than $r = (2^{n-1} - 1)*n$ edges. $r = (2^{n-1} - 1)*n = |En| - n$.

It appers that the induced graph H has at least |En| - r edges. |En| - r = |En| - (|En| - n) = n. We can conclude that H has at least n edges.

Sorry if there is something unclear. English is not my native language. I would be glad if someone improves my post. I've done my best to format it and make it readable but I am new to LaTeX and I preferred not to use it for now.

-