Grafo de Kneser

En teoría de grafos, el grafo de Kneser Plantilla:Math (alternativamente Plantilla:Math) es el grafo cuyos vértices corresponden a los [[combinatoria|subconjuntos de Plantilla:Mvar elementos de un conjunto de Plantilla:Mvar 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 Plantilla:Math es el grafo completo de Plantilla:Mvar vértices.

El grafo de Kneser Plantilla:Math es el complemento del grafo línea del grafo completo sobre Plantilla:Mvar vértices.

El grafo de Kneser Plantilla:Math es el grafo impar Plantilla:Math; en particular, Plantilla:Math es el grafo de Petersen (véase la figura de la parte superior derecha).

El grafo de Kneser Plantilla:Math, visualizado a la derecha.

Propiedades

Propiedades básicas

El grafo de Kneser $K (n, k)$ tiene $(\binom{n}{k})$ vértices. Cada vértice tiene exactamente $(\binom{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 $((\binom{n}{2}), (\binom{n - 2}{2}), (\binom{n - 4}{2}), (\binom{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 (2 k, k)$ que está desconectado. Más precisamente, la conectividad de $K (n, k)$ es $(\binom{n - k}{k}),$ igual al número de vecinos por vértice Plantilla:Harv.

Plantilla:AnchorNúmero cromático

Como conjeturó Plantilla:Harvsp, el coloreado del grafo de Kneser Plantilla:Math para $n \geq 2 k$ es exactamente Plantilla:Math. Por ejemplo, el grafo de Petersen requiere tres colores en cualquier coloración propia. Esta conjetura se ha demostrado de varias maneras.

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

Cuando $n < 2 k$ , el número cromático de Plantilla:Math es 1.

Ciclo hamiltoniano

El grafo de Kneser Plantilla:Math contiene un camino hamiltoniano si Plantilla:Harv:

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

Ya que

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

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

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

El grafo de Kneser Plantilla:Math contiene un ciclo hamiltoniano si existe un entero no negativo a tal que $n = 2 k + 2^{a}$ Plantilla:Harv. En particular, el grafo impar Plantilla:Mvar tiene un ciclo hamiltoniano si Plantilla:Math.
Con la excepción del grafo de Petersen, todos los grafos de Kneser conectados Plantilla:Math con Plantilla:Math son hamiltonianos Plantilla:Harv.

Cliques

Cuando Plantilla:Math, el grafo de Kneser Plantilla:Math no contiene triángulos. De manera más general, cuando Plantilla:Math no contiene cliques de tamaño Plantilla:Math, mientras que contiene tales cliques cuando Plantilla:Math. Además, aunque el grafo de Kneser siempre contiene ciclos de longitud cuatro siempre que Plantilla:Math, para valores de Plantilla:Mvar cercanos a Plantilla:Math, el ciclo impar más corto puede tener una longitud variable Plantilla:Harv.

Diámetro

El diámetro de un grafo de Kneser conectado Plantilla:Math es Plantilla:Harv:

⌈ \frac{k - 1}{n - 2 k} ⌉ + 1 .

Espectro

El espectro del grafo de Kneser Plantilla:Math consta de k + 1 autovalores distintos:

λ_{j} = (- 1)^{j} (\binom{n - k - j}{k - j}), j = 0, \dots, k .

Además

λ_{j}

aparece con multiplicidad

(\binom{n}{j}) - (\binom{n}{j - 1})

para

j > 0

y

λ_{0}

tiene multiplicidad 1.^[1]

Número de independencia

El teorema Erdős-Ko-Rado establece que el conjunto independiente del grafo de Kneser Plantilla:Math para $n \geq 2 k$ es

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

Grafos relacionados

El grafo de Johnson Plantilla:Math es aquel cuyos vértices son los subconjuntos de Plantilla:Mvar elementos de un conjunto de Plantilla:Mvar elementos, siendo dos vértices adyacentes cuando se encuentran en un conjunto de Plantilla:Math elementos. El grafo de Johnson Plantilla:Math es el complemento del grafo de Kneser Plantilla:Math. 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 Plantilla:Math tiene el mismo conjunto de vértices que el grafo de Kneser Plantilla:Math, pero conecta dos vértices siempre que correspondan a conjuntos que se cruzan en Plantilla:Mvar o menos elementos Plantilla:Harv. Así Plantilla:Math.

El grafo de Kneser bipartito Plantilla:Math tiene como vértices los conjuntos de Plantilla:Mvar y de Plantilla:Math elementos extraídos de una colección de Plantilla:Mvar 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 $(\binom{n - k}{k}) .$ . El grafo de Kneser bipartito se puede formar como un recubrimiento doble bipartito de Plantilla:Math 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 Plantilla:Harv. El grafo de Kneser bipartito Plantilla:Math es el grafo de Desargues y el grafo de Kneser bipartito Plantilla:Math es un grafo en corona.

Referencias

Plantilla:Listaref

Bibliografía

Enlaces externos

Plantilla:Control de autoridades

↑ Plantilla:Cite web

[1] Plantilla:Cite web

[1]

Grafo de Kneser

Sumario

Ejemplos

Propiedades

Propiedades básicas

Plantilla:AnchorNúmero cromático

Ciclo hamiltoniano

Cliques

Diámetro

Espectro

Número de independencia

Grafos relacionados

Referencias

Bibliografía

Enlaces externos

Menú de navegación

Grafo de Kneser

Ejemplos

Propiedades

Propiedades básicas

Plantilla:AnchorNúmero cromático

Ciclo hamiltoniano

Cliques

Diámetro

Espectro

Número de independencia

Grafos relacionados

Referencias

Bibliografía

Enlaces externos

Menú de navegación

Buscar