Grafo de Kneser

Propiedades básicas

• El grafo de Kneser ${\displaystyle K(n,k)}$ tiene ${\displaystyle {\tbinom {n}{k}}}$ vértices. Cada vértice tiene exactamente ${\displaystyle {\tbinom {n-k}{k}}}$ vecinos.
• El grafo de Kneser es transitivo de vértices y arco transitivo.
• Cuando ${\displaystyle k=2}$, el grafo de Kneser es un grafo fuertemente regular, con parámetros ${\displaystyle ({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{2}})}$. Sin embargo, no es muy regular cuando ${\displaystyle k>2}$, ya que diferentes pares de vértices no adyacentes tienen diferentes números de vecinos comunes según el tamaño de la intersección de los correspondientes pares de conjuntos.
• Debido a que los grafos de Kneser son regulares y transitivo de vínculos, su conectividad de vértices es igual a su grado, excepto por ${\displaystyle K(2k,k)}$ que está desconectado. Más precisamente, la conectividad de ${\displaystyle K(n,k)}$ es ${\displaystyle {\tbinom {n-k}{k}},}$ igual al número de vecinos por vértice (Watkins, 1970).

Número cromático

Como conjeturó txt,, el coloreado del grafo de Kneser K(n, k) para ${\displaystyle n\geq 2k}$ es exactamente n − 2k + 2. Por ejemplo, el grafo de Petersen requiere tres colores en cualquier coloración propia. Esta conjetura se ha demostrado de varias maneras.

• txt, demostró esto utilizando métodos topológicos, dando lugar al campo de la combinatoria topológica.
• Poco tiempo después,txt, dio una prueba simple, usando el teorema de Borsuk-Ulam y un lema de David Gale.
• txt, ganó el premio Morgan por una prueba aún más simplificada pero todavía topológica.
• txt, encontró una prueba combinatoria puramente.

Cuando ${\displaystyle n<2k}$, el número cromático de K(n, k) es 1.

Ciclo hamiltoniano

• El grafo de Kneser K(n, k) contiene un camino hamiltoniano si (Chen, 2003):

${\displaystyle n\geq {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right).}$

Ya que

${\displaystyle {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right)<\left({\frac {3+{\sqrt {5}}}{2}}\right)k+1,}$

válido para todo k. Esta condición se cumple si

${\displaystyle n\geq \left({\frac {3+{\sqrt {5}}}{2}}\right)k+1\approx 2.62k+1.}$

• El grafo de Kneser K(n, k) contiene un ciclo hamiltoniano si existe un entero no negativo a tal que ${\displaystyle n=2k+2^{a}}$ (Mütze, Nummenpalo y Walczak, 2018). En particular, el grafo impar O_n tiene un ciclo hamiltoniano si n ≥ 4.
• Con la excepción del grafo de Petersen, todos los grafos de Kneser conectados K(n, k) con n ≤ 27 son hamiltonianos (Shields, 2004).

Cliques

• Cuando n < 3k, el grafo de Kneser K(n, k) no contiene triángulos. De manera más general, cuando n < ck no contiene cliques de tamaño c, mientras que contiene tales cliques cuando n ≥ ck. Además, aunque el grafo de Kneser siempre contiene ciclos de longitud cuatro siempre que n ≥ 2k + 2, para valores de n cercanos a 2k, el ciclo impar más corto puede tener una longitud variable (Denley, 1997).

Diámetro

• El diámetro de un grafo de Kneser conectado K(n, k) es (Valencia-Pabon y Vera, 2005):

${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.}$

Espectro

• El espectro del grafo de Kneser K(n, k) consta de k + 1 autovalores distintos:

${\displaystyle \lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}},\qquad j=0,\ldots ,k.}$

Además ${\displaystyle \lambda _{j}}$ aparece con multiplicidad ${\displaystyle {\tbinom {n}{j}}-{\tbinom {n}{j-1}}}$ para ${\displaystyle j>0}$ y ${\displaystyle \lambda _{0}}$ tiene multiplicidad 1.

Número de independencia

• El teorema Erdős-Ko-Rado establece que el conjunto independiente del grafo de Kneser K(n, k) para ${\displaystyle n\geq 2k}$ es

${\displaystyle \alpha (K(n,k))={\binom {n-1}{k-1}}.}$