The vertices of the $n$-dimensional cube are painted in two colors. The number of vertices of each color is the same ($2^{n-1}$). Prove that at least $2^{n-1}$ edges connect vertices of different colors.

  • $\begingroup$ Do you mean coloring in the graph-theoretical sense, i.e., coloring of the hypercube $Q_n$? $\endgroup$ – user12344567 Jun 26 '15 at 10:42
  • $\begingroup$ @ blazs: No, I mean arbitrary painting of hypercube. $\endgroup$ – grizzly Jun 26 '15 at 10:46
  • $\begingroup$ Ok, just to make perfectly sure: you allow vertices connected by an edge to have the same color? $\endgroup$ – user12344567 Jun 26 '15 at 10:47
  • 1
    $\begingroup$ Yes, of course. $\endgroup$ – grizzly Jun 26 '15 at 10:48
  • $\begingroup$ @grizzly Where did this problem come from? What have you tried? $\endgroup$ – Tad Jun 27 '15 at 0:02

The question can be phrased as follows: for any subset $S$ of $2^{n-1}$ vertices in the $n$-dimensional hypercube graph $H_n$, show that $|\delta(S)|\ge2^{n-1}$, where $$\delta(S) := \{(u,v)\mid u\in S, v\notin S\}$$ is the boundary of $S$.

It is a standard result of spectral graph theory that, for any subset $S$ of a graph $G$, $$|\delta(S)| \ge \lambda_2 |S| (1-|S|/|V(G)|)$$ where $0=\lambda_1\le\lambda_2\le\cdots\le\lambda_{n-1}$ are the eigenvalues of the Laplacian of $G$.

Now, $H_n$ is the $n$-fold (Cartesian) graph product of the graph $H_1$ having two vertices and one edge. The eigenvalues of (the Laplacian of) $H_1$ are $0$ and $2$, and it follows that the eigenvalues of $H_n$ are $0, 2,\ldots, 2n$, each with multiplicity $\binom nk$. Thus, for $H_n$, we have $\lambda_2=2$; it follows that if $|S|=2^{n-1}$, we have $$|\delta(S)| \ge \lambda_2 |S| (1-|S|/|V(H_n)|)=2\cdot 2^{n-1}\cdot(1-2^{n-1}/2^n)=2^{n-1},$$ as required.

One reference which seems to have all of this, with some more detail, is Alexandra Kolla's lecture notes.

  • $\begingroup$ Thank you for an interesting solution. I have not studied the graph theory, but I was able to understand it in general terms. I know that combinatorics and graph theory are connected. But here it is at such a depth... It is impressive! $\endgroup$ – grizzly Jun 27 '15 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.