gráfico de johnson

Clase de gráficos no dirigidos definidos a partir de sistemas de conjuntos.

Los gráficos de Johnson son una clase especial de gráficos no dirigidos definidos a partir de sistemas de conjuntos. Los vértices del gráfico 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 gráficos de Johnson como el} esquema de Johnson, estrechamente relacionado, llevan el nombre de Selmer M. Johnson . ${\displaystyle J(n,k)}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle (k-1)}$

Casos especiales

• Ambos 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 de la gráfica de Petersen , ^[1] de ahí la gráfica lineal de K ₅ . De manera más general, para todos , 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)}$está conexo a Hamilton , lo que significa que cada par de vértices forma los puntos finales de una ruta hamiltoniana en el gráfico. En particular esto significa que tiene un ciclo hamiltoniano. ^[2]
• También se sabe que el gráfico de Johnson está conectado por vértices. ^[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ímplejo . ^[4]
• el número de camarilla de está dado por una expresión en términos de sus valores propios mínimo y mayor: ${\displaystyle J(n,k)}$ ${\displaystyle \omega (J(n,k))=1-{\tfrac {\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 gráfico de Johnson es una cuadrícula local, lo que significa que el subgrafo inducido de los vecinos de cualquier vértice es un gráfico de torre . Más precisamente, en el gráfico de Johnson , cada vecindad es el gráfico de una torre. ^[6] ${\displaystyle J(n,k)}$ ${\displaystyle k\times (n-k)}$

Grupo de automorfismo

Hay 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 distancia, también es regular en distancia . Denotando 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 de distancia regular distinto; la matriz de intersección de se comparte con otros tres gráficos de distancia regular 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)}$

Esquema 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 camino 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 gráficos transitivos de distancia, los gráficos impares , cuyos vértices son subconjuntos de elementos de un conjunto de elementos y cuyas aristas corresponden a pares de subconjuntos disjuntos. ^[9] ${\displaystyle k}$ ${\displaystyle (2k+1)}$

Problemas abiertos

Las propiedades de expansión de vértices de los gráficos de Johnson, así como la estructura de los correspondientes conjuntos extremos de vértices de un tamaño dado, no se comprenden completamente. 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]

Ver 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 Australiana de Matemáticas, vol. 7, Cambridge: Cambridge University Press, pág. 300, doi :10.1017/CBO9780511662058, ISBN 0-521-43594-3, señor  1232658.
2. Alspach, Brian (2013), "Los gráficos de Johnson están conectados a Hamilton", Ars Mathematica Contemporanea , 6 (1): 21–23, doi : 10.26493/1855-3974.291.574.
3. Newman, Ilán; Rabinovich, Yuri (2015), Sobre la conectividad de los gráficos facetarios de complejos simpliciales , arXiv : 1502.02232 , Bibcode :2015arXiv150202232N.
4. Rispoli, Fred J. (2008), La gráfica del hipersimplex , 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, SEÑOR  1072157; véanse en particular las págs. 89 y 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 gráficos con esquemas de asociación, de esta manera, se puede ver en Bose, RC (1963), "Strongly regular graphs, parcial geometries and parcialmente balanceados", Pacific Journal of Mathematics , 13 (2): 389– 419, doi : 10.2140/pjm.1963.13.389 , SEÑOR  0157909.
11. Christofides, Demétres; Ellis, David; Keevash, Peter (2013), "Una desigualdad isoperimétrica de vértice aproximada para conjuntos de $r$", The Electronic Journal of Combinatorics , 4 (20).
12. Diossil, CD; Meagher, Karen (2016), Teoremas de Erdős-Ko-Rado: enfoques algebraicos , Cambridge, Reino Unido, ISBN 9781107128446, OCLC  935456305{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )

enlaces externos

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