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

Sintesi Tecnica: Grafi con segni con autovalore minimo fissato almeno pari a −3 e i loro reticoli

Enunciato del Problema
Questo articolo investiga le proprietà strutturali di grafi con segni connessi $(G, \sigma)$ il cui autovalore minimo, $\lambda_{\min}(G, \sigma)$, è limitato inferiormente da un valore vicino a $-3$. Nello specifico, gli autori affrontano il comportamento di tali grafi quando possiedono una valenza minima (grado) sufficientemente elevata. Lo studio si concentra su due aspetti primari:

1. Determinare se l'autovalore minimo sia costretto a essere almeno $-3$ (anziché solo maggiore di $-3 - \varepsilon$) sotto condizioni di alta valenza.
2. Caratterizzare il reticolo integrale $\Lambda(G, \sigma)$ associato a questi grafi, specificamente determinando se esso si imbedda in una somma diretta di reticoli standard $\mathbb{Z}^n$ e copie del reticolo radice $E_8$.
3. Analizzare l' "estensibilità" di questi grafi: se un grafo con segni con $\lambda_{\min} \ge -3$ possa essere un sottografo indotto proprio di un grafo con segni connesso più grande con lo stesso limite di autovalore.

Metodologia
Gli autori utilizzano una combinazione di teoria spettrale dei grafi e teoria dei reticoli, impiegando i seguenti strumenti chiave:

• Associazione di Reticoli: Per un grafo con segni con autovalore minimo $\lambda$, la matrice $G_r(G, \sigma) = A(G, \sigma) - \lfloor \lambda \rfloor I$ è semidefinita positiva. Il reticolo $\Lambda(G, \sigma)$ è definito come il reticolo integrale generato dalle colonne di una matrice $N$ tale che $G_r(G, \sigma) = N^T N$.
• Grafi con Segni di Hoffman: Gli autori utilizzano il framework dei grafi con segni di Hoffman, che consistono in vertici "snelli" (slim) e "grassi" (fat). I vertici grassi sono sostituiti da clique positive per costruire grafi più grandi. Questo framework permette l'analisi dei limiti degli autovalori al crescere delle dimensioni delle clique.
• Sottografi Minimi Vietati: La strategia di dimostrazione si basa sull'identificazione di un insieme finito di "grafi con segni di Hoffman grassi minimi vietati" per la soglia $\lambda = -3$. Dimostrando che questo insieme è finito, gli autori stabiliscono che i grafi con valenza minima sufficientemente grande non possono contenere queste strutture vietate, imponendo così che l'autovalore soddisfi specifici limiti.
• Reticoli Unimodulari Senza Radici: Il documento costruisce esempi di grafi con segni non estendibili utilizzando reticoli unimodulari irriducibili generati da vettori di norma quadrata 3 (senza radici), come il reticolo Leech più corto e il reticolo Conway-Borcherds.

Contributi Chiave e Risultati

1. Eliminazione del Gap di Autovalore (Teorema 1.3):
   Il documento prova che esistono un numero reale positivo $\varepsilon$ e un intero positivo $\kappa_3$ tali che, se un grafo con segni connesso ha $\lambda_{\min} > -3 - \varepsilon$ e valenza minima almeno $\kappa_3$, allora $\lambda_{\min} \ge -3$. Ciò rafforza i risultati precedenti che caratterizzavano i grafi con $\lambda_{\min} \in (-2, -1]$ e $(-1-\sqrt{2}, -1]$.

2. Struttura del Reticolo (Teorema 1.3):
   Sotto le condizioni sopra descritte, il reticolo associato $\Lambda(G, \sigma)$ è dimostrato essere un sottoreticolo di una somma diretta del reticolo standard $\mathbb{Z}^n$ e di copie del reticolo radice $E_8$. Questo generalizza i risultati precedenti in cui i reticoli per $\lambda_{\min} \ge -2$ erano limitati ai reticoli radice $A_n, D_n, E_6, E_7, E_8$.

3. Estensibilità dei Grafi (Teorema 1.7):
   Gli autori dimostrano che se un grafo con segni connesso ha $\lambda_{\min} \ge -3$ e valenza minima sufficientemente grande, esso è estensibile. Ovvero, può essere imbeduto come sottografo indotto proprio in infiniti grafi con segni connessi più grandi che soddisfano ugualmente il limite di autovalore $\lambda_{\min} \ge -3$. Ciò implica che tali grafi non sono massimali nel contesto della preservazione dell'autovalore.

4. Costruzione di Grafi Non Estendibili:
   Il documento costruisce esempi specifici di grafi regolari con segni non estendibili con $\lambda_{\min} = -3$. Questi sono derivati da reticoli unimodulari irriducibili generati da vettori di norma quadrata 3 senza radici (ad esempio, il reticolo Leech più corto, il reticolo Leech dispari e il reticolo Conway-Borcherds).

• Viene fornito un esempio con ordine 2300 e valenza 891.
• Questa costruzione dimostra che la costante $\kappa_4$ nel Teorema 1.7 (la soglia per l'estensibilità) deve essere almeno 892.

5. Finitezza delle Strutture Vietate (Teorema 3.2):
   Un risultato tecnico critico è la dimostrazione che l'insieme dei grafi con segni di Hoffman grassi minimi vietati per $\lambda = -3$ è finito. Questa finitezza è essenziale per stabilire l'esistenza della soglia di valenza $\kappa_3$.

Significatività e Rivendicazioni
Il documento si pone come un sostanziale rafforzamento delle precedenti caratterizzazioni di grafi con segni con autovalori minimi fissati.

• Motivazione: Il lavoro è motivato dalla classificazione dei grafi con segni con $\lambda_{\min} \ge -2$ (che corrispondono ai reticoli radice) e dal problema più ampio di determinare il numero massimo di linee biangolari nello spazio euclideo con angoli specifici.
• Classificazione: Gli autori suggeriscono che, mentre esistono infiniti grafi estendibili con $\lambda_{\min} \ge -3$, l'esistenza di grafi non estendibili è probabilmente finita (o almeno limitata a specifiche costruzioni di reticoli). Essi pongono il Problema 1.9: "Esistono infiniti classi di switching di grafi con segni non estendibili con autovalore minimo almeno $-3$?". In base ai loro risultati, si aspettano che la risposta sia negativa.
• Limitazioni: Il documento non pretende di classificare completamente tutti i grafi con segni non estendibili con $\lambda_{\min} = -3$, ma fornisce un quadro per comprendere le proprietà dei loro reticoli e per costruire esempi specifici. Evidenzia che la costante $\kappa_4$ richiesta dal teorema di estensibilità è non banale (almeno 892), indicando che i grafi piccoli possono comportarsi diversamente rispetto a quelli con alta valenza.

In sintesi, il documento stabilisce che l'alta valenza forza i grafi con segni con autovalori vicini a $-3$ a conformarsi a una specifica struttura di reticolo ($\mathbb{Z}^n \oplus E_8^k$) e a diventare estendibili, identificando al contempo le costruzioni derivate da reticoli come i candidati probabili per i grafi con segni non estendibili e massimali in questo regime.