Résumé Technique : Codes LCD Binaires et Leurs Représentations Graphiques

Énoncé du Problème

L'article aborde le problème fondamental de caractériser quels graphes simples (graphes sans boucles ni arêtes multiples) génèrent des codes binaires à Dualité Complémentaire Linéaire (LCD) via leurs matrices d'adjacence. Alors que des recherches antérieures ont établi des liens entre les spectres de graphes et les dimensions de codes, et fourni des conditions suffisantes pour certaines familles de graphes (telles que les Graphes Fortement Réguliers) afin de produire des codes LCD, une caractérisation complète faisait défaut. De plus, la relation entre l'équivalence de codes et l'isomorphisme de graphes pour les codes LCD, bien que connue comme réductible au Problème d'Isomorphisme de Graphes (GI), manquait d'une bijection constructive permettant une classification systématique des graphes basée sur des outils de la théorie des codes.

Le défi central consiste à déterminer des conditions nécessaires et suffisantes pour qu'une matrice d'adjacence $A$ d'un graphe soit idempotente sur $\mathbb{F}_2$ (c'est-à-dire $A^2 = A$), car cette propriété est équivalente au fait que l'espace vectoriel engendré par les lignes de $A$ forme un code LCD.

Méthodologie

L'auteur emploie une approche duale combinant la théorie algébrique des codes et la théorie algébrique des graphes :

1. Projecteurs Orthogonaux et Idempotence : L'article exploite la propriété structurelle selon laquelle un code binaire $C$ est LCD si et seulement si son projecteur orthogonal $\Pi_C$ est une matrice symétrique satisfaisant $\Pi_C^2 = \Pi_C$. L'auteur établit que pour les codes LCD binaires pairs, ce projecteur correspond exactement à la matrice d'adjacence d'un graphe simple.
2. Caractérisation Combinatoire : En analysant la condition d'idempotence $A^2 = A$ sur $\mathbb{F}_2$, l'article dérive des contraintes combinatoires sur la structure du graphe, reliant spécifiquement les degrés des sommets et le nombre de voisins communs entre sommets adjacents et non adjacents.
3. Analyse des Graphes à Distance Régulière (DRG) : L'article applique la relation de récurrence à trois termes des matrices de distance pour les DRG. Cela permet de réduire la condition d'idempotence à des contraintes de parité explicites sur les paramètres du tableau d'intersection $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$.
4. Formules de Masse pour la Classification : Pour classifier les graphes dont les matrices d'adjacence sont idempotentes, l'article exploite des formules de masse existantes pour les codes LCD binaires (développées par Carlet et al.). En établissant une bijection entre les codes non équivalents et les graphes non isomorphes, l'auteur évite l'énumération exhaustive des graphes, utilisant à la place la classification connue des codes LCD pour déduire la classification des graphes correspondants.

Contributions Clés

1. Caractérisation Nécessaire et Suffisante des DRG

L'article fournit une caractérisation complète des graphes à distance régulière qui génèrent des codes LCD binaires pairs. Pour un DRG avec tableau d'intersection $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$, la matrice d'adjacence génère un code LCD si et seulement si :

• $b_0 \equiv 0 \pmod 2$ (le degré est pair) ;
• $a_1 \equiv 1 \pmod 2$, où $a_1 = b_0 - b_1 - c_1$ ;
• $c_2 \equiv 0 \pmod 2$.

Ce résultat généralise et renforce les conditions suffisantes précédentes pour les Graphes Fortement Réguliers (SRG) établies par Key et Rodrigues, étendant la portée à tous les graphes à distance régulière.

2. Bijection Préservant l'Équivalence

L'article établit une bijection entre :

• Les codes LCD binaires pairs de longueur $n$ ;
• Les graphes simples à $n$ sommets dont les matrices d'adjacence sont idempotentes sur $\mathbb{F}_2$.

Crucialement, cette bijection préserve l'équivalence : deux codes sont équivalents par permutation si et seulement si leurs graphes correspondants sont isomorphes. Cela permet la traduction de problèmes entre la théorie des codes et la théorie des graphes.

3. Conditions Combinatoires

