Resumo Técnico: Códigos LCD Binários e Suas Representações Gráficas

Declaração do Problema

O artigo aborda o problema fundamental de caracterizar quais grafos simples (grafos sem laços ou arestas múltiplas) geram códigos Lineares Complementares Duais (LCD) binários por meio de suas matrizes de adjacência. Embora pesquisas anteriores tenham estabelecido conexões entre espectros de grafos e dimensões de códigos, e fornecido condições suficientes para famílias específicas de grafos (como Grafos Regularmente Fortes) produzirem códigos LCD, uma caracterização completa estava ausente. Além disso, a relação entre equivalência de códigos e isomorfismo de grafos para códigos LCD, embora soubesse ser redutível ao Problema de Isomorfismo de Grafos (GI), carecia de uma bijeção construtiva que pudesse facilitar a classificação sistemática de grafos com base em ferramentas da teoria de códigos.

O desafio central é determinar condições necessárias e suficientes para que a matriz de adjacência $A$ de um grafo seja idempotente sobre $\mathbb{F}_2$ (isto é, $A^2 = A$), pois essa propriedade é equivalente ao fato de o espaço gerado pelas linhas de $A$ formar um código LCD.

Metodologia

O autor emprega uma abordagem dual combinando teoria de códigos algébrica e teoria de grafos algébrica:

1. Projetores Ortogonais e Idempotência: O artigo utiliza a propriedade estrutural de que um código binário $C$ é LCD se e somente se seu projetor ortogonal $\Pi_C$ for uma matriz simétrica satisfazendo $\Pi_C^2 = \Pi_C$. O autor estabelece que, para códigos LCD binários pares, esse projetor corresponde exatamente à matriz de adjacência de um grafo simples.
2. Caracterização Combinatória: Ao analisar a condição de idempotência $A^2 = A$ sobre $\mathbb{F}_2$, o artigo deriva restrições combinatórias na estrutura do grafo, relacionando especificamente os graus dos vértices e o número de vizinhos comuns entre vértices adjacentes e não adjacentes.
3. Análise de Grafos Regularmente Distanciados (DRG): O artigo aplica a relação de recorrência de três termos das matrizes de distância para DRGs. Isso permite reduzir a condição de idempotência a restrições de paridade explícitas nos parâmetros do array de interseção $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$.
4. Fórmulas de Massa para Classificação: Para classificar grafos com matrizes de adjacência idempotentes, o artigo aproveita fórmulas de massa existentes para códigos LCD binários (desenvolvidas por Carlet et al.). Ao estabelecer uma bijeção entre códigos inequivalentes e grafos não isomorfos, o autor evita a enumeração exaustiva de grafos, utilizando em vez disso a classificação conhecida de códigos LCD para inferir a classificação dos grafos correspondentes.

Principais Contribuições

1. Caracterização Necessária e Suficiente de DRGs

O artigo fornece uma caracterização completa de grafos regularmente distanciados que produzem códigos LCD binários pares. Para um DRG com array de interseção $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$, a matriz de adjacência gera um código LCD se e somente se:

• $b_0 \equiv 0 \pmod 2$ (valência é par);
• $a_1 \equiv 1 \pmod 2$, onde $a_1 = b_0 - b_1 - c_1$;
• $c_2 \equiv 0 \pmod 2$.

Este resultado generaliza e fortalece condições suficientes anteriores para Grafos Regularmente Fortes (SRGs) por Key e Rodrigues, estendendo o escopo a todos os grafos regularmente distanciados.

2. Bijeção Preservadora de Equivalência

O artigo estabelece uma bijeção entre:

• Códigos LCD binários pares de comprimento $n$;
• Grafos simples em $n$ vértices com matrizes de adjacência idempotentes sobre $\mathbb{F}_2$.

Crucialmente, esta bijeção preserva a equivalência: dois códigos são permutação-equivalentes se e somente se seus grafos correspondentes forem isomorfos. Isso permite a tradução de problemas entre teoria de códigos e teoria de grafos.

3. Condições Combinatórias

