Gráfica de Kneser

Grafo cuyos vértices corresponden a combinaciones de un conjunto de n elementos

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

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

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 ₃ = K (5, 2) es el gráfico de Petersen (ver la 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 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. ${\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 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 igual al número de vecinos por vértice. ^[1] ${\displaystyle K(2k,k)}$ ${\displaystyle K(n,k)}$ ${\displaystyle {\tbinom {n-k}{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. ${\displaystyle K(n,k)}$ ${\displaystyle 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 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 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. ${\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 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]

${\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 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 ≥ 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 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 ≥ ck . Además, aunque el grafo 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 longitud variable. ^[11]

Diámetro

El diámetro de un grafo de Kneser conexo K ( n , k ) es ^[12] $${\displaystyle \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] $${\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}}$

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

Referencias

Notas

1. Villanueva (1970).
2. Lovász (1978).
3. Bárá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).

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, North Carolina State University , 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 .