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

Resumo Técnico: Grafos assinados com autovalor mínimo fixo pelo menos $-3$ e seus reticulados

Enunciado do Problema
Este artigo investiga as propriedades estruturais de grafos assinados conexos $(G, \sigma)$ cujo autovalor mínimo, $\lambda_{\min}(G, \sigma)$, é limitado inferiormente por um valor próximo a $-3$. Especificamente, os autores abordam o comportamento de tais grafos quando estes possuem uma valência mínima (grau) suficientemente grande. O estudo foca em dois aspectos primários:

1. Determinar se o autovalor mínimo é forçado a ser pelo menos $-3$ (em vez de apenas maior que $-3 - \varepsilon$) sob condições de alta valência.
2. Caracterizar o reticulado integral $\Lambda(G, \sigma)$ associado a esses grafos, especificamente determinando se ele se imerge em uma soma direta de reticulados padrão $\mathbb{Z}^n$ e cópias do reticulado de raiz $E_8$.
3. Analisar a "extensibilidade" desses grafos: se um grafo assinado com $\lambda_{\min} \ge -3$ pode ser um subgrafo induzido próprio de um grafo assinado conexo maior com o mesmo limite de autovalor.

Metodologia
Os autores empregam uma combinação de teoria espectral de grafos e teoria de reticulados, utilizando as seguintes ferramentas principais:

• Associação de Reticulados: Para um grafo assinado com autovalor mínimo $\lambda$, a matriz $G_r(G, \sigma) = A(G, \sigma) - \lfloor \lambda \rfloor I$ é semidefinida positiva. O reticulado $\Lambda(G, \sigma)$ é definido como o reticulado integral gerado pelas colunas de uma matriz $N$ tal que $G_r(G, \sigma) = N^T N$.
• Grafos Assinados de Hoffman: Os autores utilizam o arcabouço de grafos assinados de Hoffman, que consistem em vértices "magros" (slim) e "gordos" (fat). Os vértices gordos são substituídos por cliques positivos para construir grafos maiores. Este arcabouço permite a análise de limites de autovalores conforme o tamanho dos cliques cresce.
• Subgrafos Proibidos Mínimos: A estratégia de prova baseia-se na identificação de um conjunto finito de "grafos assinados de Hoffman gordos mínimos proibidos" para o limiar $\lambda = -3$. Ao provar que este conjunto é finito, os autores estabelecem que grafos com valência mínima suficientemente grande não podem conter essas estruturas proibidas, forçando assim o autovalor a satisfazer limites específicos.
• Reticulados Unimodulares Sem Raízes: O artigo constrói exemplos de grafos assinados não extensíveis usando reticulados unimodulares irredutíveis gerados por vetores de norma ao quadrado 3 (sem raízes), como o reticulado Leech curto e o reticulado Conway-Borcherds.

Principais Contribuições e Resultados

1. Eliminação do Gap de Autovalor (Teorema 1.3):
   O artigo prova que existem um número real positivo $\varepsilon$ e um inteiro positivo $\kappa_3$ tais que, se um grafo assinado conexo possui $\lambda_{\min} > -3 - \varepsilon$ e valência mínima pelo menos $\kappa_3$, então $\lambda_{\min} \ge -3$. Isso fortalece resultados anteriores que caracterizaram grafos com $\lambda_{\min} \in (-2, -1]$ e $(-1-\sqrt{2}, -1]$.

2. Estrutura de Reticulado (Teorema 1.3):
   Sob as condições acima, o reticulado associado $\Lambda(G, \sigma)$ é provado ser um subreticulado de uma soma direta do reticulado padrão $\mathbb{Z}^n$ e cópias do reticulado de raiz $E_8$. Isso generaliza descobertas anteriores onde os reticulados para $\lambda_{\min} \ge -2$ eram restritos aos reticulados de raiz $A_n, D_n, E_6, E_7, E_8$.

3. Extensibilidade de Grafos (Teorema 1.7):
   Os autores mostram que, se um grafo assinado conexo possui $\lambda_{\min} \ge -3$ e valência mínima suficientemente grande, ele é extensível. Isto é, ele pode ser imerso como um subgrafo induzido próprio em infinitos grafos assinados conexos maiores que também satisfazem $\lambda_{\min} \ge -3$. Isso implica que tais grafos não são maximais no contexto de preservação de autovalor.

4. Construção de Grafos Não Extensíveis:
   O artigo constrói exemplos específicos de grafos assinados regulares não extensíveis com $\lambda_{\min} = -3$. Estes são derivados de reticulados unimodulares irredutíveis gerados por vetores de norma ao quadrado 3 sem raízes (ex: o reticulado Leech curto, o reticulado Leech ímpar e o reticulado Conway-Borcherds).

   • Um exemplo é fornecido com ordem 2300 e valência 891.
   • Esta construção demonstra que a constante $\kappa_4$ no Teorema 1.7 (o limiar para extensibilidade) deve ser pelo menos 892.

5. Finitude de Estruturas Proibidas (Teorema 3.2):
   Um resultado técnico crítico é a prova de que o conjunto de grafos assinados de Hoffman gordos mínimos proibidos para $\lambda = -3$ é finito. Esta finitude é essencial para estabelecer a existência do limiar de valência $\kappa_3$.

Significância e Alegações
O artigo posiciona-se como um fortalecimento substancial das caracterizações prévias de grafos assinados com autovalores mínimos fixos.

• Motivação: O trabalho é motivado pela classificação de grafos assinados com $\lambda_{\min} \ge -2$ (que correspondem a reticulados de raiz) e pelo problema mais amplo de determinar o número máximo de linhas biangulares no espaço Euclidiano com ângulos específicos.
• Classificação: Os autores sugerem que, embora existam infinitos grafos extensíveis com $\lambda_{\min} \ge -3$, a existência de grafos não extensíveis é provavelmente finita (ou pelo menos restrita a construções de reticulados específicos). Eles propõem o Problema 1.9: "Existem infinitas classes de troca (switching classes) de grafos assinados não extensíveis com autovalor mínimo pelo menos $-3$?" Com base em seus resultados, eles esperam que a resposta seja negativa.
• Limitações: O artigo não pretende classificar totalmente todos os grafos assinados não extensíveis com $\lambda_{\min} = -3$, mas fornece um arcabouço para compreender suas propriedades de reticulado e para construir exemplos específicos. Ele destaca que a constante $\kappa_4$ exigida pelo teorema de extensibilidade é não trivial (pelo menos 892), indicando que grafos pequenos podem se comportar de maneira diferente de grafos com alta valência.

Em resumo, o artigo estabelece que a alta valência força grafos assinados com autovalores próximos de $-3$ a conformarem-se a uma estrutura de reticulado específica ($\mathbb{Z}^n \oplus E_8^k$) e a se tornarem extensíveis, enquanto identifica construções derivadas de reticulados específicos como as prováveis candidatas a grafos assinados não extensíveis e maximais neste regime.