Gráfico de Johnson

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${\displaystyle J(n,k)}$son los${\displaystyle k}$subconjuntos de elementos de un${\displaystyle n}$-conjunto de elementos; dos vértices son adyacentes cuando la intersección de los dos vértices (subconjuntos) contiene${\displaystyle (k-1)}$-elementos. ^{[ 1 ]} Tanto los grafos de Johnson como el esquema de Johnson, estrechamente relacionado , reciben su nombre de Selmer M. Johnson .

• Ambos${\displaystyle J(n,1)}$y${\displaystyle J(n,n-1)}$son el gráfico completo K _n .
• ${\displaystyle J(4,2)}$es el gráfico octaédrico . ^{[ 2 ]}
• ${\displaystyle J(5,2)}$es el complemento del gráfico de Petersen , ^{[ 1 ]} por lo tanto el gráfico de líneas de K ₅ . Más generalmente, para todo${\displaystyle n}$, el gráfico de Johnson${\displaystyle J(n,2)}$es la gráfica lineal de K _n y el complemento de la gráfica de Kneser${\displaystyle K(n,2).}$

• ${\displaystyle J(n,k)}$es isomorfo a${\displaystyle J(n,nk).}$
• A pesar de${\displaystyle 0\leq j\leq \operatorname {diam} (J(n,k))}$, cualquier par de vértices a distancia${\displaystyle j}$compartir${\displaystyle kj}$elementos en común.
• ${\displaystyle J(n,k)}$es hamiltoniano-conexo , lo que significa que cada par de vértices forma los extremos de un camino hamiltoniano en el grafo. En particular, esto significa que tiene un ciclo hamiltoniano . ^{[ 3 ]}
• También se sabe que el gráfico de Johnson${\displaystyle J(n,k)}$es${\displaystyle k(nk)}$-conectado por vértices. ^{[ 4 ]}
• ${\displaystyle J(n,k)}$forma el grafo de vértices y aristas de un politopo de ( n  −  1) dimensiones , llamado hipersímplex . ^{[ 5 ]}
• Cualquier camarilla máxima es de la forma${\displaystyle \{S\cup \{x\}\mid x\in \{1,\dots ,n\}\setminus S\}}$por un${\displaystyle (k-1)}$subconjunto de elementos${\displaystyle S}$y${\displaystyle k<n-1}$o de la forma${\displaystyle \{S\setminus \{x\}\mid x\in S\}}$por un${\displaystyle (k+1)}$-conjunto de elementos${\displaystyle S}$para${\displaystyle k>1}$o de la forma${\displaystyle \{\{1\},\{2\}\}}$en el caso límite${\displaystyle (n,k)=(2,1)}$. ^{[ 6 ]}
• El número de camarilla de${\displaystyle J(n,k)}$viene dada por una expresión en términos de sus autovalores mínimo y máximo :${\displaystyle \omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }}$, o, según la descripción explícita anterior de las camarillas máximas,${\displaystyle \omega (J(n,k))=\max\{k+1,N-k+1\}.}$
• La camarilla cubre el número de${\displaystyle J(n,k)}$Satisface${\displaystyle \theta (J(n,1))=1}$para${\displaystyle n>1}$,${\displaystyle \theta (J(n,2))=n-2}$para${\displaystyle n>2}$y${\displaystyle \theta (J(n,3))=\lfloor (n-1)^{2}/4\rfloor }$para${\displaystyle n>5}$pero no se conoce en general. ^{[ 7 ]}
• El número cromático de${\displaystyle J(n,k)}$es como máximo${\displaystyle n,\chi (J(n,k))\leq n.}$^{[ 8 ]}
• 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 torres . Más precisamente, en el grafo de Johnson${\displaystyle J(n,k)}$, cada vecindario es un${\displaystyle k\times (n-k)}$Gráfico de la torre. ^{[ 9 ]}

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

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

${\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${\displaystyle J(n,k)}$es${\displaystyle J(8,2)}$, su matriz de intersección no se comparte con ningún otro grafo distancia-regular distinto; la matriz de intersección de${\displaystyle J(8,2)}$se comparte con otros tres grafos regulares de distancia que no son grafos de Johnson. ^{[ 1 ]}

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

${\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}}}.}$

dónde${\displaystyle A_{n,k}(j)=(k-j)(n-k-j)-j.}$^{[ 10 ]}

• Los autovectores de${\displaystyle J(n,k)}$tener una descripción explícita. ^{[ 11 ]}

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

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

Las propiedades de expansión de vértices de los grafos de Johnson, así como la estructura de los conjuntos extremos de vértices correspondientes de un tamaño dado, no se comprenden completamente. Sin embargo, recientemente se obtuvo una cota inferior asintóticamente ajustada para la expansión de grandes conjuntos de vértices. ^{[ 14 ]}

En general, determinar el número cromático de un grafo de Johnson es un problema abierto . ^{[ 15 ] [ 16 ]}

• Gráfico de Grassmann

• Weisstein, Eric W. , "Grafo de Johnson" , MathWorld
• Brouwer, Andries E. , gráficos de Johnson