Gráfico fuertemente regular

Concepto en teoría de grafos

El gráfico de Paley de orden 13, un gráfico fuertemente regular con parámetros (13,6,2,3) .

En teoría de grafos , un gráfico fuertemente regular ( SRG ) es un gráfico regular G = ( V , E ) con v vértices y grado k tal que para algunos enteros dados ${\displaystyle \lambda ,\mu \geq 0}$

• cada dos vértices adyacentes tienen λ vecinos comunes, y
• cada dos vértices no adyacentes tienen μ vecinos comunes.

Un gráfico tan fuertemente regular se denota por srg( v , k , λ, μ) ; sus "parámetros" son los números en ( v , k , λ, μ). Su gráfico de complemento también es fuertemente regular: es un srg( v , v − k − 1, v − 2 − 2 k + μ, v − 2 k + λ) .

Un gráfico fuertemente regular es un gráfico de distancia regular con diámetro 2 siempre que μ sea distinto de cero. Es un gráfico localmente lineal siempre que λ = 1 .

Etimología

Un gráfico fuertemente regular se denota como srg( v , k , λ, μ) en la literatura. Por convención, los gráficos que satisfacen trivialmente la definición se excluyen de los estudios detallados y de las listas de gráficos fuertemente regulares. Estos incluyen la unión disjunta de uno o más grafos completos de igual tamaño , ^{[1] [2]} y sus complementos , los grafos multipartitos completos con conjuntos independientes de igual tamaño.

Andries Brouwer y Hendrik van Maldeghem (ver #Referencias) utilizan una definición alternativa pero totalmente equivalente de gráfico fuertemente regular basada en la teoría de grafos espectrales : un gráfico fuertemente regular es un gráfico regular finito que tiene exactamente tres valores propios, de los cuales solo uno es igual al grado k , de multiplicidad 1. Esto descarta automáticamente los gráficos completamente conectados (que tienen solo dos valores propios distintos, no tres) y los gráficos desconectados (para los cuales la multiplicidad del grado k es igual al número de componentes conectados diferentes, que por lo tanto excedería uno). Gran parte de la literatura, incluido Brouwer, se refiere al valor propio más grande como r (con multiplicidad f ) y al más pequeño como s (con multiplicidad g ).

Historia

RC Bose introdujo los gráficos fuertemente regulares en 1963. ^[3] Se basaron en trabajos anteriores de la década de 1950 en el entonces nuevo campo de la teoría de gráficos espectrales .

Ejemplos

• El ciclo de longitud 5 es un srg(5, 2, 0, 1).
• La gráfica de Petersen es un srg(10, 3, 0, 1).
• La gráfica de Clebsch es un srg(16, 5, 0, 2).
• El gráfico de Shrikhande es un srg(16, 6, 2, 2) que no es un gráfico transitivo de distancia .
• La gráfica de torre cuadrada n  ×  n , es decir, la gráfica lineal de una gráfica bipartita completa equilibrada K _{n , n} , es un srg( n ² , 2 n  − 2, n  − 2, 2). Los parámetros para n = 4 coinciden con los del gráfico de Shrikhande, pero los dos gráficos no son isomórficos.
• La gráfica lineal de una gráfica completa K _n es una . ${\textstyle \operatorname {srg} \left({\binom {n}{2}},2(n-2),n-2,4\right)}$
• Las gráficas de Chang son srg(28, 12, 6, 4), iguales que la gráfica lineal de K ₈ , pero estas cuatro gráficas no son isomorfas.
• Cada cuadrilátero generalizado de orden (s, t) da un srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1) como su gráfico lineal . Por ejemplo, GQ(2, 4) da srg(27, 10, 1, 5) como gráfico lineal.
• El gráfico de Schläfli es un srg(27, 16, 10, 8). ^[4]
• La gráfica de Hoffman-Singleton es un srg(50, 7, 0, 1).
• La gráfica de Sims-Gewirtz es (56, 10, 0, 2).
• El gráfico M22, también conocido como gráfico de Mesner, es un srg(77, 16, 0, 4).
• El gráfico de Brouwer-Haemers es un srg(81, 20, 1, 6).
• El gráfico de Higman-Sims es un srg(100, 22, 0, 6).
• El gráfico local de McLaughlin es un srg(162, 56, 10, 24).
• La gráfica de Cameron es un srg(231, 30, 9, 3).
• El gráfico de Berlekamp-van Lint-Seidel es un srg(243, 22, 1, 2).
• La gráfica de McLaughlin es un srg(275, 112, 30, 56).
• La gráfica de Paley de orden q es un srg( q , ( q  − 1)/2, ( q  − 5)/4, ( q  − 1)/4). El gráfico de Paley más pequeño, con q = 5 , es el de 5 ciclos (arriba).
• Los gráficos transitivos de arco autocomplementarios son fuertemente regulares.

