Los vértices de la $n$-cubo dimensional están pintadas en dos colores. El número de vértices de cada color es la misma ($2^{n-1}$). Demostrar que al menos $2^{n-1}$ aristas conectan los vértices de diferentes colores.
Respuesta
¿Demasiados anuncios?
La pregunta puede ser formulada de la siguiente manera: para cualquier subconjunto $S$ $2^{n-1}$ vértices en el $n$-dimensiones hipercubo gráfico de $H_n$, muestran que $|\delta(S)|\ge2^{n-1}$, donde $$\delta(S) := \{(u,v)\mid u\in S, v\notin S\}$$ es el límite de $S$.
Es un resultado estándar de gráfico espectral teoría de que, para cualquier subconjunto $S$ de un gráfico de $G$, $$|\delta(S)| \ge \lambda_2 |S| (1-|S|/|V(G)|)$$ donde $0=\lambda_1\le\lambda_2\le\cdots\le\lambda_{n-1}$ son los autovalores de la Laplaciano de $G$.
Ahora, $H_n$ $n$veces (Cartesiano) gráfico producto de la gráfica de $H_1$ tener dos vértices y aristas. Los autovalores de (el Laplaciano de) $H_1$$0$$2$, y de ello se sigue que los autovalores de a$H_n$$0, 2,\ldots, 2n$, cada una con multiplicidad $\binom nk$. Así, por $H_n$,$\lambda_2=2$; de ello se sigue que si $|S|=2^{n-1}$, tenemos $$|\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},$$ como se requiere.
Una referencia que parece tener todo esto, con algo más de detalle, es Alexandra Kolla de notas de la conferencia.
