Riepilogo Tecnico: Codici LCD Binari e le Loro Rappresentazioni Grafiche

Enunciato del Problema

Il lavoro affronta il problema fondamentale di caratterizzare quali grafi semplici (grafi senza anelli o spigoli multipli) generano codici binari a Duale Complementare Lineare (LCD) tramite le loro matrici di adiacenza. Sebbene ricerche precedenti avessero stabilito connessioni tra gli spettri dei grafi e le dimensioni dei codici, e fornito condizioni sufficienti per specifiche famiglie di grafi (come i Grafi Fortemente Regolari) per produrre codici LCD, mancava una caratterizzazione completa. Inoltre, la relazione tra equivalenza dei codici e isomorfismo dei grafi per i codici LCD, pur essendo nota come riducibile al Problema dell'Isomorfismo di Grafi (GI), mancava di una biezione costruttiva che potesse facilitare la classificazione sistematica dei grafi basata su strumenti della teoria dei codici.

La sfida principale consiste nel determinare condizioni necessarie e sufficienti affinché la matrice di adiacenza $A$ di un grafo sia idempotente su $\mathbb{F}_2$ (cioè $A^2 = A$), poiché questa proprietà è equivalente al fatto che lo span delle righe di $A$ formi un codice LCD.

Metodologia

L'autore impiega un approccio duale che combina la teoria algebrica dei codici e la teoria algebrica dei grafi:

1. Proiettori Ortogonali e Idempotenza: Il lavoro utilizza la proprietà strutturale secondo cui un codice binario $C$ è LCD se e solo se il suo proiettore ortogonale $\Pi_C$ è una matrice simmetrica che soddisfa $\Pi_C^2 = \Pi_C$. L'autore stabilisce che, per i codici LCD binari pari, questo proiettore corrisponde esattamente alla matrice di adiacenza di un grafo semplice.
2. Caratterizzazione Combinatoria: Analizzando la condizione di idempotenza $A^2 = A$ su $\mathbb{F}_2$, il lavoro deriva vincoli combinatori sulla struttura del grafo, relazionando specificamente i gradi dei vertici e il numero di vicini comuni tra vertici adiacenti e non adiacenti.
3. Analisi dei Grafi a Distanza Regolare (DRG): Il lavoro applica la relazione di ricorrenza a tre termini delle matrici di distanza per i DRG. Ciò permette di ridurre la condizione di idempotenza a vincoli di parità espliciti sui parametri dell'array di intersezione $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$.
4. Formule di Massa per la Classificazione: Per classificare i grafi con matrici di adiacenza idempotenti, il lavoro sfrutta le esistenti formule di massa per i codici LCD binari (sviluppate da Carlet et al.). Stabilendo una biezione tra codici inequivalenti e grafi non isomorfi, l'autore evita l'enumerazione esaustiva dei grafi, utilizzando invece la classificazione nota dei codici LCD per inferire la classificazione dei grafi corrispondenti.

Contributi Chiave

1. Caratterizzazione Necessaria e Sufficiente dei DRG

Il lavoro fornisce una caratterizzazione completa dei grafi a distanza regolare che producono codici LCD binari pari. Per un DRG con array di intersezione $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$, la matrice di adiacenza genera un codice LCD se e solo se:

• $b_0 \equiv 0 \pmod 2$ (il grado è pari);
• $a_1 \equiv 1 \pmod 2$, dove $a_1 = b_0 - b_1 - c_1$;
• $c_2 \equiv 0 \pmod 2$.

Questo risultato generalizza e rafforza le precedenti condizioni sufficienti per i Grafi Fortemente Regolari (SRG) di Key e Rodrigues, estendendo la portata a tutti i grafi a distanza regolare.

2. Biezione che Preserva l'Equivalenza

Il lavoro stabilisce una biezione tra:

• Codici LCD binari pari di lunghezza $n$;
• Grafi semplici su $n$ vertici con matrici di adiacenza idempotenti su $\mathbb{F}_2$.

Crucialmente, questa biezione preserva l'equivalenza: due codici sono equivalenti per permutazione se e solo se i loro grafi corrispondenti sono isomorfi. Ciò permette la traduzione di problemi tra la teoria dei codici e la teoria dei grafi.

