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 elementos k de un conjunto de n elementos , y donde dos vértices son adyacentes si y solo si el dos conjuntos correspondientes son inconexos . Los gráficos de Kneser llevan el nombre de Martin Kneser , quien los investigó por primera vez en 1955.
Gráfico de Kneser | |
---|---|
![]() El gráfico de Kneser K (5, 2) , isomorfo al gráfico de Petersen | |
Lleva el nombre de | Martin Kneser |
Vértices | |
Bordes | |
Número cromático | |
Propiedades | -arco regular -transitivo |
Notación | K ( n , k ), KG n , k . |
Tabla de gráficos y parámetros |
Ejemplos de
El gráfico de Kneser K ( n , 1) es el gráfico completo en n vértices.
La gráfica de Kneser K ( n , 2) es el complemento de la gráfica lineal de la gráfica completa en n vértices.
El gráfico de Kneser K (2 n - 1, n - 1) es el gráfico impar O n ; en particular, O 3 = K (5, 2) es el gráfico de Petersen (ver figura superior derecha).
El gráfico de Kneser O 4 = K (7, 3) , visualizado a la derecha.
Propiedades
Propiedades básicas
- El gráfico de Kneser K ( n , k ) tienevértices. Cada vértice tiene exactamente vecinos.
- El gráfico de Kneser es transitivo de vértice y de arco transitivo . Sin embargo, en general, no es un gráfico fuertemente regular , ya que diferentes pares de vértices no adyacentes tienen diferentes números de vecinos comunes dependiendo del tamaño de la intersección del par de conjuntos correspondiente.
- Debido a que los gráficos de Kneser son regulares y transitivos por los bordes , su conectividad de vértice es igual a su grado , excepto K (2 k , k ) que está desconectado. Más precisamente, la conectividad de K ( n , k ) eslo mismo que el número de vecinos por vértice ( Watkins 1970 ).
Número cromático
Como conjeturaba Kneser ( 1955 ), el número cromático del gráfico de Kneser K ( n , k ) paraes exactamente n - 2 k + 2 ; por ejemplo, el gráfico de Petersen requiere tres colores en cualquier coloración adecuada. Esta conjetura se demostró de varias formas.
- László Lovász ( 1978 ) lo demostró utilizando métodos topológicos, dando lugar al campo de la combinatoria topológica .
- Poco después, Imre Bárány ( 1978 ) dio una demostración simple, utilizando el teorema de Borsuk-Ulam y un lema de David Gale .
- Joshua E. Greene ( 2002 ) ganó el Premio Morgan por una prueba aún más simplificada pero topológica.
- Jiří Matoušek ( 2004 ) encontró una prueba puramente combinatoria .
Cuándo , el número cromático de K ( n , k ) es 1.
Ciclo hamiltoniano
- El gráfico de Kneser K ( n , k ) contiene un ciclo hamiltoniano si ( Chen 2003 ):
- Desde
- Se cumple para todo k esta condición se satisface si
- El gráfico de Kneser K ( n , k ) contiene un ciclo hamiltoniano si existe un número entero no negativo a tal que( Mütze, Nummenpalo y Walczak 2018 ). En particular, el gráfico impar O n tiene un ciclo hamiltoniano si n ≥ 4 .
- Con la excepción del gráfico de Petersen, todos los gráficos de Kneser conectados K ( n , k ) con n ≤ 27 son hamiltonianos ( Shields 2004 ).
Camarillas
- Cuando n <3 k , la gráfica de Kneser K ( n , k ) no contiene triángulos. De manera más general, cuando n < ck no contiene camarillas de tamaño c , mientras que sí las contiene cuando n ≥ ck . Además, aunque el gráfico de Kneser siempre contiene ciclos de longitud cuatro siempre que n ≥ 2 k + 2 , para valores de n cercanos a 2 k, el ciclo impar más corto puede tener una duración no constante ( Denley 1997 ).
Diámetro
- El diámetro de un gráfico de Kneser conectado K ( n , k ) es ( Valencia-Pabon & Vera 2005 ):
Espectro
- El espectro del gráfico de Kneser K ( n , k ) consta de k + 1 autovalores distintos :
- es más ocurre con multiplicidad por y tiene multiplicidad 1. Consulte este documento para obtener una prueba.
Número de independencia
- El teorema de Erdős-Ko-Rado establece que el número de independencia del gráfico de Kneser K ( n , k ) para es
Gráficos relacionados
El gráfico de Johnson J ( n , k ) es el gráfico 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 elementos ( k - 1) . El gráfico de Johnson J ( n , 2) es el complemento del gráfico de Kneser K ( n , 2) . Los gráficos de Johnson están estrechamente relacionados con el esquema de Johnson , y ambos llevan el nombre de Selmer M. Johnson .
La generalizada Kneser gráfico K ( n , k , s ) tiene el mismo conjunto de vértices como el Kneser gráfico K ( n , k ) , pero conecta dos vértices siempre que corresponden a los conjuntos que se cruzan en s o menos elementos ( Denley 1997 ). Por tanto, K ( n , k , 0) = K ( n , k ) .
El gráfico de Kneser bipartito H ( n , k ) tiene como vértices los conjuntos de k y n - k elementos extraídos de una colección de n elementos. Dos vértices están conectados por un borde siempre que un conjunto sea un subconjunto del otro. Al igual que el gráfico de Kneser, es un vértice transitivo con gradoEl gráfico de Kneser bipartito se puede formar como una cubierta doble bipartita de K ( n , k ) en la que se hacen dos copias de cada vértice y se reemplaza cada borde por un par de bordes que conectan los pares de vértices correspondientes ( Simpson 1991 ). El gráfico de Kneser bipartito H (5, 2) es el gráfico de Desargues y el gráfico de Kneser bipartito H ( n , 1) es un gráfico de corona .
Referencias
- Bárány, Imre (1978), "Una breve prueba de la conjetura de Kneser", Journal of Combinatorial Theory, Serie A , 25 (3): 325–326, doi : 10.1016 / 0097-3165 (78) 90023-7 , MR 0514626
- Chen, Ya-Chen (2003), "Gráficos de Kneser hamiltonianos sin triángulos", Journal of Combinatorial Theory, Serie B , 89 (1): 1-16, doi : 10.1016 / S0095-8956 (03) 00040-6 , MR 1999733
- Denley, Tristan (1997), "La extraña circunferencia del gráfico de Kneser generalizado", European Journal of Combinatorics , 18 (6): 607–611, doi : 10.1006 / eujc.1996.0122 , MR 1468332
- Greene, Joshua E. (2002), "Una nueva prueba corta de la conjetura de Kneser", American Mathematical Monthly , 109 (10): 918–920, doi : 10.2307 / 3072460 , JSTOR 3072460 , MR 1941810
- Kneser, Martin (1955), "Aufgabe 360", Jahresbericht der Deutschen Mathematiker-Vereinigung , 58 (2): 27
- Lovász, László (1978), "Conjetura de Kneser, número cromático y homotopía", Journal of Combinatorial Theory , Serie A, 25 (3): 319–324, doi : 10.1016 / 0097-3165 (78) 90022-5 , hdl : 10338.dmlcz / 126.050 , MR 0514625
- Matoušek, Jiří (2004), "Una prueba combinatoria de la conjetura de Kneser", Combinatorica , 24 (1): 163-170, doi : 10.1007 / s00493-004-0011-1 , hdl : 20.500.11850 / 50671 , MR 2057690
- Mütze, Torsten; Nummenpalo, Jerri; Walczak, Bartosz (2018), "Sparse Kneser graphs are hamiltonian", STOC'18 — Actas del 50º Simposio Anual de ACM SIGACT sobre Teoría de la Computación , Nueva York: ACM, págs. 912–919, arXiv : 1711.01636 , MR 3826304
- Shields, Ian Beaumont (2004), Heurística del ciclo de Hamilton en Hard Graphs , Ph.D. tesis, Universidad Estatal de Carolina del Norte , archivado desde el original el 17 de septiembre de 2006 , consultado el 1 de octubre de 2006
- Simpson, JE (1991), "Hamiltonian bipartite graphs", Actas de la 22a Conferencia del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Baton Rouge, LA, 1991) , Congressus Numerantium , 85 , págs. 97-110, MR 1152123
- Valencia-Pabón, Mario; Vera, Juan-Carlos (2005), "Sobre el diámetro de las gráficas de Kneser", Matemáticas discretas , 305 (1–3): 383–385, doi : 10.1016 / j.disc.2005.10.001 , MR 2186709
- Watkins, Mark E. (1970), "Conectividad de gráficos transitivos", Journal of Combinatorial Theory , 8 : 23-29, doi : 10.1016 / S0021-9800 (70) 80005-9 , MR 0266804
enlaces externos
- Weisstein, Eric W. "Gráfico de Kneser" . MathWorld .
- Weisstein, Eric W. "Gráfico impar" . MathWorld .