Resumen Técnico: Códigos LCD Binarios y sus Representaciones Gráficas

Planteamiento del Problema

El artículo aborda el problema fundamental de caracterizar qué grafos simples (grafos sin bucles ni aristas múltiples) generan códigos binarios de Dualidad Complementaria Lineal (LCD) a través de sus matrices de adyacencia. Si bien investigaciones anteriores establecieron conexiones entre los espectros de grafos y las dimensiones de los códigos, y proporcionaron condiciones suficientes para familias específicas de grafos (como los Grafos Fuertemente Regulares) para obtener códigos LCD, faltaba una caracterización completa. Además, la relación entre la equivalencia de códigos y el isomorfismo de grafos para códigos LCD, aunque se sabía que era reducible al Problema del Isomorfismo de Grafos (GI), carecía de una biyección constructiva que facilitara la clasificación sistemática de grafos basándose en herramientas de la teoría de códigos.

El desafío central es determinar las condiciones necesarias y suficientes para que la matriz de adyacencia $A$ de un grafo sea idempotente sobre $\mathbb{F}_2$ (es decir, $A^2 = A$), ya que esta propiedad es equivalente a que el espacio generado por las filas de $A$ forme un código LCD.

Metodología

El autor emplea un enfoque dual que combina la teoría de códigos algebraicos y la teoría de grafos algebraica:

1. Proyectores Ortogonales e Idempotencia: El artículo utiliza la propiedad estructural de que un código binario $C$ es LCD si y solo si su proyector ortogonal $\Pi_C$ es una matriz simétrica que satisface $\Pi_C^2 = \Pi_C$. El autor establece que, para códigos LCD binarios pares, este proyector corresponde exactamente a la matriz de adyacencia de un grafo simple.
2. Caracterización Combinatoria: Al analizar la condición de idempotencia $A^2 = A$ sobre $\mathbb{F}_2$, el artículo deriva restricciones combinatorias sobre la estructura del grafo, relacionando específicamente los grados de los vértices y el número de vecinos comunes entre vértices adyacentes y no adyacentes.
3. Análisis de Grafos de Distancia-Regular (DRG): El artículo aplica la relación de recurrencia de tres términos de las matrices de distancia para DRGs. Esto permite reducir la condición de idempotencia a restricciones de paridad explícitas sobre los parámetros del array de intersección $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$.
4. Fórmulas de Masa para la Clasificación: Para clasificar grafos con matrices de adyacencia idempotentes, el artículo aprovecha las fórmulas de masa existentes para códigos LCD binarios (desarrolladas por Carlet et al.). Al establecer una biyección entre códigos no equivalentes y grafos no isomorfos, el autor evita la enumeración exhaustiva de grafos, utilizando en su lugar la clasificación conocida de códigos LCD para inferir la clasificación de los grafos correspondientes.

Contribuciones Clave

1. Caracterización Necesaria y Suficiente de DRGs

El artículo proporciona una caracterización completa de los grafos de distancia-regular que generan códigos LCD binarios pares. Para un DRG con array de intersección $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$, la matriz de adyacencia genera un código LCD si y solo si:

• $b_0 \equiv 0 \pmod 2$ (el grado es par);
• $a_1 \equiv 1 \pmod 2$, donde $a_1 = b_0 - b_1 - c_1$;
• $c_2 \equiv 0 \pmod 2$.

Este resultado generaliza y fortalece las condiciones suficientes anteriores para Grafos Fuertemente Regulares (SRGs) propuestas por Key y Rodrigues, extendiendo el alcance a todos los grafos de distancia-regular.

2. Biyección que Preserva la Equivalencia

El artículo establece una biyección entre:

• Códigos LCD binarios pares de longitud $n$;
• Grafos simples en $n$ vértices con matrices de adyacencia idempotentes sobre $\mathbb{F}_2$.

Crucialmente, esta biyección preserva la equivalencia: dos códigos son permutacionalmente equivalentes si y solo si sus grafos correspondientes son isomorfos. Esto permite la traducción de problemas entre la teoría de códigos y la teoría de grafos.

