Gráfico de Johnson

Clase de grafos no dirigidos definidos a partir de sistemas de conjuntos

En matemáticas , los grafos de Johnson son una clase especial de grafos no dirigidos definidos a partir de sistemas de conjuntos. Los vértices del grafo de Johnson son los subconjuntos de elementos de un conjunto de elementos; dos vértices son adyacentes cuando la intersección de los dos vértices (subconjuntos) contiene elementos. ^{[1] Tanto los grafos de Johnson como el} esquema de Johnson, estrechamente relacionado, reciben su nombre de Selmer M. Johnson . ${\displaystyle J(n,k)}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle (k-1)}$

Casos especiales

• Tanto y son el gráfico completo K _n . ${\displaystyle J(n,1)}$ ${\displaystyle J(n,n-1)}$
• ${\displaystyle J(4,2)}$es el gráfico octaédrico .
• ${\displaystyle J(5,2)}$es el complemento del gráfico de Petersen , ^[1] de ahí el gráfico lineal de K ₅ . De manera más general, para todo , el gráfico de Johnson es el gráfico lineal de K _n y el complemento del gráfico de Kneser ${\displaystyle n}$ ${\displaystyle J(n,2)}$ ${\displaystyle K(n,2).}$

Propiedades de la teoría de grafos

• ${\displaystyle J(n,k)}$es isomorfo a ${\displaystyle J(n,n-k).}$
• Para todos , cualquier par de vértices a distancia comparten elementos en común. ${\displaystyle 0\leq j\leq \operatorname {diam} (J(n,k))}$ ${\displaystyle j}$ ${\displaystyle k-j}$
• ${\displaystyle J(n,k)}$es hamiltoniano-conexo , lo que significa que cada par de vértices forma los puntos finales de un camino hamiltoniano en el grafo. En particular, esto significa que tiene un ciclo hamiltoniano . ^[2]
• También se sabe que el gráfico de Johnson está conexo por vértice. ^[3] ${\displaystyle J(n,k)}$ ${\displaystyle k(n-k)}$
• ${\displaystyle J(n,k)}$forma el gráfico de vértices y aristas de un politopo de dimensión ( n  − 1) , llamado hipersímplex . ^[4]
• El número de camarilla de se da mediante una expresión en términos de sus valores propios mínimo y máximo : ${\displaystyle J(n,k)}$ ${\displaystyle \omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }.}$
• El número cromático de es como máximo ^[5] ${\displaystyle J(n,k)}$ ${\displaystyle n,\chi (J(n,k))\leq n.}$
• Cada grafo de Johnson es localmente una cuadrícula , lo que significa que el subgrafo inducido de los vecinos de cualquier vértice es un grafo de torre . Más precisamente, en el grafo de Johnson , cada vecindario es un grafo de torre. ^[6] ${\displaystyle J(n,k)}$ ${\displaystyle k\times (n-k)}$

Grupo de automorfismos

Existe un subgrupo transitivo de distancia de isomorfo a . De hecho, , excepto que cuando , . ^[7] ${\displaystyle \operatorname {Aut} (J(n,k))}$ ${\displaystyle \operatorname {Sym} (n)}$ ${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)}$ ${\displaystyle n=2k\geq 4}$ ${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)\times C_{2}}$

Matriz de intersección

Como consecuencia de ser transitivo en cuanto a la distancia, también es regular en cuanto a la distancia . Si denotamos su diámetro , la matriz de intersección de está dada por ${\displaystyle J(n,k)}$ ${\displaystyle d}$ ${\displaystyle J(n,k)}$

${\displaystyle \left\{b_{0},\ldots ,b_{d-1},c_{1},\ldots c_{d}\right\}}$

dónde:

${\displaystyle {\begin{aligned}b_{j}&=(k-j)(n-k-j)&&0\leq j<d\\c_{j}&=j^{2}&&0<j\leq d\end{aligned}}}$

Resulta que a menos que sea , su matriz de intersección no se comparte con ningún otro gráfico regular-de-distancia distinto; la matriz de intersección de se comparte con otros tres gráficos regulares-de-distancia que no son gráficos de Johnson. ^[1] ${\displaystyle J(n,k)}$ ${\displaystyle J(8,2)}$ ${\displaystyle J(8,2)}$

Valores propios y vectores propios

• El polinomio característico de está dado por ${\displaystyle J(n,k)}$

${\displaystyle \phi (x):=\prod _{j=0}^{\operatorname {diam} (J(n,k))}\left(x-A_{n,k}(j)\right)^{{\binom {n}{j}}-{\binom {n}{j-1}}}.}$

donde ^[7] ${\displaystyle A_{n,k}(j)=(k-j)(n-k-j)-j.}$

