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

Résumé technique : Graphes signés avec la plus petite valeur propre fixée à au moins −3 et leurs réseaux

Énoncé du problème
Cet article étudie les propriétés structurelles des graphes signés connexes $(G, \sigma)$ dont la plus petite valeur propre, $\lambda_{\min}(G, \sigma)$, est bornée inférieurement par une valeur proche de $-3$. Plus précisément, les auteurs traitent du comportement de ces graphes lorsqu'ils possèdent une valence minimale (degré) suffisamment grande. L'étude se concentre sur deux aspects principaux :

1. Déterminer si la plus petite valeur propre est forcée d'être au moins égale à $-3$ (plutôt que simplement supérieure à $-3 - \varepsilon$) sous des conditions de haute valence.
2. Caractériser le réseau intégral $\Lambda(G, \sigma)$ associé à ces graphes, en déterminant spécifiquement s'il s'implante dans une somme directe de réseaux standards $\mathbb{Z}^n$ et de copies du réseau racine $E_8$.
3. Analyser l'« extensibilité » de ces graphes : si un graphe signé avec $\lambda_{\min} \ge -3$ peut être un sous-graphe induit propre d'un graphe signé connexe plus grand possédant la même borne de valeur propre.

Méthodologie
Les auteurs emploient une combinaison de théorie spectrale des graphes et de théorie des réseaux, en utilisant les outils clés suivants :

• Association de réseaux : Pour un graphe signé ayant une valeur propre $\lambda$, la matrice $G_r(G, \sigma) = A(G, \sigma) - \lfloor \lambda \rfloor I$ est semi-définie positive. Le réseau $\Lambda(G, \sigma)$ est défini comme le réseau intégral généré par les colonnes d'une matrice $N$ telle que $G_r(G, \sigma) = N^T N$.
• Graphes signés de Hoffman : Les auteurs utilisent le cadre des graphes signés de Hoffman « minces » (slim) et « gras » (fat). Les sommets gras sont remplacés par des cliques positives pour construire des graphes plus grands. Ce cadre permet l'analyse des limites de valeurs propres à mesure que la taille des cliques augmente.
• Sous-graphes minimaux interdits : La stratégie de preuve repose sur l'identification d'un ensemble fini de « graphes signés de Hoffman gras minimaux interdits » pour le seuil $\lambda = -3$. En prouvant que cet ensemble est fini, les auteurs établissent que les graphes ayant une valence minimale suffisamment grande ne peuvent pas contenir ces structures interdites, imposant ainsi des limites spécifiques à la valeur propre.
• Réseaux unimodulaires sans racines : L'article construit des exemples de graphes signés non extensibles en utilisant des réseaux unimodulaires irréductibles générés par des vecteurs de norme au carré 3 (sans racines), tels que le réseau de Leech court et le réseau de Conway-Borcherds.

Contributions clés et résultats

1. Élimination de l'écart de valeur propre (Théorème 1.3) :
   L'article prouve qu'il existe un nombre réel positif $\varepsilon$ et un entier positif $\kappa_3$ tels que si un graphe signé connexe possède $\lambda_{\min} > -3 - \varepsilon$ et une valence minimale d'au moins $\kappa_3$, alors $\lambda_{\min} \ge -3$. Cela renforce les résultats précédents qui caractérisaient les graphes avec $\lambda_{\min} \in (-2, -1]$ et $(-1-\sqrt{2}, -1]$.

2. Structure du réseau (Théorème 1.3) :
   Sous les conditions susmentionnées, le réseau associé $\Lambda(G, \sigma)$ est prouvé être un sous-réseau d'une somme directe du réseau standard $\mathbb{Z}^n$ et de copies du réseau racine $E_8$. Cela généralise les découvertes antérieures où les réseaux pour $\lambda_{\min} \ge -2$ étaient restreints aux réseaux racines $A_n, D_n, E_6, E_7, E_8$.

3. Extensibilité des graphes (Théorème 1.7) :
   Les auteurs montrent que si un graphe signé connexe possède $\lambda_{\min} \ge -3$ et une valence minimale suffisamment grande, il est extensible. C'est-à-dire qu'il peut être implanté comme un sous-graphe induit propre dans une infinité de graphes signés connexes plus grands qui satisfont également $\lambda_{\min} \ge -3$. Cela implique que ces graphes ne sont pas maximaux dans le contexte de la préservation de la valeur propre.

4. Construction de graphes non extensibles :
   L'article construit des exemples spécifiques de graphes signés réguliers non extensibles avec $\lambda_{\min} = -3$. Ceux-ci sont dérivés de réseaux unimodulaires irréductibles générés par des vecteurs de norme au carré 3 sans racines (par exemple, le réseau de Leech court, le réseau de Leech impair et le réseau de Conway-Borcherds).

• Un exemple est fourni avec un ordre de 2300 et une valence de 891.
• Cette construction démontre que la constante $\kappa_4$ dans le Théorème 1.7 (le seuil d'extensibilité) doit être au moins de 892.

5. Finitude des structures interdites (Théorème 3.2) :
   Un résultat technique critique est la preuve que l'ensemble des graphes signés de Hoffman gras minimaux interdits pour $\lambda = -3$ est fini. Cette finitude est essentielle pour établir l'existence du seuil de valence $\kappa_3$.

Signification et affirmations
L'article se positionne comme un renforcement substantiel des caractérisations antérieures des graphes signés avec des plus petites valeurs propres fixes.

• Motivation : Le travail est motivé par la classification des graphes signés avec $\lambda_{\min} \ge -2$ (qui correspondent aux réseaux racines) et par le problème plus large de déterminer le nombre maximal de droites biangulaires dans l'espace euclidien avec des angles spécifiques.
• Classification : Les auteurs suggèrent que, bien qu'il existe une infinité de graphes extensibles avec $\lambda_{\min} \ge -3$, l'existence de graphes non extensibles est probablement finie (ou du moins restreinte à des constructions de réseaux spécifiques). Ils posent le Problème 1.9 : « Existe-t-il une infinité de classes de commutation de graphes signés non extensibles avec la plus petite valeur propre d'au moins $-3$ ? » Sur la base de leurs résultats, ils s'attendent à ce que la réponse soit négative.
• Limites : L'article ne prétend pas classer pleinement tous les graphes signés non extensibles avec $\lambda_{\min} = -3$, mais fournit un cadre pour comprendre leurs propriétés de réseau et pour construire des exemples spécifiques. Il souligne que la constante $\kappa_4$ requise pour le théorème d'extensibilité est non triviale (au moins 892), indiquant que les petits graphes peuvent se comporter différemment de ceux ayant une haute valence.

En résumé, l'article établit qu'une haute valence force les graphes signés ayant des valeurs propres proches de $-3$ à se conformer à une structure de réseau spécifique ($\mathbb{Z}^n \oplus E_8^k$) et à devenir extensibles, tout en identifiant les constructions dérivées de réseaux comme les candidats probables pour les graphes signés non extensibles et maximaux dans ce régime.