Independence Complex

グラフの頂点の部分集合で, そのいづれも辺で結ばれていないものを集めてくると, abstract simplicial complex ができる。 これを, そのグラフの independence complex と呼ぶ。

Independence complex は, グラフを扱う様々な場面で登場する。 誰が最初に考えたのかよく分からないが, 例えば Kozlov の [Koz04] に定義がある。

Independence complex のホモトピー型についても様々な人が調べている。 Adamaszek と Barmak は [AB11] でその connectivity の lower bound について調べている。Ehrenborg と Hetyei [EH06] は, より一般の indepencence complex を定義し, そのホモトピー型について調べている。

Adamaszek [Ada12] は, 頂点を取り除く操作に関係した cofiber sequence を構成し, それを用いて cycle の巾の場合などが wedge和に split することを示している。Adamaszek は, [Ada14] で rational homology についても考えている。

具体的なグラフの independence complex についても, もちろん, 色々調べられている。Grid graph の場合は, Bousquet-Mélou と Linusson と Nevo の [BLN08] や Thapper の [Tha] などで調べられている。 統計力学の問題とも関係しているらしい。 Braun [Bra] は, stable Kneser graph の場合を調べている。

Engström [Eng] によると, independence complex の total Betti number は “intriguing graph invariant” らしい。そこには independence complex の total Betti number を調べた文献が色々挙げられている。

• independence complex の total Betti number

グラフの頂点の independence は, matroid のアイデアの基本であることも知っておくべきだろう。

Coxeter group に対しては, Coxeter graph があるが, その independence complex に関係した chain complex を Larsen と Lindenstrauss [LL] が定義している。

References

[AB11]

Michał Adamaszek and Jonathan Ariel Barmak. “On a lower bound for the connectivity of the independence complex of a graph”. In: Discrete Math. 311.21 (2011), pp. 2566–2569. url: https://doi.org/10.1016/j.disc.2011.06.010.

[Ada12]

Michał Adamaszek. “Splittings of independence complexes and the powers of cycles”. In: J. Combin. Theory Ser. A 119.5 (2012), pp. 1031–1047. arXiv: 1106.6250. url: https://doi.org/10.1016/j.jcta.2012.01.009.

[Ada14]

Michał Adamaszek. “Extremal problems related to Betti numbers of flag complexes”. In: Discrete Appl. Math. 173 (2014), pp. 8–15. arXiv: 1109.4775. url: https://doi.org/10.1016/j.dam.2014.04.006.

[BLN08]

Mireille Bousquet-Mélou, Svante Linusson, and Eran Nevo. “On the independence complex of square grids”. In: J. Algebraic Combin. 27.4 (2008), pp. 423–450. arXiv: math/0701890. url: http://dx.doi.org/10.1007/s10801-007-0096-x.

[Bra]

Benjamin Braun. Independence Complexes of Stable Kneser Graphs. arXiv: 0912.0720.

[EH06]

Richard Ehrenborg and Gábor Hetyei. “The topology of the independence complex”. In: European J. Combin. 27.6 (2006), pp. 906–923. url: http://dx.doi.org/10.1016/j.ejc.2005.04.010.

[Eng]

Alexander Engström. Graph colouring and the total Betti number. arXiv: 1412.8460.

[Koz04]

Dmitry N. Kozlov. “Directed trees in a string, real polynomials with triple roots, and chain mails”. In: Discrete Comput. Geom. 32.3 (2004), pp. 373–382. arXiv: math/0210045. url: http://dx.doi.org/10.1007/s00454-004-2906-4.

[LL]

Michael Larsen and Ayelet Lindenstrauss. Coxeter Cochain Complexes. arXiv: 1210.7254.

[Tha]

Johan Thapper. Independence Complexes of Cylinders Constructed from Square and Hexagonal Grid Graphs. arXiv: 0812.1165.