Signed graphs with fixed smallest eigenvalue at least $-3$ and their lattices

Resumen Técnico: Grafos con signo con el menor autovalor fijo de al menos −3 y sus redes

Planteamiento del Problema
Este artículo investiga las propiedades estructurales de los grafos con signo conexos $(G, \sigma)$ cuyo menor autovalor, $\lambda_{\min}(G, \sigma)$, está acotado inferiormente por un valor cercano a $-3$. Específicamente, los autores abordan el comportamiento de tales grafos cuando poseen una valencia mínima (grado) suficientemente grande. El estudio se centra en dos aspectos primarios:

1. Determinar si el menor autovalor es forzado a ser al menos $-3$ (en lugar de solo mayor que $-3 - \varepsilon$) bajo condiciones de alta valencia.
2. Caracterizar la red integral $\Lambda(G, \sigma)$ asociada a estos grafos, específicamente determinando si se incrusta en una suma directa de redes estándar $\mathbb{Z}^n$ y copias de la red de raíces $E_8$.
3. Analizar la "extendibilidad" de estos grafos: si un grafo con signo con $\lambda_{\min} \ge -3$ puede ser un subgrafo inducido propio de un grafo con signo conexo más grande que posea el mismo límite de autovalor.

Metodología
Los autores emplean una combinación de teoría espectral de grafos y teoría de redes, utilizando las siguientes herramientas clave:

• Asociación de Redes: Para un grafo con signo con un menor autovalor $\lambda$, la matriz $G_r(G, \sigma) = A(G, \sigma) - \lfloor \lambda \rfloor I$ es semidefinida positiva. La red $\Lambda(G, \sigma)$ se define como la red integral generada por las columnas de una matriz $N$ tal que $G_r(G, \sigma) = N^T N$.
• Grafos con Signo de Hoffman: Los autores utilizan el marco de los grafos con signo de Hoffman, que consisten en vértices "delgados" (slim) y "gruesos" (fat). Los vértices gruesos son reemplazados por cliques positivos para construir grafos más grandes. Este marco permite el análisis de los límites de los autovalores a medida que el tamaño de los cliques crece.
• Subgrafos Prohibidos Mínimos: La estrategia de prueba se basa en la identificación de un conjunto finito de "grafos de Hoffman con signo gruesos mínimos prohibidos" para el umbral $\lambda = -3$. Al demostrar que este conjunto es finito, los autores establecen que los grafos con valencia mínima suficientemente grande no pueden contener estas estructuras prohibidas, forzando así al autovalor a satisfacer límites específicos.
• Redes Unimodulares sin Raíces: El artículo construye ejemplos de grafos con signo no extendibles utilizando redes unimodulares irreducibles generadas por vectores de norma al cuadrado 3 (sin raíces), tales como la red de Leech corta, la red de Conway-Borcherds, entre otras.

Contribuciones Clave y Resultados

1. Eliminación del Brecha de Autovalores (Teorema 1.3):
   El artículo demuestra que existen un número real positivo $\varepsilon$ y un entero positivo $\kappa_3$ tales que, si un grafo con signo conexo tiene $\lambda_{\min} > -3 - \varepsilon$ y una valencia mínima de al menos $\kappa_3$, entonces $\lambda_{\min} \ge -3$. Esto refuerza resultados previos que caracterizaron grafos con $\lambda_{\min} \in (-2, -1]$ y $(-1-\sqrt{2}, -1]$.

2. Estructura de la Red (Teorema 1.3):
   Bajo las condiciones mencionadas, se demuestra que la red asociada $\Lambda(G, \sigma)$ es un subgrafo de una suma directa de la red estándar $\mathbb{Z}^n$ y copias de la red de raíces $E_8$. Esto generaliza hallazgos anteriores donde las redes para $\lambda_{\min} \ge -2$ estaban restringidas a las redes de raíces $A_n, D_n, E_6, E_7, E_8$.

3. Extendibilidad de los Grafos (Teorema 1.7):
   Los autores muestran que si un grafo con signo conexo tiene $\lambda_{\min} \ge -3$ y una valencia mínima suficientemente grande, es extendible. Es decir, puede ser incrustado como un subgrafo inducido propio en infinitos grafos con signo conexos más grandes que también satisfacen $\lambda_{\min} \ge -3$. Esto implica que tales grafos no son maximales en el contexto de la preservación del autovalor.

4. Construcción de Grafos No Extendibles:
   El artículo construye ejemplos específicos de grafos regulares con signo no extendibles con $\lambda_{\min} = -3$. Estos se derivan de redes unimodulares irreducibles generadas por vectores de norma al cuadrado 3 sin raíces (por ejemplo, la red de Leech corta, la red de Leech impar y la red de Conway-Borcherds).

   • Se proporciona un ejemplo con orden 2300 y valencia 891.
   • Esta construcción demuestra que la constante $\kappa_4$ en el Teorema 1.7 (el umbral para la extendibilidad) debe ser al menos 892.

5. Finitud de las Estructuras Prohibidas (Teorema 3.2):
   Un resultado técnico crítico es la demostración de que el conjunto de grafos de Hoffman con signo gruesos mínimos prohibidos para $\lambda = -3$ es finito. Esta finitud es esencial para establecer la existencia del umbral de valencia $\kappa_3$.

Significancia y Reivindicaciones
El artículo se posiciona como un fortalecimiento sustancial de las caracterizaciones previas de grafos con signo con autovalores mínimos fijos.

• Motivación: El trabajo está motivado por la clasificación de grafos con signo con $\lambda_{\min} \ge -2$ (que corresponden a redes de raíces) y el problema más amplio de determinar el número máximo de líneas biangulares en el espacio euclidiano con ángulos específicos.
• Clasificación: Los autores sugieren que, si bien existen infinitos grafos extendibles con $\lambda_{\min} \ge -3$, la existencia de grafos no extendibles es probablemente finita (o al menos está restringida a construcciones de redes específicas). Plantean el Problema 1.9: "¿Existen infinitas clases de conmutación (switching classes) de grafos con signo no extendibles con el menor autovalor de al menos $-3$?". Basándose en sus resultados, esperan que la respuesta sea negativa.
• Limitaciones: El artículo no pretende clasificar completamente todos los grafos con signo no extendibles con $\lambda_{\min} = -3$, sino que proporciona un marco para comprender sus propiedades de red y construir ejemplos específicos. Destaca que la constante $\kappa_4$ requerida para el teorema de extendibilidad es no trivial (al menos 892), lo que indica que los grafos pequeños pueden comportarse de manera diferente a aquellos con valencia alta.

En resumen, el artículo establece que la alta valencia fuerza a los grafos con signo con autovalores cercanos a $-3$ a conformarse con una estructura de red específica ($\mathbb{Z}^n \oplus E_8^k$) y a volverse extendibles, identificando simultáneamente las construcciones derivadas de redes como los candidatos probables para los grafos con signo no extendibles y maximales en este régimen.