位相的組合せ論

位相的組合せ論という数学の分野は、組合せ論における問題を解決するために位相的および代数的位相的手法を応用するものです。

歴史

組合せ位相幾何学の分野では位相幾何学における組合せ概念が使用され、20 世紀初頭には代数位相幾何学の分野へと発展しました。

1978年、状況は逆転しました。代数位相幾何学の手法が組合せ論の問題を解くために用いられたのです。ラースロー・ロヴァースがクネザー予想を証明し、位相組合せ論という新しい分野が幕を開けました。ロヴァースの証明にはボルスク＝ウラム定理が用いられ、この定理はこの新しい分野において今もなお重要な役割を果たしています。この定理には多くの等価版や類似版があり、公平な分割問題の研究に用いられてきました。

ホモロジー的手法をグラフ理論に応用した別の事例として、ロヴァースは、アンドラーシュ・フランクの予想の無向バージョンと有向バージョンの両方を証明しました。k連結グラフG、k点、および合計がとなるk個の正の整数が与えられたとき、、、およびが連結サブグラフを張るようなの分割が存在する。 $v_{1},\ldots ,v_{k}\in V(G)$ $n_{1},n_{2},\ldots ,n_{k}$ $|V(G)|$ $\{V_{1},\ldots ,V_{k}\}$ $V(G)$ $v_{i}\in V_{i}$ $|V_{i}|=n_{i}$ $V_{i}$

1987年、ノーガ・アロンはボルスク＝ウラム定理を用いてネックレス分割問題を解いた。この定理は、線形決定木アルゴリズムにおける計算量問題やアンデラー＝カープ＝ローゼンベルグ予想の研究にも用いられてきた。その他の分野としては、半順序集合の位相幾何学やブルハット順序などが挙げられる。

さらに、微分位相幾何学の手法には、離散モース理論における組み合わせ論的類似物が存在する。

参照

参考文献

de Longueville, Mark (2004)、「25 years proof of the Kneser conjecture - The advent of topological combinatorics」（PDF）EMS Newsletter、サウサンプトン、ハンプシャー：ヨーロッパ数学協会、pp. 16– 19 、2008年7月29日閲覧。

さらに読む

ビョルナー、アンダース(1995)、「位相的手法」、グラハム、ロナルド L. ;マーティン・グレッシェル; Lovász、László (編)、Handbook of Combinatorics (PDF)、vol. 2、MIT プレス、ISBN 978-0-262-07171-0。
Kozlov, Dmitry (2005), Trends in topological combinatorics , arXiv : math.AT/0507390 , Bibcode :2005math......7390K。
コズロフ、ドミトリー（2007）、組合せ代数的位相幾何学、シュプリンガー、ISBN 978-3-540-71961-8。
Lange, Carsten (2005), 組合せ曲率、群作用、および着色：位相的組合せ論の側面(PDF)、ベルリン工科大学博士論文。
Matoušek, Jiří (2003), 「Borsuk-Ulam定理の使用：組合せ論と幾何学における位相的手法の講義」、Springer、ISBN 978-3-540-00362-5。
バーマク、ジョナサン（2011）、有限位相空間の代数的位相学とその応用、シュプリンガー、ISBN 978-3-642-22002-9。
de Longueville, Mark (2011), A Course in Topological Combinatorics , Springer, ISBN 978-1-4419-7909-4。