無限グラフ

組み合せ論の研究対象としての グラフは, 普通は有限グラフであるが, 無限グラフも数学の様々な分野で登場する。 例えば, 自由群の 分類空間として \(S^1\) の wegde が取れるが, その universal cover は無限の tree である。

このような無限の場合を扱うために, Diestel [Die] は, 位相空間論的な手法を提案している。Diestel と Sprüssel [DS11] は, 無限グラフのための ホモロジー論を構成している。

一方, 何かしら測る方法があればよい, という視点から, 測度論な手法も考えられている。 頂点集合に測度が定義された無限グラフは, Lenz と Pogorzelski と Schmidt の [LPS19] で measure graph と呼ばれている。 彼等は, Ihara zeta function の拡張を定義している。

• measure graph

頂点集合 \(V\) が standard Borel space, つまり Polish space に同伴した measurable space である simple graph で, 辺の集合が \(V\times V\) の Borel subset であるものは, Borel graph と呼ばれている。

• Borel graph

Bernshteyn [Ber19] は, Kechris と Marks の [KM] を参照している。

確率論的に考えるためには, グラフの極限という概念も必要になる。 有限グラフの極限について議論しているのは, Lovász と Szegedy の [LS06] である。 彼等によると, 有限グラフの列の “limit object” は symmetric measurable function \([0,1]^2\to [0,1]\) で表現されるらしい。 このようなものは graphon (graph function) と呼ばれている。 また [LS] では, compact空間で decorate された graph の limit を考えている。

• graphon

graphon については, Glasscock の “What is \(\ldots \)” の記事 [Gla15] がある。

有限グラフの列としては, expander というものもある。トポロジー関係では, geometric group theory などで登場する。

• expander

Borodin と Olshanski の [BO12] にあるように, 無限対称群や無限次ユニタリ群の表現論でも, 無限グラフが使われる。Kerov と Okounkov と Olshanski の [KOO98] で使われているのは, 無限対称群に対する Young graph で Borodin と Olshanski が調べているのは, ユニタリ群に対する Gel\('\)fand-Tsetlin graph である。

• Young graph
• Gel\('\)fand-Tsetlin graph

References

[Ber19]

Anton Bernshteyn. “Measurable versions of the Lovász local lemma and measurable graph colorings”. In: Adv. Math. 353 (2019), pp. 153–223. arXiv: 1604.07349. url: https://doi.org/10.1016/j.aim.2019.06.031.

[BO12]

Alexei Borodin and Grigori Olshanski. “The boundary of the Gelfand-Tsetlin graph: a new approach”. In: Adv. Math. 230.4-6 (2012), pp. 1738–1779. arXiv: 1109.1412. url: https://doi.org/10.1016/j.aim.2012.04.005.

[Die]

Reinhard Diestel. Locally finite graphs with ends: a topological approach. arXiv: 0912.4213.

[DS11]

Reinhard Diestel and Philipp Sprüssel. “On the homology of locally compact spaces with ends”. In: Topology Appl. 158.13 (2011), pp. 1626–1639. arXiv: 0910.5650. url: https://doi.org/10.1016/j.topol.2011.05.031.

[Gla15]

Daniel Glasscock. “What is …a graphon?” In: Notices Amer. Math. Soc. 62.1 (2015), pp. 46–48. arXiv: 1611.00718.

[KM]

Alexander S. Kechris and Andrew S. Marks. Descriptive Graph Combinatorics. url: https://math.berkeley.edu/~marks/papers/combinatorics20book.pdf.

[KOO98]

Sergei Kerov, Andrei Okounkov, and Grigori Olshanski. “The boundary of the Young graph with Jack edge multiplicities”. In: Internat. Math. Res. Notices 4 (1998), pp. 173–199. arXiv: q-alg/9703037. url: http://dx.doi.org/10.1155/S1073792898000154.

[LPS19]

Daniel Lenz, Felix Pogorzelski, and Marcel Schmidt. “The Ihara zeta function for infinite graphs”. In: Trans. Amer. Math. Soc. 371.8 (2019), pp. 5687–5729. arXiv: 1408.3522. url: https://doi.org/10.1090/tran/7508.

[LS]

László Lovász and Balázs Szegedy. Limits of compact decorated graphs. arXiv: 1010.5155.

[LS06]

László Lovász and Balázs Szegedy. “Limits of dense graph sequences”. In: J. Combin. Theory Ser. B 96.6 (2006), pp. 933–957. arXiv: math/0408173. url: http://dx.doi.org/10.1016/j.jctb.2006.05.002.