Gráfica 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 conjuntos correspondientes son disjuntos . Los grafos de Kneser reciben su nombre de Martin Kneser , quien los investigó por primera vez en 1956.

Ejemplos

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

El grafo de Kneser $K (n, 2)$ es el complemento del grafo lineal del grafo 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 la 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. $K(n,k)$ ${\tbinom {n}{k}}$ ${\tbinom {nk}{k}}$

El grafo de Kneser es transitivo por vértices y transitivo por arcos . Cuando , el grafo de Kneser es un grafo 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. ${\estilo de visualización k=2}$ $({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{ 2}})$ $k>2$

Debido a que los grafos de Kneser son regulares y transitivos en sus aristas , su conectividad de vértices 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] ${\estilo de visualización K(2k,k)}$ $K(n,k)$ ${\tbinom {nk}{k}},$

Número cromático

Como conjeturó Kneser (1956) , el número cromático del gráfico de Kneser para es 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 maneras. $K(n,k)$ ${\estilo de visualización n\geq 2k}$

László Lovász lo demostró en 1978 utilizando métodos topológicos , ^[2] dando origen al campo de la combinatoria topológica .
Poco después, Imre Bárány dio una prueba sencilla, utilizando el teorema de Borsuk-Ulam y un lema de David Gale . ^[3]
Joshua E. Greene ganó el Premio Morgan 2002 a la investigación universitaria destacada 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]

Por el contrario, el número cromático fraccionario de estos grafos es . ^[6] Cuando , no tiene aristas y su número cromático es 1. ${\estilo de visualización n/k}$ ${\estilo de visualización n<2k}$ $K(n,k)$

Ciclos hamiltonianos

Es bien sabido que el gráfico de Petersen no es hamiltoniano , pero durante mucho tiempo se conjeturó que esta era la única excepción y que cualquier otro gráfico de Kneser conexo $K (n, k)$ es hamiltoniano.

En 2003, Chen demostró que el gráfico de Kneser $K (n, k)$ contiene un ciclo hamiltoniano si ^[7]

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

Desde

{\frac {1}{2}}(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 ${\estilo de visualización k}$

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 \leq 27$ son hamiltonianos. ^[8]

En 2021, Mütze, Nummenpalo y Walczak demostraron que el grafo de Kneser $K (n, k)$ contiene un ciclo hamiltoniano si existe un entero no negativo tal que . ^[9] En particular, el grafo impar $O$ $n$ tiene un ciclo hamiltoniano si $n$ $\geq 4$ . Finalmente, en 2023, Merino, Mütze y Namrata completaron la prueba de la conjetura. ^[10] ${\estilo de visualización a}$ $Estilo de visualización n=2k+2^{a}}$

Camarillas

Cuando $n < 3 k$ , el grafo de Kneser $K (n, k)$ no contiene triángulos. En términos más generales, cuando $n < ck$ no contiene camarillas de tamaño $c$ , mientras que sí contiene dichas camarillas cuando $n \geq ck$ . Además, aunque el grafo de Kneser siempre contiene ciclos de longitud cuatro siempre que $n \geq 2 k + 2$ , para valores de $n$ cercanos a $2 k$ el ciclo impar más corto puede tener longitud variable. ^[11]

Diámetro

El diámetro de un grafo de Kneser conexo $K (n, k)$ es ^[12] $\left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.$

Espectro

El espectro del grafo de Kneser $K (n, k)$ consta de k + 1 valores propios distintos : Además ocurre con multiplicidad para y tiene multiplicidad 1. ^[13] $\lambda _{j}=(-1)^{j}{\binom {nkj}{kj}},\qquad j=0,\ldots ,k.$ $\lambda _{j}$ ${\tbinom {n}{j}}-{\tbinom {n}{j-1}}$ $j>0$ $\lambda _{0}$

Número de independencia

El teorema de Erdős–Ko–Rado establece que el número de independencia del grafo de Kneser $K (n, k)$ para es ${\estilo de visualización n\geq 2k}$ $\alpha (K(n,k))={\binom {n-1}{k-1}}.$

Gráficos relacionados

El grafo de Johnson $J (n, k)$ es el grafo 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 , ambos nombrados en honor a 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 intersecan en $s$ o menos elementos. ^[11] Por lo tanto, $K (n, k, 0) = K (n, k)$ .

El grafo 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 sea un subconjunto del otro. Al igual que el grafo de Kneser, es transitivo en vértices con grado El grafo bipartito de Kneser 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 pares correspondientes de vértices. ^[14] El grafo bipartito de Kneser $H$ $(5, 2)$ es el grafo de Desargues y el grafo bipartito de Kneser $H$ $($ $n$ $, 1)$ es un grafo de corona . ${\tbinom {n-k}{k}}.$

Referencias

Notas

^ Villanueva (1970).
^ Lovász (1978).
^ Bárá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).
^ por 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).

Obras citadas

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 circunferencia impar del gráfico de Kneser generalizado", European Journal of Combinatorics , 18 (6): 607–611, doi : 10.1006/eujc.1996.0122 , MR 1468332
Godsil, Christopher ; Meagher, Karen (2015), Teoremas de Erdős–Ko–Rado: enfoques algebraicos, Cambridge Studies in Advanced Mathematics, Cambridge University Press, pág. 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 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/126050 , 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, 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 grafos de Kneser son hamiltonianos", Actas del 55.º Simposio anual de la 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), Hamilton Cycle Heuristics in Hard Graphs, tesis doctoral, Universidad Estatal de Carolina del Norte , archivada desde el original el 17 de septiembre de 2006 , consultada el 1 de octubre de 2006
Simpson, JE (1991), "Gráficos bipartitos hamiltonianos", Actas de la vigésimo segunda conferencia del sudeste sobre combinatoria, teoría de grafos y computación (Baton Rouge, LA, 1991) , Congressus Numerantium, vol. 85, págs. 97-110, MR 1152123
Valencia-Pabon, Mario; Vera, Juan-Carlos (2005), "Sobre el diámetro de los grafos de Kneser", Discrete Mathematics , 305 (1–3): 383–385, doi : 10.1016/j.disc.2005.10.001 , MR 2186709
Watkins, Mark E. (1970), "Conectividad de grafos 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". MundoMatemático .
Weisstein, Eric W. "Gráfico impar". MathWorld .