Un grafo fuertemente regular se llama primitivo si tanto el grafo como su complemento son conexos. Todos los gráficos anteriores son primitivos, de lo contrario μ = 0 o λ = k .

El problema de 99 gráficos de Conway requiere la construcción de un srg(99, 14, 1, 2). Se desconoce si existe un gráfico con estos parámetros, y John Horton Conway ofreció un premio de 1000 dólares por la solución a este problema. ^[5]

Gráficos sin triángulos

Las gráficas fuertemente regulares con λ = 0 no tienen triángulos . Aparte de los gráficos completos en menos de 3 vértices y todos los gráficos bipartitos completos, los siete enumerados anteriormente (pentágono, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22 y Higman-Sims) son los únicos conocidos.

gráficos geodésicos

Todo gráfico fuertemente regular es un gráfico geodésico , un gráfico en el que cada dos vértices tiene un camino más corto único y no ponderado . ^[6] Los únicos gráficos fuertemente regulares conocidos son aquellos en los que es 0, por lo tanto, también libres de triángulos. Estos se denominan gráficos de Moore y se exploran a continuación con más detalle. Aún no se han descartado otras combinaciones de parámetros como (400, 21, 2, 1). A pesar de las investigaciones en curso sobre las propiedades que tendría un gráfico fuertemente regular, ^{[7] [8]} no se sabe si existen más o incluso si su número es finito. ^[6] Sólo se conoce el resultado elemental, que no puede ser 1 para tal gráfico. ${\displaystyle \mu =1}$ ${\displaystyle \mu =1}$ ${\displaystyle \lambda }$ ${\displaystyle \mu =1}$ ${\displaystyle \lambda }$

Propiedades algebraicas de gráficos fuertemente regulares.

Relación básica entre parámetros.

Los cuatro parámetros en un srg( v , k , λ, μ) no son independientes. Deben obedecer a la siguiente relación:

${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$

La relación anterior se deriva mediante un argumento de conteo de la siguiente manera:

1. Imagine que los vértices del gráfico se encuentran en tres niveles. Elija cualquier vértice como raíz, en el Nivel 0. Entonces sus k vecinos se encuentran en el Nivel 1 y todos los demás vértices se encuentran en el Nivel 2.
2. Los vértices en el Nivel 1 están conectados directamente a la raíz, por lo tanto, deben tener λ otros vecinos en común con la raíz, y estos vecinos comunes también deben estar en el Nivel 1. Dado que cada vértice tiene grado k , quedan aristas para cada Nivel 1. nodo para conectarse a los vértices en el Nivel 2. Por lo tanto, hay aristas entre el Nivel 1 y el Nivel 2. ${\displaystyle k-\lambda -1}$ ${\displaystyle k(k-\lambda -1)}$
3. Los vértices en el Nivel 2 no están conectados directamente a la raíz, por lo tanto deben tener μ vecinos comunes con la raíz, y todos estos vecinos comunes deben estar en el Nivel 1. Hay vértices en el Nivel 2, y cada uno está conectado a μ vértices en el Nivel 1. Por lo tanto, el número de aristas entre el Nivel 1 y el Nivel 2 es . ${\displaystyle (v-k-1)}$ ${\displaystyle (v-k-1)\mu }$
4. Al equiparar las dos expresiones para los bordes entre el Nivel 1 y el Nivel 2, se obtiene la relación.

Ecuaciones matriciales de adyacencia

Sea I la matriz identidad y J la matriz de unos , ambas matrices de orden v . La matriz de adyacencia A de un gráfico fuertemente regular satisface dos ecuaciones.

Primero:

${\displaystyle AJ=JA=kJ,}$

que es una reformulación del requisito de regularidad. Esto muestra que k es un valor propio de la matriz de adyacencia con el vector propio de todos unos.

Segundo:

${\displaystyle A^{2}=kI+\lambda {A}+\mu (J-I-A)}$

que expresa una fuerte regularidad. El ij -ésimo elemento del lado izquierdo da el número de caminos de dos pasos de i a j . El primer término del lado derecho da el número de caminos de dos pasos desde i de regreso a i , es decir, k bordes hacia afuera y hacia adentro. El segundo término da el número de caminos de dos pasos cuando i y j están directamente conectados. El tercer término da el valor correspondiente cuando i y j no están conectados. Dado que los tres casos son mutuamente excluyentes y colectivamente exhaustivos , se sigue la igualdad aditiva simple.

Por el contrario, un gráfico cuya matriz de adyacencia satisface las dos condiciones anteriores y que no es un gráfico completo o nulo es un gráfico fuertemente regular. ^[9]

Valores propios y espectro gráfico.

Dado que la matriz de adyacencia A es simétrica, se deduce que sus vectores propios son ortogonales . Ya observamos un vector propio arriba que está hecho de todos unos, correspondiente al valor propio k . Por lo tanto, todos los otros vectores propios x deben satisfacer donde J es la matriz de todos unos como antes. Tome la ecuación previamente establecida: ${\displaystyle Jx=0}$

${\displaystyle A^{2}=kI+\lambda {A}+\mu (J-I-A)}$

y multiplica la ecuación anterior por el vector propio x :

${\displaystyle A^{2}x=kIx+\lambda {A}x+\mu (J-I-A)x}$

Llame al valor propio correspondiente p (que no debe confundirse con el parámetro del gráfico) y sustitúyalo , y : ${\displaystyle \lambda }$ ${\displaystyle Ax=px}$ ${\displaystyle Jx=0}$ ${\displaystyle Ix=x}$

${\displaystyle p^{2}x=kx+\lambda px-\mu x-\mu px}$

Elimina x y reordena para obtener una cuadrática:

${\displaystyle p^{2}+(\mu -\lambda )p-(k-\mu )=0}$

Esto da los dos valores propios adicionales . Por tanto, existen exactamente tres valores propios para una matriz fuertemente regular. ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )\pm {\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]}$

