Topological Combinatorics

トポロジーの手法を応用して組み合せ論の問題を解く, というのは結構有効な手法である。例えば, 古典的なものとしては, 正多面体の分類に Euler標数を用いる, というものがある。

Topological combinatorics という言葉は, arXiv にある Kozlov の thesis [Koz] のタイトルとして使われている。他に, Matoušek の [Mat03] という Borsuk-Ulamの定理に関する本がある。

Schöneborn と Ziegler の [SZ05] によると, この本で Matoušek は topological combinatorics における most challenging problem の一つは “topological Tverberg conjecture”と言っているらしい。

有名な結果として, Lovász による Borsuk-Ulam の定理を用いた Kneser 予想の証明 [Lov78] がある。これが topological combinatorics の起源であると言われているようであるが, Ziegler は AMS の Notices での解説 [Zie11] で, Birch が [Bir59] で不動点定理を用いたのは, それよりずっと古いことに注意している。

2008年には, Kozlovの“Combinatorial Algebraic Topology” という本 [Koz08] が出版された。Kozlov の本の前半には, この分野, 特に graph の Hom complex を調べるのに現在使われている道具についてまとめられていて便利である。他に topological combinatorics の基礎として使えるものとして, Björner の [Bjö95] や Živaljević の [Živ97] がある。 Björner のは ここから, Živaljević のは ここから download できる。

もちろん, トポロジーの手法やアイデアが応用できる問題は, graph 以外にも数多くある。 最近では, Björner, Goresky, MacPherson [BGM] が, 関数 \(f:\{0,1\}^{n}\to \{0,1\}\) から位相空間 \(X_{f}\) を作り, そのトポロジカルな性質を調べることで \(f\) の circuit complexity の評価を得ることを提案している。彼等自身, 2種類の空間モデルを構成している。

枠組みとして知っておくと良さそうなのは, 以下のことだろう。

• poset のホモトピー論
• small category のホモトピー論
• graph のホモトピー論
• combinatorial groupoid
• discrete Morse theory

組み合せ論というと, 離散的な構造を想像するが, topological combinatorics の手法は, より幅広いものも扱える。例えば, Živaljević [Živ] は, poset, convex polytope, oriented matroid, subspace arrangement などの continuous版を考えている。

逆に, 幾何学的対象を離散化して調べるということも考えられている。 例えば, discrete Morse theory を smooth Morse theory の近似として使うことは, Gallais [Gal10] や Benedetti [Ben16] などが考えている。Forman は Ricci curvature の離散版を [For03] で定義している。

• Forman-Ricci curvature

Forman-Ricci curvature では Gauss-Bonnet の定理が成り立たないが, Gauss-Bonnet の定理が成り立つような cell complex 上の Ricci curvature を Watanabe が [Wat19] で定義している。

一方, Lin, Lu, Yau [LLY11] によると, Ricci curvature の graph 版を最初に定義したのは, Chung と Yau [CY96] らしい。 その後 Lin と Yau は [LY10] で一般化を行なっている。 Lin, Lu, Yau の論文のものは Watanabe と Yamada の [WY20]では, LLY-Ricci curvatureと呼ばれている。

• LLY-Ricci curvature

Watanabe と Yamada の [WY20]では Watanabe の Ricci curvature と LLY-Ricci curvature の比較が行なわれている。

References

[Ben16]

Bruno Benedetti. “Smoothing discrete Morse theory”. In: Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 16.2 (2016), pp. 335–368. arXiv: 1212. 0885.

[BGM]

Anders Björner, Mark Goresky, and Robert MacPherson. Topological aspects of Boolean functions. arXiv: 2205.14424.

[Bir59]

B. J. Birch. “On \(3N\) points in a plane”. In: Proc. Cambridge Philos. Soc. 55 (1959), pp. 289–293. url: https://doi.org/10.1017/s0305004100034071.

[Bjö95]

