Recognizability equals CMSO-definability for graphs of rank-width at most two

技術的要約：ランク幅が2以下のグラフにおける認識可能性とCMSO定義可能性の等価性

問題設定
本論文は、Courcelleのプログラムにおける「認識可能性対定義可能性」の問題、特に高密度グラフ（dense graphs）に関する問題に取り組んでいる。中心となる問いは、すべてのVR認識可能（有限の頂点置換代数によって飽和される）なグラフ特性が、有界ランク幅のグラフクラス上でCMSO（Counting Monadic Second-Order logic）によって定義可能であるかどうかである。この等価性は、有界ツリー幅（疎なグラフ）および有界線形クリーク幅については既知であるが、一般的な有界ランク幅については未解決のままであった。具体的に、本論文はランク幅が最大2のグラフのクラス $\mathcal{C}_2$ を対象としており、ランク幅1（分割分解/split-decomposition）のケースから、最初の非自明な有界ランク幅レベルへと問題を前進させている。

手法および構造的アプローチ
証明は、構造的な証拠（structural witnesses）と転置される論理オブジェクトを分離することによって進行し、問題を「スプリット・プライム（split-prime）グラフ」と「任意のグラフ」の2つの主要な段階に分けて処理する。

1. スプリット・プライムグラフの構造的組織化:

   • 著者らは、Clark–Whittleの連結関数理論、特に「フラワー（flower）」および「極大部分木（maximal partial-tree）」定理を利用して、非逐次的（non-sequential）なexact cut-rank-two分離を整理する。
   • 強連結等価分離クラスに対して**標準的なコア（canonical cores）を定義する。アンカー（anchor）の向きを固定することで、これらのコアはCMSO定義可能なラミナー・ファミリー（laminar family）**を形成する。
   • 補助的な部分木（幅の境界を証明するために使用されるもの）と、標準的なラミナー木（転置される対象）との間に重要な区別を設ける。補助的な部分はそれ自体が転置されるのではなく、局所的なピースが一様に有界な線形ランク幅のレイアウトを持つことを証明するためだけに機能する。

2. 有界な局所線形幅:

   • 著者らは、標準的なラミナー分解の局所的なピースのための「修正されたトーソル（corrected torsos）」を構築する。これらのトーソルは、境界ブロックをターミナル・トリプル（ポート頂点）に置き換えることで、$\mathbb{F}_2$ 上の線形代数的演算を通じてカットランクの性質を維持する。
   • Hall–Oxley–Semple–Whittleの枝幅3ディスプレイ定理を用いて、フラワーフリー（flower-free）な成分が、線形ランク幅が最大6の**ポート連続レイアウト（port-contiguous layouts）**を持つことを証明する。
   • これにより、分解の各局所ピースが、有界な線形クリーク幅（具体的には、トーソルにおいて最大6、および局所展開において有界な線形クリーク幅）を持つことが確立される。

3. コヒーレント・フレームと有限状態評価:

   • 論理的評価を可能にするため、境界カットの順序付けられた行基底を選択するためのコヒーレント・フレーム・セレクター（coherent frame selectors）（単項色）を導入する。これにより、隣接する局所ピース間の線形代数的関係が整合的かつ定義可能になることを保証する。
   • 有効なランク2ポートグラフ、およびこれらのグラフのVR合同類を表す有限の状態集合を定義する。
   • ラミナー木上でボトムアップ評価を行う。局所的な展開（子状態の代表元を代入して形成されるもの）は有界な線形クリーク幅を持つため、局所的な遷移はCMSO式によって定義される。これは、有界線形クリーク幅のクラスにおける特性のCMSO定義可能性を保証するBojańczyk, Grohe, Pilipczukの定理に基づいている。

4. 任意のグラフへの持ち上げ:

   • 任意のグラフへの拡張は、標準的なスプリット分解（canonical split decomposition）（Cunningham）を用いて、プライム・グラフから行われる。
   • 著者らは、ファクター・ツリーを扱うために、強化されたスプリット分解（Campbellら）のCMSO転置を用いる。
   • 非プライム・ファクター（クリークおよびスター）については、有界な線形クリーク幅は自明である。プライム・ファクターについては、先に確立されたプライム・ケースの結果が適用される。
   • 連結成分は、成分のルートの状態で構成される有限可換モノイド計算を通じて処理される。これは、モジュロ・カーディナリティ述語を用いてCMSOで表現可能である。

主要な貢献と結果

• 主定理: 本論文は、クラス $\mathcal{C}_2$（ランク幅 $\le 2$ のグラフ）において、言語 $L \subseteq \mathcal{C}_2$ がVR認識可能であることと、CMSO文によって定義可能であることが同値であることを証明する。
• 構造的インターフェース: 本研究は、Clark–Whittleの部分木理論と論理的転置の間の厳密なインターフェースを確立している。フルな部分木自体は転置されないが、標準的なコア・ラミナー木が転置され、それが局所評価を整理するのに十分であることを示している。
• 幅の境界: 著者らは、局所トーソルの線形ランク幅（最大6）および局所展開の線形クリーク幅に関する明示的な境界を提供しており、これらは既存の論理的定義可能性の定理を呼び出すのに十分である。
• 非逐次的カットの処理: 手法は、非逐的なランク2カットをラミナー構造へと整理することに成功しており、ランク幅1のグラフ（ツリーなど）が非有界な線形ランク幅を持ち得るという問題を克服している。

意義と主張
本論文は、有界線形クリーク幅から、最初の非自明な有界ランク幅レベル（スプリット分解のケースを超えて）へと、認識可能性対定義可能性の問題を進展させたと主張している。

• 主張の謙虚さ: 著者らは、この議論が「ランク幅2のグラフは有界な線形クリーク幅を持つ」ことを意味しない（実際には持たない）ことを明示している。むしろ、その意義は、非逐的なランク2カットを、個々のポート・トーソルが一様な線形境界を持つような、定義可能なラミナー・スケルトンへと整理できる点にある。
• 将来の障害: 結論部では、この結果をより高いランク幅へ拡張するための構造的な障害を特定している。それは、より高次のランクの連結関数に対して、連続する境界ブロックを表示するための、より強力なHall–Oxley–Semple–Whittleディスプレイ定理の類似物、あるいは有界な幅の局所トーソルを生み出すための別のメカニズムの必要性である。現在の議論は、そのような置き換えが、有限状態評価の枠組みを変更することなく、理論的に挿入できるような設計となっている。

要約すると、本論文は、プライム・グラフのCMSO転置可能なラミナー分解を構築し、得られるトーソルの一様な局所幅の境界を証明し、スプリット分解を通じて結果を持ち上げることで、ランク幅が2以下のグラフにおいてVR認識可能性とCMSO定義可能性の等価性が成立することを証明している。