技術的概要：2 進 LCD コードとそのグラフ表現

問題提起

本論文は、隣接行列を通じて 2 進線形相補的双対（LCD）コードを生成する単純グラフ（ループや多重辺を持たないグラフ）を特徴づけるという根本的な問題に取り組む。以前の研究では、グラフのスペクトルとコードの次元との間の関連性が確立され、特定のグラフ族（強正則グラフなど）が LCD コードを生成するための十分条件が提供されていたが、完全な特徴づけは欠けていた。さらに、LCD コードにおけるコードの同値性とグラフの同型性の関係は、グラフ同型問題（GI）に帰着可能であることが知られていたものの、コード理論的ツールに基づいてグラフを体系的に分類することを可能にする構成的双射は存在しなかった。

核心的な課題は、グラフの隣接行列 $A$ が $\mathbb{F}_2$ 上で冪等（すなわち $A^2 = A$）となるための必要十分条件を決定することである。なぜなら、この性質は $A$ の行空間が LCD コードを形成することと同等だからである。

手法

著者は、代数的コード理論と代数的グラフ理論を組み合わせる二重のアプローチを採用している：

1. 直交射影と冪等性：本論文は、2 進コード $C$ が LCD であるための構造的特性、すなわちその直交射影 $\Pi_C$ が $\Pi_C^2 = \Pi_C$ を満たす対称行列であることと必要十分であるという性質を利用する。著者は、2 進偶数 LCD コードの場合、この射影が単純グラフの隣接行列と完全に一致することを確立している。
2. 組合せ論的特徴づけ：$\mathbb{F}_2$ 上での冪等条件 $A^2 = A$ を分析することにより、本論文はグラフ構造に対する組合せ論的制約を導き出し、特に頂点の次数と、隣接する頂点同士および非隣接する頂点同士の間にある共通の近傍の数を関連付けている。
3. 距離正則グラフ（DRG）の分析：本論文は、DRG の距離行列に関する 3 項漸化式を適用する。これにより、冪等条件を交差配列パラメータ $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$ に関する明示的な偶奇の制約に還元することが可能となる。
4. 分類のための質量公式：冪等隣接行列を持つグラフを分類するために、本論文は Carlet らによって開発された 2 進 LCD コードの既存の質量公式を利用する。非同値なコードと非同型なグラフとの間の双射を確立することにより、著者はグラフの網羅的な列挙を回避し、代わりに LCD コードの既知の分類を利用して、対応するグラフの分類を推論する。

主要な貢献

1. DRG の必要十分条件による特徴づけ

本論文は、2 進偶数 LCD コードを生成する距離正則グラフの完全な特徴づけを提供する。交差配列 $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$ を持つ DRG について、その隣接行列が LCD コードを生成するのは、以下の条件を満たす場合に限られる：

• $b_0 \equiv 0 \pmod 2$（次数が偶数であること）；
• $a_1 \equiv 1 \pmod 2$（ここで $a_1 = b_0 - b_1 - c_1$）；
• $c_2 \equiv 0 \pmod 2$。

この結果は、Key と Rodrigues による強正則グラフ（SRG）に対する以前の十分条件を一般化・強化し、対象範囲をすべての距離正則グラフに拡張するものである。

2. 同値性を保存する双射

本論文は、以下の間の双射を確立する：

• 長さ $n$ の 2 進偶数 LCD コード；
• $\mathbb{F}_2$ 上で冪等隣接行列を持つ $n$ 頂点の単純グラフ。

重要なのは、この双射が同値性を保存することである。すなわち、2 つのコードが置換同値であるのは、対応するグラフが同型である場合に限られる。これにより、コード理論とグラフ理論の間で問題の変換が可能となる。

3. 組合せ論的条件

単純グラフが 2 進偶数 LCD コードを生成するのは、以下の条件を満たす場合に限られる：