Un graphe simple génère un code LCD binaire pair si et seulement si :

• Chaque sommet a un degré pair ;
• Toute paire de sommets adjacents a un nombre impair de voisins communs ;
• Toute paire de sommets non adjacents a un nombre pair de voisins communs.

4. Classification des Petits Graphes

En utilisant la bijection et les formules de masse, l'article classe tous les graphes simples dont les matrices d'adjacence sont idempotentes et comportant au plus 13 sommets. Parmi 22 213 codes LCD binaires de longueur $n \le 13$, l'auteur identifie 1 208 graphes non isomorphes, incluant des familles connues telles que les graphes complets, les graphes multipartites complets et certains graphes fortement réguliers.

Résultats

Caractérisation de Familles de Graphes Spécifiques

Le théorème général sur les DRG fournit des critères précis pour plusieurs familles de graphes bien connues :

• Graphes Complets ($K_n$) : Génèrent un code LCD si et seulement si $n$ est impair.
• Graphes Cycles ($C_n$) : Seul $C_3$ (qui est $K_3$) génère un code LCD ; les cycles avec $n \ge 4$ ne le font pas.
• Graphes de Hamming ($H(n, m)$) : Génèrent un code LCD si et seulement si $m$ est impair.
• Graphes de Johnson ($J(n, k)$) : Génèrent un code LCD si et seulement si $n$ est impair.
• Graphes de Grassmann ($J_q(n, k)$) : Génèrent un code LCD si et seulement si $n$ est impair et $q$ est impair. Si $q$ est pair, ils ne génèrent jamais un code LCD.

Graphes de Conférence et Observation de Haemers

L'article traite d'une observation computationnelle de Haemers, Peeters et van Rijckevorsel concernant les graphes de conférence (SRG avec paramètres $(q, (q-1)/2, (q-5)/4, (q-1)/4)$).

• Preuve Théorique : L'article démontre qu'un graphe de conférence génère un code LCD binaire pair si et seulement si $q \equiv 1 \pmod 8$.
• Équivalence : Il confirme que les graphes de conférence non isomorphes avec $q \equiv 1 \pmod 8$ génèrent des codes non équivalents. Cela fournit une explication théorique à l'observation selon laquelle des graphes non isomorphes dans cette classe produisent des codes distincts, une propriété précédemment vérifiée uniquement par calcul pour des cas spécifiques comme $srg(25, 12, 5, 6)$.

Classification Computationnelle

Pour $n \le 13$, la classification révèle :

• 44 graphes appartenant à des familles bien connues (6 graphes complets, 36 graphes multipartites complets, 2 graphes fortement réguliers).
• Les deux graphes fortement réguliers identifiés sont le graphe de Paley d'ordre 9 ($srg(9, 4, 1, 2)$) et le complémentaire du graphe de Petersen ($srg(10, 6, 3, 4)$).
• Les codes générés par ces graphes spécifiques sont confirmés comme optimaux selon les tables de Grassl.

Signification et Revendications

L'article revendique combler le fossé entre la théorie des codes LCD et la théorie des graphes en établissant une correspondance structurelle qui est à la fois nécessaire et suffisante.

• Unification : La caractérisation unifie le traitement des graphes complets, de Hamming, de Johnson et de Grassmann sous un cadre unique de régularité à distance.
• Explication Théorique : Il fournit la première justification théorique de l'observation selon laquelle les graphes de conférence non isomorphes génèrent des codes non équivalents, dépassant la vérification empirique.
• Innovation Méthodologique : Le travail démontre que les formules de masse, traditionnellement utilisées pour classifier les codes, peuvent être efficacement réutilisées pour classifier les graphes possédant des propriétés algébriques spécifiques (matrices d'adjacence idempotentes), offrant ainsi un nouvel outil pour l'énumération des graphes.
• Problèmes Ouverts : L'article note modestement que, bien que le graphe de Paley atteigne la plus grande distance minimale pour $srg(41, 20, 9, 10)$, il reste une question ouverte de savoir si le graphe de Paley est l'optimiseur unique pour tous les graphes de conférence avec $q \equiv 1 \pmod 8$ et $q > 41$.