A. Björner. “Topological methods”. In: Handbook of combinatorics, Vol. 1, 2. Amsterdam: Elsevier, 1995, pp. 1819–1872.

[CY96]

F. R. K. Chung and S.-T. Yau. “Logarithmic Harnack inequalities”. In: Math. Res. Lett. 3.6 (1996), pp. 793–812.

[For03]

Robin Forman. “Bochner’s method for cell complexes and combinatorial Ricci curvature”. In: Discrete Comput. Geom. 29.3 (2003), pp. 323–374. url: http://dx.doi.org/10.1007/s00454-002-0743-x.

[Gal10]

Étienne Gallais. “Combinatorial realization of the Thom-Smale complex via discrete Morse theory”. In: Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 9.2 (2010), pp. 229–252. arXiv: 0803.2616.

[Koz]

Dmitry N. Kozlov. Trends in Topological Combinatorics. arXiv: math/ 0507390.

[Koz08]

Dmitry Kozlov. Combinatorial algebraic topology. Vol. 21. Algorithms and Computation in Mathematics. Berlin: Springer, 2008, pp. xx+389. isbn: 978-3-540-71961-8. url: https://doi.org/10.1007/978-3-540-71962-5.

[LLY11]

Yong Lin, Linyuan Lu, and Shing-Tung Yau. “Ricci curvature of graphs”. In: Tohoku Math. J. (2) 63.4 (2011), pp. 605–627. url: http://dx.doi.org/10.2748/tmj/1325886283.

[Lov78]

L. Lovász. “Kneser’s conjecture, chromatic number, and homotopy”. In: J. Combin. Theory Ser. A 25.3 (1978), pp. 319–324. url: http://dx.doi.org/10.1016/0097-3165(78)90022-5.

[LY10]

Yong Lin and Shing-Tung Yau. “Ricci curvature and eigenvalue estimate on locally finite graphs”. In: Math. Res. Lett. 17.2 (2010), pp. 343–356. url: https://doi.org/10.4310/MRL.2010.v17.n2.a13.

[Mat03]

Jiří Matoušek. Using the Borsuk-Ulam theorem. Universitext. Lectures on topological methods in combinatorics and geometry, Written in cooperation with Anders Björner and Günter M. Ziegler. Berlin: Springer-Verlag, 2003, pp. xii+196. isbn: 3-540-00362-2.

[SZ05]

Torsten Schöneborn and Günter M. Ziegler. “The topological Tverberg theorem and winding numbers”. In: J. Combin. Theory Ser. A 112.1 (2005), pp. 82–104. arXiv: math / 0409081. url: http://dx.doi.org/10.1016/j.jcta.2005.01.005.

[Wat19]

Kazuyoshi Watanabe. “Combinatorial Ricci curvature on cell-complex and Gauss-Bonnnet theorem”. In: Tohoku Math. J. (2) 71.4 (2019), pp. 533–547. arXiv: 1703.08409. url: https://doi.org/10.2748/tmj/1576724792.

[WY20]

Kazuyoshi Watanabe and Taiki Yamada. “Relation between combinatorial Ricci curvature and Lin-Lu-Yau’s Ricci curvature on cell complexes”. In: Tokyo J. Math. 43.1 (2020), pp. 25–45. arXiv: 1801.05593. url: https://doi.org/10.3836/tjm/1502179293.

[Zie11]

Günter M. Ziegler. “3N colored points in a plane”. In: Notices Amer. Math. Soc. 58.4 (2011), pp. 550–557.

[Živ]

Rade T. Živaljević. A glimpse into continuous combinatorics of posets, polytopes, and matroids. arXiv: 1603.08175.

[Živ97]

Rade T. Živaljević. “Topological methods”. In: Handbook of discrete and computational geometry. CRC Press Ser. Discrete Math. Appl. Boca Raton, FL: CRC, 1997, pp. 209–224.