そうとは限らないだろ。
この記事では様々な定理の組合せ論的証明について扱っていきます。内容は随時アップデートしていく予定です。
Brouwer の不動点定理 #
Brouwer の不動点定理は位相幾何学の定理です。この定理を組合せ論の Sperner の補題を用いて証明することができます。以下の記事をご覧ください。
【月刊組合せ論 Natori】Brouwer の不動点定理と Sperner の補題【2025 年 11 月号】
この記事では触れていませんが、HEX の定理からも Brouwer の不動点定理を証明することができます。以下の記事が面白いのでご覧ください。
Borsuk-Ulam の定理 #
Borsuk-Ulam の定理も位相幾何学の定理であり、組合せ論の Tucker の補題から証明できます。いつか記事にしたいです。以下の文献を読むとよいです。
- Matoušek, Jiří. Using the Borsuk-Ulam theorem. Universitext. Berlin: Springer. xii, 214 p. (2008).
ハムサンドイッチの定理 #
ハムサンドイッチの定理とは、 次元空間にある 個の立体はある超平面で同時に二等分できるといった定理です。
通常、二等分という概念はルベーグ測度などを用いて定式化されるので、あまり組合せ論とのつながりはありません。しかし、次のような有限集合バージョンがあります。
ハムサンドイッチの定理およびこの有限集合版はともに Borsuk-Ulam の定理から証明できます。
有限集合版は Tucker の補題から直接証明できるかもしれません。
ネックレス分割問題 #
ネックレス分割問題には
- 離散版
- 連続版
があり、離散版の証明は連続版を経由するものしか見つかっていないそうです。
「すべての定理は組合せ論的に証明すべきである」という考えのもとでは離散版を直接証明したくなりますが、そう甘くはないのでしょう。
いずれ記事にする予定です。
Kostka-Foulkes 多項式 #
対称多項式である Hall-Littlewood 多項式と Schur 多項式の関係を表しているのが Kostka-Foulkes 多項式です。以下の記事をご覧ください。
【月刊組合せ論 Natori】Hall-Littlewood 多項式と Kostka-Foulkes 多項式【2023 年 6 月号】
Kostka-Foulkes 多項式の係数は非負整数です。組合せ論的な証明としては charge を用いるものが知られています。
Kostka-Foulkes 多項式は A 型以外のルート系でも定義でき、この場合にも係数が非負整数であることが知られていますが、組合せ論的な証明は特殊な場合にしか知られていません。
Riemann の写像定理 #
Riemann の写像定理は複素解析における定理です。組合せ論とは無縁な雰囲気がありますが、実はサークルパッキングを用いた証明が知られているそうです。
いつか勉強して記事を書こうと思います。
その他 #
ちょっと聞いたことがある程度のものを並べておきます。
- Howe 双対性：RSK 対応で説明できるそうです。
- Riemann-Roch の定理：グラフ理論版が知られているそうです。
- Milnor 予想：Rasmussen の不変量を用いた組合せ論的証明が知られているそうです。
- グリッドダイアグラム：結び目理論をグリッドダイアグラムを用いて調べる研究があるそうです。
他にもこの定理が組合せ論的に証明できるといったことをご存じであれば、ぜひご連絡ください。