Grafo de Kneser
# Grafo de Kneser

En teoría de grafos, el grafo de Kneser K(n, k) (alternativamente $KG_{n,k})$ es el grafo cuyos vértices corresponden a los subconjuntos de k elementos de un conjunto de n elementos, y donde dos vértices son adyacentes si y solo si los dos correspondientes conjuntos son disjuntos. Los grafos de Kneser llevan el nombre de Martin Kneser, quien los investigó por primera vez en 1956.

## Ejemplos

El grafo de Kneser K(n, 1) es el grafo completo de n vértices.

El grafo de Kneser K(n, 2) es el complemento del grafo línea del grafo completo sobre n vértices.

El grafo de Kneser K(2n − 1, n − 1) es el grafo impar $O_n;$ en particular, $O_3=$ K(5, 2) es el grafo de Petersen (véase la figura de la parte superior derecha).

El grafo de Kneser $O_4=$ K(7, 3), visualizado a la derecha.

## Propiedades

### Propiedades básicas

* El grafo de Kneser $K(n,k)$ tiene ${\tbinom {n}{k}}$ vértices. Cada vértice tiene exactamente ${\tbinom {n-k}{k}}$ vecinos.
* El grafo de Kneser es transitivo de vértices y arco transitivo.
* Cuando $k=2$, el grafo de Kneser es un grafo fuertemente regular, con parámetros $({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{2}})$. Sin embargo, no es muy regular cuando $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 $K(2k,k)$ que está desconectado. Más precisamente, la conectividad de $K(n,k)$ es ${\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 $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 $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):

       $n\geq {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right).$
    Ya que
       ${\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
       $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 $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):

       $\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:

       $\lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}},\qquad j=0,\ldots ,k.$
    Además $\lambda _{j}$ aparece con multiplicidad ${\tbinom {n}{j}}-{\tbinom {n}{j-1}}$ para $j>0$ y $\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 $n\geq 2k$ es

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

## Grafos relacionados

El grafo de Johnson J(n, k) es aquel cuyos vértices son los subconjuntos de k elementos de un conjunto de n elementos, siendo dos vértices adyacentes cuando se encuentran en un conjunto de (k − 1) elementos. El grafo de Johnson J(n, 2) es el complemento del grafo de Kneser K(n, 2). Los grafos de Johnson están estrechamente relacionados con el esquema de Johnson, que llevan el nombre de Selmer M. Johnson.

El grafo de Kneser generalizado K(n, k, s) tiene el mismo conjunto de vértices que el grafo de Kneser K(n, k), pero conecta dos vértices siempre que correspondan a conjuntos que se cruzan en s o menos elementos (Denley, 1997). Así K(n, k, 0)= K(n, k).

El grafo de Kneser bipartito H(n, k) tiene como vértices los conjuntos de k y de n − k elementos extraídos de una colección de n elementos. Dos vértices están conectados por una arista siempre que un conjunto es un subconjunto del otro. Al igual que el grafo de Kneser, es vértice transitivo con grado ${\tbinom {n-k}{k}}.$. El grafo de Kneser bipartito se puede formar como un recubrimiento doble bipartito de K(n, k) en el que se hacen dos copias de cada vértice y se reemplaza cada vínculo por un par de vínculos que conectan los correspondientes pares de vértices (Simpson, 1991). El grafo de Kneser bipartito H(5, 2) es el grafo de Desargues y el grafo de Kneser bipartito H(n, 1) es un grafo en corona.