Por el contrario, un gráfico regular conectado con sólo tres valores propios es fuertemente regular. ^[10]

Siguiendo la terminología de gran parte de la literatura sobre grafos fuertemente regulares, el valor propio más grande se llama r con multiplicidad f y el más pequeño se llama s con multiplicidad g .

Dado que la suma de todos los valores propios es la traza de la matriz de adyacencia , que en este caso es cero, se pueden calcular las respectivas multiplicidades f y g :

• El valor propio k tiene multiplicidad 1.
• El valor propio tiene multiplicidad . ${\displaystyle r={\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]}$ ${\displaystyle f={\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$
• El valor propio tiene multiplicidad . ${\displaystyle s={\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]}$ ${\displaystyle g={\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$

Como las multiplicidades deben ser números enteros, sus expresiones proporcionan restricciones adicionales sobre los valores de v , k , μ y λ .

Gráficos fuertemente regulares para los cuales tienen valores propios enteros con multiplicidades desiguales. ${\displaystyle 2k+(v-1)(\lambda -\mu )\neq 0}$

Gráficos muy regulares, que se denominan gráficos de conferencia debido a su conexión con matrices de conferencia simétricas . Sus parámetros se reducen a ${\displaystyle 2k+(v-1)(\lambda -\mu )=0}$

${\displaystyle \operatorname {srg} \left(v,{\frac {1}{2}}(v-1),{\frac {1}{4}}(v-5),{\frac {1}{4}}(v-1)\right).}$

Sus valores propios son y , cuyas multiplicidades son iguales a . Además, en este caso, v debe ser igual a la suma de dos cuadrados, relacionado con el teorema de Bruck-Ryser-Chowla . ${\displaystyle r={\frac {-1+{\sqrt {v}}}{2}}}$ ${\displaystyle s={\frac {-1-{\sqrt {v}}}{2}}}$ ${\displaystyle {\frac {v-1}{2}}}$

Otras propiedades de los valores propios y sus multiplicidades son:

• ${\displaystyle (A-rI)\times (A-sI)=\mu .J}$, por lo tanto ${\displaystyle (k-r).(k-s)=\mu v}$
• ${\displaystyle \lambda -\mu =r+s}$
• ${\displaystyle k-\mu =-r\times s}$
• ${\displaystyle k\geq r}$
• Dado un srg( v , k , λ, μ) con valores propios r y s , su complemento srg( v , v − k − 1, v − 2 − 2 k + μ, v − 2 k + λ) tiene valores propios -1 -s y -1-r .
• Las ecuaciones alternativas para las multiplicidades son y ${\displaystyle f={\frac {(s+1)k(k-s)}{\mu (s-r)}}}$ ${\displaystyle g={\frac {(r+1)k(k-r)}{\mu (r-s)}}}$
• La condición del cociente de marcos: . Como corolario, si y sólo si en algún orden. ${\displaystyle vk(v-k-1)=fg(r-s)^{2}}$ ${\displaystyle v=(r-s)^{2}}$ ${\displaystyle {f,g}={k,v-k-1}}$
• Condiciones de Kerin: y ${\displaystyle (v-k-1)^{2}(k^{2}+r^{3})\geq (r+1)^{3}k^{2}}$ ${\displaystyle (v-k-1)^{2}(k^{2}+s^{3})\geq (s+1)^{3}k^{2}}$
• Límite absoluto: y . ${\displaystyle v\leq {\frac {f(f+3)}{2}}}$ ${\displaystyle v\leq {\frac {g(g+3)}{2}}}$
• Atado con garra: si , entonces o . ${\displaystyle r+1>{\frac {s(s+1)(\mu +1)}{2}}}$ ${\displaystyle \mu =s^{2}}$ ${\displaystyle \mu =s(s+1)}$

Si se violan las condiciones anteriores para cualquier conjunto de parámetros, entonces no existe un gráfico fuertemente regular para esos parámetros. Brouwer ha compilado aquí dichas listas de existencia o inexistencia con los motivos de su inexistencia, si los hubiera.

El teorema de Hoffman-Singleton

Como se señaló anteriormente, las multiplicidades de los valores propios están dadas por

${\displaystyle M_{\pm }={\frac {1}{2}}\left[(v-1)\pm {\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$

que deben ser números enteros.

En 1960, Alan Hoffman y Robert Singleton examinaron aquellas expresiones cuando se aplicaron a gráficas de Moore que tienen λ = 0 y μ = 1. Dichas gráficas están libres de triángulos (de lo contrario, λ excedería cero) y cuadriláteros (de lo contrario, μ excedería 1), por lo tanto tienen una circunferencia (longitud de ciclo más pequeña) de 5. Sustituyendo los valores de λ y μ en la ecuación , se puede ver que , y las multiplicidades de valores propios se reducen a ${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$ ${\displaystyle v=k^{2}+1}$

${\displaystyle M_{\pm }={\frac {1}{2}}\left[k^{2}\pm {\frac {2k-k^{2}}{\sqrt {4k-3}}}\right]}$

Para que las multiplicidades sean enteras, la cantidad debe ser racional, por lo tanto, o el numerador es cero o el denominador es un número entero. ${\displaystyle {\frac {2k-k^{2}}{\sqrt {4k-3}}}}$ ${\displaystyle 2k-k^{2}}$ ${\displaystyle {\sqrt {4k-3}}}$

Si el numerador es cero, las posibilidades son: ${\displaystyle 2k-k^{2}}$

• k = 0 y v = 1 produce un gráfico trivial con un vértice y sin aristas, y
• k = 2 y v = 5 produce el gráfico de ciclo de 5 vértices , generalmente dibujado como un pentágono regular . ${\displaystyle C_{5}}$

Si el denominador es un número entero t , entonces es un cuadrado perfecto , entonces . Sustituyendo: ${\displaystyle {\sqrt {4k-3}}}$ ${\displaystyle 4k-3}$ ${\displaystyle t^{2}}$ ${\displaystyle k={\frac {t^{2}+3}{4}}}$

${\displaystyle {\begin{aligned}M_{\pm }&={\frac {1}{2}}\left[\left({\frac {t^{2}+3}{4}}\right)^{2}\pm {\frac {{\frac {t^{2}+3}{2}}-\left({\frac {t^{2}+3}{4}}\right)^{2}}{t}}\right]\\32M_{\pm }&=(t^{2}+3)^{2}\pm {\frac {8(t^{2}+3)-(t^{2}+3)^{2}}{t}}\\&=t^{4}+6t^{2}+9\pm {\frac {-t^{4}+2t^{2}+15}{t}}\\&=t^{4}+6t^{2}+9\pm \left(-t^{3}+2t+{\frac {15}{t}}\right)\end{aligned}}}$

Dado que ambos lados son números enteros, debe ser un número entero, por lo tanto t es factor de 15, es decir , por lo tanto . Sucesivamente: ${\displaystyle {\frac {15}{t}}}$ ${\displaystyle t\in \{\pm 1,\pm 3,\pm 5,\pm 15\}}$ ${\displaystyle k\in \{1,3,7,57\}}$

• k = 1 y v = 2 produce una gráfica trivial de dos vértices unidos por una arista,
• k = 3 y v = 10 produce el gráfico de Petersen ,
• k = 7 y v = 50 produce el gráfico de Hoffman-Singleton , descubierto por Hoffman y Singleton en el curso de este análisis, y
• k = 57 y v = 3250 predice un gráfico famoso que no se ha descubierto desde 1960 ni se ha refutado su existencia. ^[11]

El teorema de Hoffman-Singleton establece que no existen gráficos de Moore de circunferencia 5 fuertemente regulares excepto los enumerados anteriormente.

Ver también

• Geometría parcial
• Matriz de adyacencia de Seidel
• dos gráficos

Notas

1. Brouwer, Andries E; Haemers, Willem H. Espectros de gráficos. pag. 101 Archivado el 16 de marzo de 2012 en la Wayback Machine.
2. Diossil, Chris; Royle, Gordon. Teoría de grafos algebraica . Springer-Verlag Nueva York, 2001, pág. 218.
3. https://projecteuclid.org/euclid.pjm/1103035734, RC Bose, Gráficos muy regulares, geometrías parciales y diseños parcialmente equilibrados, Pacific J. Math 13 (1963) 389–419. (pág.122)
4. Weisstein, Eric W. , "Gráfico de Schläfli", MathWorld
5. Conway, John H. , Cinco problemas de $ 1000 (actualización de 2017) (PDF) , Enciclopedia en línea de secuencias enteras , consultado el 12 de febrero de 2019
6. Blokhuis, A .; Brouwer, AE (1988), "Gráficos geodésicos de diámetro dos", Geometriae Dedicata , 25 (1–3): 527–533, doi :10.1007/BF00191941, MR  0925851, S2CID  189890651
7. Alemán, J.; Fisher, PH (2001), "Sobre gráficos fuertemente regulares con ", European Journal of Combinatorics , 22 (3): 303–306, doi : 10.1006/eujc.2000.0472 , MR  1822718 ${\displaystyle \mu =1}$
8. Belousov, IN; Makhnev, AA (2006), "Sobre gráficos fuertemente regulares con y sus automorfismos", Doklady Akademii Nauk , 410 (2): 151–155, SEÑOR  2455371 ${\displaystyle \mu =1}$
9. Cameron, PJ; van Lint, JH (1991), Diseños, gráficos, códigos y sus vínculos, Textos estudiantiles de la London Mathematical Society 22, Cambridge University Press, pág. 37, ISBN 978-0-521-42385-4
10. Diossil, Chris; Royle, Gordon. Teoría de grafos algebraica . Springer-Verlag, Nueva York, 2001, Lema 10.2.1.
11. Dalfó, C. (2019), "Un estudio sobre el gráfico de Moore que falta", Álgebra lineal y sus aplicaciones , 569 : 1–14, doi :10.1016/j.laa.2018.12.035, hdl : 2117/127212 , SEÑOR  3901732, S2CID  126689579

Referencias

• Andries Brouwer y Hendrik van Maldeghem (2022), Gráficos fuertemente regulares . Cambridge: Prensa de la Universidad de Cambridge. ISBN 1316512037 . ISBN 978-1316512036  
• AE Brouwer, AM Cohen y A. Neumaier (1989), Gráficos regulares de distancia . Berlín, Nueva York: Springer-Verlag. ISBN 3-540-50619-5 , ISBN 0-387-50619-5  
• Chris Godsil y Gordon Royle (2004), Teoría de grafos algebraicos . Nueva York: Springer-Verlag. ISBN 0-387-95241-1 

enlaces externos

• Eric W. Weisstein , artículo de Mathworld con numerosos ejemplos.
• Gordon Royle , Lista de familias y gráficos más grandes.
• Andries E. Brouwer , Parámetros de gráficos fuertemente regulares.
• Brendan McKay , algunas colecciones de gráficos.
• Ted Spence, Gráficos fuertemente regulares en un máximo de 64 vértices.