gráfico de Kneser

Gráfico cuyos vértices corresponden a combinaciones de un conjunto de n elementos

En teoría de grafos , el gráfico de Kneser K ( n , k ) (alternativamente KG _{n , k} ) es el gráfico cuyos vértices corresponden a los k -subconjuntos de elementos de un conjunto de n elementos , y donde dos vértices son adyacentes si y sólo si el dos conjuntos correspondientes son disjuntos . Los gráficos de Kneser llevan el nombre de Martin Kneser , quien los investigó por primera vez en 1956.

Ejemplos

Gráfico de Kneser O ₄ = K (7, 3)

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 ₃ = K (5, 2) es el gráfico de Petersen (ver figura superior derecha).

El gráfico de Kneser O ₄ = 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. ${\displaystyle K(n,k)}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n-k}{k}}}$

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. ${\displaystyle k=2}$ ${\displaystyle ({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{2}})}$ ${\displaystyle k>2}$

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] ${\displaystyle K(2k,k)}$ ${\displaystyle K(n,k)}$ ${\displaystyle {\tbinom {n-k}{k}},}$

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. ${\displaystyle K(n,k)}$ ${\displaystyle n\geq 2k}$

• László Lovász demostró esto en 1978 utilizando métodos topológicos, ^[2] dando lugar al campo de la combinatoria topológica .
• Poco después, Imre Bárány hizo una demostración sencilla, utilizando el teorema de Borsuk-Ulam y un lema de David Gale . ^[3]
• Joshua E. Greene ganó el Premio Morgan 2002 por su destacada investigación universitaria por su prueba aún más simplificada pero aún topológica. ^[4]
• En 2004, Jiří Matoušek encontró una prueba puramente combinatoria . ^[5]

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. ${\displaystyle n/k}$ ${\displaystyle n<2k}$ ${\displaystyle K(n,k)}$

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]

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

$${\displaystyle {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right)<\left({\frac {3+{\sqrt {5}}}{2}}\right)k+1}$$se cumple para todos esta condición se cumple si ${\displaystyle k}$

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

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] ${\displaystyle a}$ ${\displaystyle n=2k+2^{a}}$

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] $${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.}$$

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] $${\displaystyle \lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}},\qquad j=0,\ldots ,k.}$$ ${\displaystyle \lambda _{j}}$ ${\displaystyle {\tbinom {n}{j}}-{\tbinom {n}{j-1}}}$ ${\displaystyle j>0}$ ${\displaystyle \lambda _{0}}$

numero 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 ${\displaystyle n\geq 2k}$ $${\displaystyle \alpha (K(n,k))={\binom {n-1}{k-1}}.}$$

Gráficos relacionados

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 . ${\displaystyle {\tbinom {n-k}{k}}.}$

Referencias

Notas

1. Watkins (1970).
2. Lovász (1978).
3. Barány (1978).
4. Verde (2002).
5. Matoušek (2004).
6. Godsil y Meagher (2015).
7. Chen (2003).
8. Escudos (2004).
9. Mütze, Nummenpalo y Walczak (2021).
10. Merino, Mütze y Namrata (2023).
11. Denley (1997).
12. Valencia-Pabón y Vera (2005).
13. "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)
14. 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
• Kneser, Martin (1956), "Aufgabe 360", Jahresbericht der Deutschen Mathematiker-Vereinigung , 58 (2): 27
• 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

enlaces externos

• Weisstein, Eric W. "Gráfico de Kneser". MundoMatemático .
• Weisstein, Eric W. "Gráfico extraño". MundoMatemático .