Three Combinatorial Algorithms for the Cave Polynomial of a Polymatroid

技術要約：ポリマトロイドのケイブ多項式に関する3つの組合せ論的アルゴリズム

問題提起
本論文は、ポリマトロイドのケイブ多項式（cave polynomial）の計算および組合せ論的な理解について扱う。この多項式は、ホモロジー的シフトイデアルやポリマトロイドのメビウス・サポートの研究において導入された比較的新しい対象である。ケイブ多項式が、ホモロジー的シフトイデアルやポリマトロイドのメビウス・サポートに関する重要な予想を解決することが以前に示されていたが、既存の他の既知の多項式形式との等価性の証明は、代数幾何学や多重度自由多様体の理論に基づく深いメカニズムに大きく依存していた。具体的には、先行研究では、ケイブ多項式がスタラクタイト多項式（stalactite polynomial）、ボックス多項式（box polynomial）、およびメビウス多項式（Möbius polynomial）と等しいことが示されていたが、これらの等価性は、直接的な組合せ論的推論ではなく、代数的退化の議論（例：双対ポリマトロイド的イデアルによって定義される多様体への平坦退化）を通じて証明されていた。本研究の中心的な課題は、実現可能なポリマトロイドに限定されることなく、任意のポリマロットに対してこれら3つの異なる公式の等価性を、直接的な組合せ論的推論を用いて明示的に証明することである。

手法
著者は、ポリマトロイドの構造的特性、特に$M$-凸性（$M$-convexity）およびそれに関連する独立集合多面体と基底多面体を利用した、純粋に組合せ論的なアプローチを採用している。その手法は以下の通りである：

1. 組合せ論的構造の定義： 本論文は、「ケイブ（cave）」と「スタラクタイト（stalactite）」に基づくケイブ多項式、特定の点を含むスタラクタイトを数えるスタラクタイト多項式、独立集合多面体上の離散微分による和であるボックス多項式、およびポリマトロイドから導かれるポセットのメビウス関数に基づくメビウス多項式の定義を定式化する。
2. ポセット解析： ポセット $P$ を、独立集合多面体 $I(P) \cap \mathbb{N}^p$ の要素に極大元 $\hat{1}$ を加えたものとして構成する。著者は、このポセットのメビウス関数 $\mu_P$ を調査する。
3. 帰納的証明： ポセット内の区間の長さに関する帰納法を用いて、メビウス関数の明示的な公式を導出する。
4. 切断（Truncation）の議論： スタラクタイトの局所的な性質をポリマトロイドの全体的な構造に関連付けるために、ポリマトロイドの点 $n$ における「切断」の概念を利用し、スタラクタイト多項式とメビウス多項式の係数を比較する。

主要な貢献および結果
本論文は、異なる公式間の組合せ論的な関係を示す3つの主要な定理を確立している：

1. 明示的なメビウス関数公式（定理 1.6 / 定理 3.1）： 著者は、ポリマトロイドに関連するポセットのメビウス関数 $\mu_P(m, n)$ の明示的な公式を導出した。その結果、もし $m = n - e_{i_1} - \dots - e_{i_j}$ （ただし $i_1, \dots, i_j$ は相異なるインデックス）であれば $\mu_P(m, n) = (-1)^j$ となり、それ以外の場合は $0$ となることを示している。この公式により、メビウス多項式の係数を直接計算することが可能となる。

2. ボックス多項式とメビウス多項式の等価性（定理 3.3）： ボックス多項式（$t_i^{n_i} - t_i^{n_i-1}$ のような項の積を含む）の係数を導出されたメビウス関数と比較することにより、本論文は $Box_P(t) = M\ddot{o}b_P(t)$ であることを証明している。これは、ボックス多項式の単項式の係数が、ポセットにおける関連する区間上のメビウス値の和に正確に対応することを示すことで達成される。

3. スタラクタイト計数の漸化式（定理 1.7 / 定理 4.3）： 点 $n$ を含むスタラクタイトの符号付き個数 $c'_n(P)$ が、メビウス関数 $\mu_P(n)$ と同一の漸化式を満たすことを示している。具体的には、$n$ が基底多面体に含まれる場合は $c'_n(P) = 1$、$n$ が独立集合多面体の外にある場合は $0$、それ以外の場合は$1 - \sum_{m>n} c'_m(P)$となる。これにより、$Stal_P(t) = M\ddot{o}b_P(t)$ であることが証明される。

結論
これらの結果を組み合わせることで、本論文は、任意のポリマトロイド $P$ に対して以下が成立することを述べる定理 1.5を証明している：
$$cave_P(t) = Stal_P(t) = Box_P(t) = M\ddot{o}b_P(t)$$
この等式は、実現可能なものに限らず、任意のポリマトロイドに対して成立する。

意義
本研究の意義は、定理 1.5 の証明を「組合せ論化」した点にある。代数幾何学的な議論（ジェネリック初期イデアル、平坦退化、および多重度自由多様体のヒルベルト多項式など）を、ポセット論と $M$-凸性を用いた直接的な組合せ論的証明に置き換えることで、本論文はケイブ多項式を理解するための自己完結的な枠組みを提供している。さらに、メビウス関数の明示的な公式とスタラクタイト計数の漸化式は、新たな計算ツールを提供する。応用として、本論文は、マトロイドのスナッパー多項式（ポリマトロイドに制限されたもの）を、単項式を二項式の積へ送る写像を通じて、これら3つの等価な公式の観点から解釈している。