3. Condiciones Combinatorias

Un grafo simple genera un código LCD binario par si y solo si:

• Cada vértice tiene un grado par;
• Cualquier par de vértices adyacentes tiene un número impar de vecinos comunes;
• Cualquier par de vértices no adyacentes tiene un número par de vecinos comunes.

4. Clasificación de Grafos Pequeños

Utilizando la biyección y las fórmulas de masa, el artículo clasifica todos los grafos simples con matrices de adyacencia idempotentes en hasta 13 vértices. De 22.213 códigos LCD binarios de longitud $n \le 13$, el autor identifica 1.208 grafos no isomorfos, incluyendo familias conocidas como grafos completos, grafos multipartitos completos y ciertos grafos fuertemente regulares.

Resultados

Caracterización de Familias Específicas de Grafos

El teorema general de DRG produce criterios precisos para varias familias de grafos bien conocidas:

• Grafos Completos ($K_n$): Generan un código LCD si y solo si $n$ es impar.
• Grafos Cíclicos ($C_n$): Solo $C_3$ (que es $K_3$) genera un código LCD; los ciclos con $n \ge 4$ no lo hacen.
• Grafos de Hamming ($H(n, m)$): Generan un código LCD si y solo si $m$ es impar.
• Grafos de Johnson ($J(n, k)$): Generan un código LCD si y solo si $n$ es impar.
• Grafos de Grassmann ($J_q(n, k)$): Generan un código LCD si y solo si $n$ es impar y $q$ es impar. Si $q$ es par, nunca generan un código LCD.

Grafos de Conferencia y la Observación de Haemers

El artículo aborda una observación computacional de Haemers, Peeters y van Rijckevorsel sobre los grafos de conferencia (SRGs con parámetros $(q, (q-1)/2, (q-5)/4, (q-1)/4)$).

• Demostración Teórica: El artículo demuestra que un grafo de conferencia genera un código LCD binario par si y solo si $q \equiv 1 \pmod 8$.
• Equivalencia: Confirma que los grafos de conferencia no isomorfos con $q \equiv 1 \pmod 8$ generan códigos no equivalentes. Esto proporciona una explicación teórica a la observación de que los grafos no isomorfos en esta clase producen códigos distintos, una propiedad verificada previamente solo computacionalmente para casos específicos como $srg(25, 12, 5, 6)$.

Clasificación Computacional

Para $n \le 13$, la clasificación revela:

• 44 grafos pertenecientes a familias bien conocidas (6 grafos completos, 36 grafos multipartitos completos, 2 grafos fuertemente regulares).
• Los dos grafos fuertemente regulares identificados son el grafo de Paley de orden 9 ($srg(9, 4, 1, 2)$) y el complemento del grafo de Petersen ($srg(10, 6, 3, 4)$).
• Se confirma que los códigos generados por estos grafos específicos son óptimos según las tablas de Grassl.

Significado y Afirmaciones

El artículo afirma cerrar la brecha entre la teoría de códigos LCD y la teoría de grafos al establecer una correspondencia estructural que es tanto necesaria como suficiente.

• Unificación: La caracterización unifica el tratamiento de los grafos completos, de Hamming, de Johnson y de Grassmann bajo un único marco de distancia-regularidad.
• Explicación Teórica: Proporciona la primera justificación teórica para la observación de que los grafos de conferencia no isomorfos generan códigos no equivalentes, superando la verificación empírica.
• Innovación Metodológica: El trabajo demuestra que las fórmulas de masa, tradicionalmente utilizadas para clasificar códigos, pueden ser reutilizadas eficazmente para clasificar grafos con propiedades algebraicas específicas (matrices de adyacencia idempotentes), ofreciendo una nueva herramienta para la enumeración de grafos.
• Problemas Abiertos: El artículo nota modestamente que, aunque el grafo de Paley alcanza la mayor distancia mínima para $srg(41, 20, 9, 10)$, sigue siendo una pregunta abierta si el grafo de Paley es el optimizador único para todos los grafos de conferencia con $q \equiv 1 \pmod 8$ y $q > 41$.