Um grafo simples produz um código LCD binário par se e somente se:

• Todo vértice tem grau par;
• Quaisquer dois vértices adjacentes têm um número ímpar de vizinhos comuns;
• Quaisquer dois vértices não adjacentes têm um número par de vizinhos comuns.

4. Classificação de Grafos Pequenos

Usando a bijeção e fórmulas de massa, o artigo classifica todos os grafos simples com matrizes de adjacência idempotentes em até 13 vértices. De 22.213 códigos LCD binários de comprimento $n \le 13$, o autor identifica 1.208 grafos não isomorfos, incluindo famílias conhecidas como grafos completos, grafos multipartidos completos e grafos regularmente fortes específicos.

Resultados

Caracterização de Famílias Específicas de Grafos

O teorema geral de DRG produz critérios precisos para várias famílias de grafos bem conhecidas:

• Grafos Completos ($K_n$): Produzem um código LCD se e somente se $n$ for ímpar.
• Grafos Cíclicos ($C_n$): Apenas $C_3$ (que é $K_3$) produz um código LCD; ciclos com $n \ge 4$ não produzem.
• Grafos de Hamming ($H(n, m)$): Produzem um código LCD se e somente se $m$ for ímpar.
• Grafos de Johnson ($J(n, k)$): Produzem um código LCD se e somente se $n$ for ímpar.
• Grafos de Grassmann ($J_q(n, k)$): Produzem um código LCD se e somente se $n$ for ímpar e $q$ for ímpar. Se $q$ for par, eles nunca produzem um código LCD.

Grafos de Conferência e Observação de Haemers

O artigo aborda uma observação computacional de Haemers, Peeters e van Rijckevorsel sobre grafos de conferência (SRGs com parâmetros $(q, (q-1)/2, (q-5)/4, (q-1)/4)$).

• Prova Teórica: O artigo prova que um grafo de conferência produz um código LCD binário par se e somente se $q \equiv 1 \pmod 8$.
• Equivalência: Confirma que grafos de conferência não isomorfos com $q \equiv 1 \pmod 8$ produzem códigos inequivalentes. Isso fornece uma explicação teórica para a observação de que grafos não isomorfos nesta classe produzem códigos distintos, uma propriedade anteriormente verificada apenas computacionalmente para casos específicos como $srg(25, 12, 5, 6)$.

Classificação Computacional

Para $n \le 13$, a classificação revela:

• 44 grafos pertencentes a famílias bem conhecidas (6 grafos completos, 36 grafos multipartidos completos, 2 grafos regularmente fortes).
• Os dois grafos regularmente fortes identificados são o grafo de Paley de ordem 9 ($srg(9, 4, 1, 2)$) e o complemento do grafo de Petersen ($srg(10, 6, 3, 4)$).
• Os códigos gerados por esses grafos específicos são confirmados como ótimos de acordo com as tabelas de Grassl.

Significado e Alegações

O artigo afirma preencher a lacuna entre a teoria de códigos LCD e a teoria de grafos, estabelecendo uma correspondência estrutural que é tanto necessária quanto suficiente.

• Unificação: A caracterização unifica o tratamento de grafos completos, de Hamming, de Johnson e de Grassmann sob um único framework de regularidade de distância.
• Explicação Teórica: Fornece a primeira justificação teórica para a observação de que grafos de conferência não isomorfos produzem códigos inequivalentes, indo além da verificação empírica.
• Inovação Metodológica: O trabalho demonstra que fórmulas de massa, tradicionalmente usadas para classificar códigos, podem ser efetivamente reaproveitadas para classificar grafos com propriedades algébricas específicas (matrizes de adjacência idempotentes), oferecendo uma nova ferramenta para enumeração de grafos.
• Problemas Abertos: O artigo nota modestamente que, embora o grafo de Paley atinja a maior distância mínima para $srg(41, 20, 9, 10)$, permanece uma questão em aberto se o grafo de Paley é o otimizador único para todos os grafos de conferência com $q \equiv 1 \pmod 8$ e $q > 41$.