• 全ての頂点の次数が偶数であること；
• 任意の 2 つの隣接する頂点が、奇数個の共通近傍を持つこと；
• 任意の 2 つの非隣接する頂点が、偶数個の共通近傍を持つこと。

4. 小規模グラフの分類

双射と質量公式を用いて、本論文は 13 頂点以下のすべての単純グラフで冪等隣接行列を持つものを分類する。長さ $n \le 13$ の 22,213 個の 2 進 LCD コードから、著者は完全グラフ、完全多部グラフ、特定の強正則グラフなどの既知の族を含む、1,208 個の非同型グラフを同定した。

結果

特定のグラフ族の特徴づけ

一般的な DRG 定理は、いくつかのよく知られたグラフ族に対して鋭い基準を与える：

• 完全グラフ（$K_n$）：$n$ が奇数の場合に限って LCD コードを生成する。
• サイクルグラフ（$C_n$）：$C_3$（すなわち $K_3$）のみが LCD コードを生成し、$n \ge 4$ のサイクルは生成しない。
• ハミンググラフ（$H(n, m)$）：$m$ が奇数の場合に限って LCD コードを生成する。
• ジョーンソングラフ（$J(n, k)$）：$n$ が奇数の場合に限って LCD コードを生成する。
• グラスマングラフ（$J_q(n, k)$）：$n$ が奇数かつ $q$ が奇数の場合に限って LCD コードを生成する。$q$ が偶数の場合、決して LCD コードを生成しない。

会議グラフと Haemers の観察

本論文は、会議グラフ（パラメータ $(q, (q-1)/2, (q-5)/4, (q-1)/4)$ を持つ SRG）に関する Haemers、Peeters、van Rijckevorsel による計算上の観察を取り扱う。

• 理論的証明：本論文は、会議グラフが 2 進偶数 LCD コードを生成するのは、$q \equiv 1 \pmod 8$ である場合に限られることを証明する。
• 同値性：$q \equiv 1 \pmod 8$ である非同型の会議グラフが非同値なコードを生成することを確認する。これは、このクラスの非同型グラフが異なるコードを生成するという観察に対する理論的説明を提供するものであり、$srg(25, 12, 5, 6)$ などの特定のケースに対しては以前に計算的に検証されていたが、それ以上のものとなる。

計算による分類

$n \le 13$ における分類は、以下の結果を示す：

• 既知の族に属する 44 個のグラフ（6 個の完全グラフ、36 個の完全多部グラフ、2 個の強正則グラフ）。
• 同定された 2 つの強正則グラフは、位数 9 の Paley グラフ（$srg(9, 4, 1, 2)$）と Petersen グラフの補グラフ（$srg(10, 6, 3, 4)$）である。
• これらの特定のグラフによって生成されるコードは、Grassl の表に従って最適であることが確認された。

意義と主張

本論文は、必要かつ十分である構造的対応を確立することにより、LCD コード理論とグラフ理論の間のギャップを埋めると主張している。

• 統合：この特徴づけは、距離正則性という単一の枠組みの下で、完全グラフ、ハミンググラフ、ジョーンソングラフ、グラスマングラフの取り扱いを統合する。
• 理論的説明：非同型の会議グラフが非同値なコードを生成するという観察に対する、初めての理論的根拠を提供し、経験的検証を超えたものとなる。
• 方法論的革新：この研究は、伝統的にコードの分類に用いられてきた質量公式が、特定の代数的性質（冪等隣接行列）を持つグラフを分類するために効果的に転用可能であることを示しており、グラフ列挙のための新たなツールを提供する。
• 未解決問題：本論文は控えめに、Paley グラフが $srg(41, 20, 9, 10)$に対して最大の最小距離を達成しているが、$q \equiv 1 \pmod 8$かつ$q > 41$ であるすべての会議グラフに対して、Paley グラフが唯一の最適化器であるかどうかは未解決の問題であると指摘している。