Problema del hipercubo

Question

$B$ es un hipercubo de n dimensiones, considerado como un grafo no dirigido. Sea $A$ sea un subconjunto de los vértices de $B$ tal que $|A| \gt 2^{n-1}$ .

Dejemos que $H$ es un subgrafo de $B$ inducido por $A$ . Demostrar que $H$ tiene al menos $n$ bordes.

Cualquier ayuda será muy apreciada.

Answer 1

Considerar temporalmente uno de los $n$ ejes de coordenadas. Su hipercubo tiene $2^{n-1}$ bordes paralelos a ese eje. Como $B$ tiene más que $2^{n-1}$ vértices, debe tener dos en el mismo de esos $2^{n-1}$ bordes. Así que $H$ tiene una arista paralela al eje de coordenadas considerado. Aplique esto a todos los $n$ de los ejes.

Answer 2

Podemos construir n -hipercubo dimensional utilizando dos $(n-1)$ -hipercubos dimensionales. Esto nos da la potencia del conjunto de vértices $|Vn| = 2^{n}$ para el hipercubo n-dimensional Gn(Vn, En) . Conociendo |Vn-1| y |En-1| para (n-1) -hipercubo dimensional sabemos que |En|En| para n -hipercubo de dimensiones. |En| = 2*|En-1| + $2^{n-1}$ .

Resolviendo esta relación de recurrencia obtenemos |En|En| para cualquier dimensión. |En| = $n*2^{n-1}$ .

Entonces elegimos al menos $(2^{n-1}+1)$ vértices para estar en el $A$ subconjunto eligiendo como máximo $(2^{n-1} - 1)$ vértices que no estarán en $A$ . Sabemos que cada vértice de $n$ -El hipercubo de dimensiones está conectado a $n$ aristas (o menos si eliminamos algunos vértices). Así que eliminar el máximo de $(2^{n-1} - 1)$ vértices elimina no más de $r = (2^{n-1} - 1)*n$ bordes. $r = (2^{n-1} - 1)*n = |En| - n$ .

Parece que el gráfico inducido H tiene al menos |En| - r bordes. |En| - r = |En| - (|En| - n) = n. Podemos concluir que H tiene al menos n bordes.

Disculpe si hay algo que no está claro. El inglés no es mi lengua materna. Me gustaría que alguien mejorara mi mensaje. He hecho todo lo posible para darle formato y hacerlo legible, pero soy nuevo en LaTeX y he preferido no usarlo por ahora.