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 at 18:07
can you explain a bit more :(... – DiscreteMath'sFan Jan 17 at 18:08
– Jan Dvorak Jan 17 at 18:10
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 at 18:14
I can't find a way how to solve the problem with this... – DiscreteMath'sFan Jan 17 at 18:14
show 1 more comment

2 Answers

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 at 18:21
thanks, I will try to solve it with it. If anyone has another ideas, please write them :) – DiscreteMath'sFan Jan 17 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) – dudelgrincen Jan 21 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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 34, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9164939522743225, "perplexity_flag": "middle"}