3. Condizioni Combinatorie

Un grafo semplice produce un codice LCD binario pari se e solo se:

• Ogni vertice ha un grado pari;
• Qualsiasi coppia di vertici adiacenti ha un numero dispari di vicini comuni;
• Qualsiasi coppia di vertici non adiacenti ha un numero pari di vicini comuni.

4. Classificazione di Grafi Piccoli

Utilizzando la biezione e le formule di massa, il lavoro classifica tutti i grafi semplici con matrici di adiacenza idempotenti su al massimo 13 vertici. Da 22.213 codici LCD binari di lunghezza $n \le 13$, l'autore identifica 1.208 grafi non isomorfi, incluse famiglie note come grafi completi, grafi multipartiti completi e specifici grafi fortemente regolari.

Risultati

Caratterizzazione di Famiglie Specifiche di Grafi

Il teorema generale sui DRG produce criteri netti per diverse famiglie di grafi ben noti:

• Grafi Complet ($K_n$): Producono un codice LCD se e solo se $n$ è dispari.
• Grafi Ciclici ($C_n$): Solo $C_3$ (che è $K_3$) produce un codice LCD; i cicli con $n \ge 4$ non lo fanno.
• Grafi di Hamming ($H(n, m)$): Producono un codice LCD se e solo se $m$ è dispari.
• Grafi di Johnson ($J(n, k)$): Producono un codice LCD se e solo se $n$ è dispari.
• Grafi di Grassmann ($J_q(n, k)$): Producono un codice LCD se e solo se $n$ è dispari e $q$ è dispari. Se $q$ è pari, non producono mai un codice LCD.

Grafi di Conferenza e l'Osservazione di Haemers

Il lavoro affronta un'osservazione computazionale di Haemers, Peeters e van Rijckevorsel riguardante i grafi di conferenza (SRG con parametri $(q, (q-1)/2, (q-5)/4, (q-1)/4)$).

• Dimostrazione Teorica: Il lavoro dimostra che un grafo di conferenza produce un codice LCD binario pari se e solo se $q \equiv 1 \pmod 8$.
• Equivalenza: Conferma che i grafi di conferenza non isomorfi con $q \equiv 1 \pmod 8$ producono codici inequivalenti. Ciò fornisce una spiegazione teorica all'osservazione secondo cui grafi non isomorfi in questa classe producono codici distinti, una proprietà precedentemente verificata solo computazionalmente per casi specifici come $srg(25, 12, 5, 6)$.

Classificazione Computazionale

Per $n \le 13$, la classificazione rivela:

• 44 grafi appartenenti a famiglie ben note (6 grafi completi, 36 grafi multipartiti completi, 2 grafi fortemente regolari).
• I due grafi fortemente regolari identificati sono il grafo di Paley di ordine 9 ($srg(9, 4, 1, 2)$) e il complementare del grafo di Petersen ($srg(10, 6, 3, 4)$).
• I codici generati da questi grafi specifici sono confermati come ottimali secondo le tabelle di Grassl.

Significato e Affermazioni

Il lavoro afferma di colmare il divario tra la teoria dei codici LCD e la teoria dei grafi stabilendo una corrispondenza strutturale che è sia necessaria che sufficiente.

• Unificazione: La caratterizzazione unifica il trattamento dei grafi completi, di Hamming, di Johnson e di Grassmann sotto un unico quadro di regolarità a distanza.
• Spiegazione Teorica: Fornisce la prima giustificazione teorica per l'osservazione secondo cui i grafi di conferenza non isomorfi producono codici inequivalenti, andando oltre la verifica empirica.
• Innovazione Metodologica: Il lavoro dimostra che le formule di massa, tradizionalmente utilizzate per classificare i codici, possono essere efficacemente riutilizzate per classificare grafi con specifiche proprietà algebriche (matrici di adiacenza idempotenti), offrendo un nuovo strumento per l'enumerazione dei grafi.
• Problemi Aperti: Il lavoro nota modestamente che, sebbene il grafo di Paley raggiunga la massima distanza minima per $srg(41, 20, 9, 10)$, rimane una questione aperta se il grafo di Paley sia l'ottimizzatore unico per tutti i grafi di conferenza con $q \equiv 1 \pmod 8$ e $q > 41$.