グラフの不変量

グラフからは, 様々なものが定義される。 それらは全て, 広い意味でのグラフの不変量と考えることができる。 もちろん, 彩色数 (chromatic number) のようにグラフに数を対応させるのが基本的な不変量であるが。

• numerical graph invariants

グラフの不変量というより, グラフのデータそのものであるが, グラフに関する基本的な概念としては, まず adjacency matrix がある。 どの頂点とどの頂点が辺で結ばれているかを, 行列で表わすものである。

• adjacency matrix

グラフの頂点の色付けについて, chromatic polynomial という多項式を考えることもできる。 結び目の研究のように, 様々な多項式による不変量も定義されている。

• グラフの多項式不変量

色付けに関連した別の系統の「不変量」として, Lovász [Lov78] により導入された “graphの間の準同型の成すpolyhedral complex” \(\Hom (G,H)\) も重要である。他にもグラフに対し, 単体的複体などの幾何学的対象を対応させる構成は, 色々知られている。

• 幾何学的なグラフの不変量

幾何学的対象があると, それらの(コ)ホモロジーを取ることで, グラフの(コ)ホモロジー論が得られる。 グラフの多項式不変量の categorification として, 幾何学的対象を経由せずに定義されるホモロジーもある。 他にも以下のようなものがある。

• Baldridge [Bal] による planar trivalent graph の bigraded cohomology
• Talbi と Benayat [TB14] による reflexive graph の homology
• Caputi, Celoria, Collari [CCC] の monotone cohomology
• quiver の各種ホモロジー論

Caputi らの monotone cohomology は, 辺を取り除くことで閉じている “monotone property” を指定することで定義される。 Chromamtic polynomial の categorification や quiver の multipath cohomology などを統一して扱えるものである。

グラフ準同型に関しては, Engström と Noren [EN13] が, グラフ準同型で index された多項式環の中のある ideal を考えることを提唱している。 Algebraic statistics などと関係あるらしい。

グラフ準同型を確率論的に考えると, subgraph density という不変量が得られる。

• subgraph density

Lovasz と Szegedy の [LS11] によると, それによりグラフの列を考える際には graphon という \([0,1]\times [0,1]\) 上の関数が, グラフの列の一般化として考えられる。

グラフに対しては, zeta関数を定義することもできる。

• グラフの zeta関数

グラフから様々な群を作ることができる。 これらもグラフの不変量と言って良いだろう。

• グラフから構成される群

グラフのデータから作られた環もいくつかある。例えば, Clifford algebra を作っているのは Khovanova [Kho10] である。Layered graph から splitting algebra という algebra が定義される。 その Koszul 性についても調べられている。Retakh らの [RSW10] など。

• splitting algebra

Retakh らは, regular cell complex の face poset の Hasse diagram として得られる graph について, 特に考えている。

Quiver からできる algebra は色々ある。

• quiver から定義される各種 algebra

グラフからは, \(C^*\)-algebra を作ることもできる。

• グラフ の \(C^*\)-algebra

グラフ や quiver から semigroup を作る方法もある。

• グラフの phylogenetic semigroup (Buczyńska, Buczyński, Kubjas, Michalekの [Buc+13; Kub15])
• quiver の transformation semigroup (East, Gadouleau, Mitchellの [EGM19])

References

[Bal]

Scott Baldridge. A Cohomology Theory for Planar Trivalent Graphs with Perfect Matchings. arXiv: 1810.07302.

[Buc+13]

Weronika Buczyńska, Jarosław Buczyński, Kaie Kubjas, and Mateusz Michałek. “On the graph labellings arising from phylogenetics”. In: Cent. Eur. J. Math. 11.9 (2013), pp. 1577–1592. arXiv: 1105 . 5382. url: https://doi.org/10.2478/s11533-013-0263-3.

[CCC]

Luigi Caputi, Daniele Celoria, and Carlo Collari. Monotone cohomologies and oriented matchings. arXiv: 2203.03476.

[EGM19]

James East, Maximilien Gadouleau, and James D. Mitchell. “Structural aspects of semigroups based on digraphs”. In: Algebr. Comb. 2.5 (2019), pp. 711–733. arXiv: 1704 . 00937. url: https://doi.org/10.5802/alco.56.

[EN13]

Alexander Engström and Patrik Norén. “Ideals of Graph Homomorphisms”. In: Ann. Comb. 17.1 (2013), pp. 71–103. arXiv: 1002.4679. url: http://dx.doi.org/10.1007/s00026-012-0169-y.

[Kho10]

Tanya Khovanova. “Clifford algebras and graphs”. In: Geombinatorics 20.2 (2010), pp. 56–76. arXiv: 0810.3322.

[Kub15]

Kaie Kubjas. “Low degree minimal generators of phylogenetic semigroups”. In: Eur. J. Math. 1.1 (2015), pp. 2–24. arXiv: 1304. 0744. url: https://doi.org/10.1007/s40879-014-0011-7.

[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.

[LS11]

L. Lovász and B. Szegedy. “Finitely forcible graphons”. In: J. Combin. Theory Ser. B 101.5 (2011), pp. 269–301. arXiv: 0901. 0929. url: http://dx.doi.org/10.1016/j.jctb.2011.03.005.

[RSW10]

Vladimir Retakh, Shirlei Serconek, and Robert Lee Wilson. “Koszulity of splitting algebras associated with cell complexes”. In: J. Algebra 323.4 (2010), pp. 983–999. arXiv: 0810.1241. url: https://doi.org/10.1016/j.jalgebra.2009.11.039.

[TB14]

Mohamed Elamine Talbi and Djilali Benayat. “Homology theory of graphs”. In: Mediterr. J. Math. 11.2 (2014), pp. 813–828. url: https://doi.org/10.1007/s00009-013-0358-x.