様々な組み合せ論的構造

私が組み合せ論的構造に興味を持ったのは, hyperplane arrangement の Salvetti complex の構成がきっかけだったが, 他にも, 組み合せ論的データから, 色んな simplicial complex が構成できるので, 代数的トポロジーの道具を使って調べることができる。

例えば, グラフからは, 様々な方法で simplicial complex が構成されている。

• グラフからできる simplicial complex

また, poset により表される構造も多いが, poset からは order complex として simplicial complex が得られる。

• order complex

このように, simplicial complex のような, 直接代数的トポロジーの道具を使えるもの以外にも, 様々な組み合せ論的構造がある。

古いものとしては, ループ空間の構造を表す associahedron や permutahedron などのような凸多面体がある。

• associahedron
• permutohedron

その permutohedron と関係あるもので semigraphoid というものがある。 “Statistical learning theory” に現れる組み合せ的構造らしいが, Hemmecke と Morton と Shiu と Sturmfels と Wienand の [Hem+08] によると, braid arrangement や permutohedron とも関係あるようである。

• semigraphoid

それらの関係の元になっているのは [Mor+] で調べられた semigraphoid の geometric characterization である。

古典的な幾何学との関連では, incidence geometry という構造がある。 Euclid流の幾何学は, 点や直線などを定義せず, それらの間の関係だけを考えたものとみなすことができるが, それを抽象化したものである。

• incidence geometry

有限集合の部分集合族である性質を持つものを (combinatorial) design といい, これも組み合せ論の主要な研究対象である。

• design

References

[Hem+08]

Raymond Hemmecke, Jason Morton, Anne Shiu, Bernd Sturmfels, and Oliver Wienand. “Three counter-examples on semi-graphoids”. In: Combin. Probab. Comput. 17.2 (2008), pp. 239–257. arXiv: math/0610451. url: https://doi.org/10.1017/S0963548307008838.

[Mor+]

Jason Morton, Lior Pachter, Anne Shiu, Bernd Sturmfels, and Oliver Wienand. Geometry of rank tests. arXiv: math/0605173.