• Los vectores propios de tienen una descripción explícita. ^[8] ${\displaystyle J(n,k)}$

Plan Johnson

El gráfico de Johnson está estrechamente relacionado con el esquema de Johnson , un esquema de asociación en el que cada par de conjuntos de k elementos está asociado con un número, la mitad del tamaño de la diferencia simétrica de los dos conjuntos. ^[9] El gráfico de Johnson tiene una arista para cada par de conjuntos a la distancia uno en el esquema de asociación, y las distancias en el esquema de asociación son exactamente las distancias de ruta más cortas en el gráfico de Johnson. ^[10] ${\displaystyle J(n,k)}$

El esquema de Johnson también está relacionado con otra familia de grafos transitivos de distancia, los grafos impares , cuyos vértices son subconjuntos de elementos de un conjunto de elementos y cuyos bordes corresponden a pares disjuntos de subconjuntos. ^[9] ${\displaystyle k}$ ${\displaystyle (2k+1)}$

Problemas abiertos

Las propiedades de expansión de vértices de los grafos de Johnson, así como la estructura de los conjuntos extremos correspondientes de vértices de un tamaño determinado, no se comprenden por completo. Sin embargo, recientemente se obtuvo un límite inferior asintóticamente ajustado para la expansión de grandes conjuntos de vértices. ^[11]

En general, determinar el número cromático de un gráfico de Johnson es un problema abierto . ^[12]

Véase también

• Gráfico de Grassmann

Referencias

1. Holton, DA; Sheehan, J. (1993), "Los gráficos de Johnson y los gráficos pares", El gráfico de Petersen , Serie de conferencias de la Sociedad Matemática Australiana, vol. 7, Cambridge: Cambridge University Press, pág. 300, doi :10.1017/CBO9780511662058, ISBN 0-521-43594-3, Sr.  1232658.
2. Alspach, Brian (2013), "Los grafos de Johnson están conectados a Hamilton", Ars Mathematica Contemporanea , 6 (1): 21–23, doi : 10.26493/1855-3974.291.574.
3. Newman, Ilan; Rabinovich, Yuri (2015), Sobre la conectividad de los gráficos de facetas de complejos simpliciales , arXiv : 1502.02232 , Bibcode :2015arXiv150202232N.
4. Rispoli, Fred J. (2008), El gráfico del hipersímplex , arXiv : 0811.2981 , Bibcode :2008arXiv0811.2981R.
5. "Johnson", www.win.tue.nl , consultado el 26 de julio de 2017
6. Cohen, Arjeh M. (1990), "Reconocimiento local de gráficos, edificios y geometrías relacionadas" (PDF) , en Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (eds.), Geometrías finitas, edificios y temas relacionados: artículos de la Conferencia sobre edificios y geometrías relacionadas celebrada en Pingree Park, Colorado, del 17 al 23 de julio de 1988 , Oxford Science Publications, Oxford University Press, págs. 85-94, MR  1072157; véanse en particular las páginas 89-90
7. Brouwer, Andries E. (1989), Gráficos regulares a distancia , Cohen, Arjeh M., Neumaier, Arnold., Berlín, Heidelberg: Springer Berlin Heidelberg, ISBN 9783642743436, OCLC  851840609
8. Filmus, Yuval (2014), "Una base ortogonal para funciones sobre una porción del hipercubo booleano", The Electronic Journal of Combinatorics , 23 , arXiv : 1406.0142 , Bibcode :2014arXiv1406.0142F, doi :10.37236/4567, S2CID  7416206.
9. Cameron, Peter J. (1999), Grupos de permutación, Textos para estudiantes de la London Mathematical Society, vol. 45, Cambridge University Press, pág. 95, ISBN 9780521653787.
10. La identificación explícita de los grafos con esquemas de asociación, de esta manera, se puede ver en Bose, RC (1963), "Strongly regular graphs, partial geometries and partial balanced designs", Pacific Journal of Mathematics , 13 (2): 389–419, doi : 10.2140/pjm.1963.13.389 , MR  0157909.
11. Christofides, Demetres; Ellis, David; Keevash, Peter (2013), "Una desigualdad isoperimétrica de vértice aproximada para conjuntos $r$", The Electronic Journal of Combinatorics , 4 (20).
12. Godsil, CD; Meagher, Karen (2016), Teoremas de Erdős-Ko-Rado: enfoques algebraicos , Cambridge, Reino Unido, ISBN 9781107128446, OCLC  935456305{{citation}}: CS1 maint: location missing publisher (link)

Enlaces externos

• Weisstein, Eric W. , "Gráfico de Johnson", MathWorld
• Brouwer, Andries E. , Gráficos de Johnson