El gráfico de Kneser K ( n , 1) es el gráfico completo en n vértices.
El gráfico de Kneser K ( n , 2) es el complemento del gráfico lineal del gráfico completo 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 tiene vértices. Cada vértice tiene exactamente vecinos.
El gráfico de Kneser es transitivo de vértice y transitivo de arco . Cuando , el gráfico de Kneser es un gráfico fuertemente regular , con parámetros . Sin embargo, no es fuertemente regular cuando , ya que diferentes pares de vértices no adyacentes tienen diferentes números de vecinos comunes dependiendo del tamaño de la intersección de los pares de conjuntos correspondientes.
Debido a que los gráficos de Kneser son regulares y transitivos de aristas , su conectividad de vértice es igual a su grado , excepto que está desconectado. Más precisamente, la conectividad de es la misma que el número de vecinos por vértice. [1]
numero cromatico
Como conjeturó Kneser (1956), el número cromático del gráfico de Kneser es exactamente n − 2 k + 2 ; por ejemplo, el gráfico de Petersen requiere tres colores en cualquier coloración adecuada. Esta conjetura fue probada de varias maneras.
En cambio, el número cromático fraccionario de estas gráficas es . [6]
Cuando , no tiene aristas y su número cromático es 1.
ciclos hamiltonianos
Es bien sabido que el gráfico de Petersen no es hamiltoniano , pero durante mucho tiempo se conjeturó que ésta era la única excepción y que cualquier otro gráfico de Kneser conectado K ( n , k ) es hamiltoniano.
En 2003, Chen demostró que el gráfico de Kneser K ( n , k ) contiene un ciclo hamiltoniano si [7]
Desde
se cumple para todos esta condición se cumple si
Casi al mismo tiempo, Shields demostró (computacionalmente) que, excepto el gráfico de Petersen, todos los gráficos de Kneser conectados K ( n , k ) con n ≤ 27 son hamiltonianos. [8]
En 2021, Mütze, Nummenpalo y Walczak demostraron que el gráfico de Kneser K ( n , k ) contiene un ciclo hamiltoniano si existe un número entero no negativo tal que . [9] En particular, el gráfico impar O n tiene un ciclo hamiltoniano si n ≥ 4 . Finalmente, en 2023, Merino, Mütze y Namrata completaron la prueba de la conjetura. [10]
camarillas
Cuando n < 3 k , el gráfico 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 longitud variable. [11]
Diámetro
El diámetro de un gráfico de Kneser conectado K ( n , k ) es [12]
Espectro
El espectro del gráfico de Kneser K ( n , k ) consta de k + 1 valores propios distintos :
además ocurre con multiplicidad para y tiene multiplicidad 1. [13]
El gráfico de Johnson J ( n , k ) es el gráfico cuyos vértices son los k -subconjuntos de elementos de un n -conjunto de elementos, siendo dos vértices adyacentes cuando se encuentran en un ( k − 1) -conjunto de elementos. 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 .
El gráfico de Kneser generalizado K ( n , k , s ) tiene el mismo conjunto de vértices que el gráfico de Kneser K ( n , k ) , pero conecta dos vértices siempre que correspondan a conjuntos que se cruzan en s o menos elementos. [11] Por lo tanto K ( n , k , 0) = K ( n , k ) .
El gráfico bipartito de Kneser 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 una arista siempre que un conjunto es subconjunto del otro. Al igual que el gráfico de Kneser, es transitivo de vértice con grado. El gráfico de Kneser bipartito se puede formar como una doble cubierta bipartita de K ( n , k ) en la que se hacen dos copias de cada vértice y se reemplaza cada arista por un par de aristas que conectan los pares correspondientes. de vértices. [14] El gráfico bipartito de Kneser H (5, 2) es el gráfico de Desargues y el gráfico bipartito de Kneser H ( n , 1) es un gráfico de corona .
Referencias
Notas
^ Watkins (1970).
^ Lovász (1978).
^ Barány (1978).
^ Verde (2002).
^ Matoušek (2004).
^ Godsil y Meagher (2015).
^ Chen (2003).
^ Escudos (2004).
^ Mütze, Nummenpalo y Walczak (2021).
^ Merino, Mütze y Namrata (2023).
^ ab Denley (1997).
^ Valencia-Pabón y Vera (2005).
^ "Copia archivada" (PDF) . www.math.caltech.edu . Archivado desde el original (PDF) el 23 de marzo de 2012 . Consultado el 9 de agosto de 2022 .{{cite web}}: CS1 maint: archived copy as title (link)
^ Simpson (1991).
Trabajos citados
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 hamiltonianos de Kneser sin triángulos", Journal of Combinatorial Theory , Serie B, 89 (1): 1–16, doi :10.1016/S0095-8956(03)00040-6, SEÑOR 1999733
Denley, Tristan (1997), "La circunferencia impar del gráfico de Kneser generalizado", European Journal of Combinatorics , 18 (6): 607–611, doi : 10.1006/eujc.1996.0122 , SEÑOR 1468332
Godsil, Christopher ; Meagher, Karen (2015), Teoremas de Erdős-Ko-Rado: enfoques algebraicos, Estudios de Cambridge en Matemáticas Avanzadas, Cambridge University Press, p. 43, ISBN 9781107128446
Greene, Joshua E. (2002), "Una nueva prueba breve de la conjetura de Kneser", American Mathematical Monthly , 109 (10): 918–920, doi :10.2307/3072460, JSTOR 3072460, MR 1941810
Lovász, László (1978), "Conjetura, número cromático y homotopía de Kneser", Journal of Combinatorial Theory , Serie A, 25 (3): 319–324, doi : 10.1016/0097-3165(78)90022-5 , hdl : 10338.dmlcz/126050 , SEÑOR 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, S2CID 42583803
Mütze, Torsten; Numenpalo, Jerri; Walczak, Bartosz (2021) [STOC 2018], "Los gráficos dispersos de Kneser son hamiltonianos", Journal of the London Mathematical Society , 103 (4), Nueva York: 912–919, arXiv : 1711.01636 , doi :10.1112/jlms.12406, Señor 3826304
Merino, Arturo; Mütze, Torsten; Namrata (2023), "Los gráficos de Kneser son hamiltonianos", Actas del 55º Simposio anual ACM sobre teoría de la computación , págs. 963–970, arXiv : 2212.03918 , doi : 10.1145/3564246.3585137 , ISBN 978-1-4503-9913-5
Shields, Ian Beaumont (2004), Heurística del ciclo de Hamilton en gráficos duros, Ph.D. tesis, Universidad Estatal de Carolina del Norte , archivada desde el original el 17 de septiembre de 2006 , consultado el 1 de octubre de 2006
Simpson, JE (1991), "Gráficos bipartitos hamiltonianos", Actas de la Vigésima Segunda Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Baton Rouge, LA, 1991) , Congressus Numerantium, vol. 85, págs. 97-110, SEÑOR 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 , SEÑOR 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, SEÑOR 0266804