グラフの基本

組み合せ論の研究対象としての グラフについて, 何が重要なのかは良く知らない。 教科書としては何がよいのだろうか。 グラフの zeta 関数について書かれた本の草稿が A. Terras の website から download できるが, そこでは次の本が挙げられている: Biggs の [Big74], Bollobas の [Bol98], Chung の [Chu97], Cvetkovic, Doob, Sachs の [CDS95]。PDFファイルを入手できる本としては, Diestel の [Die10] がある。 専用のサイトから download できるようになっている。

ここでは, グラフの定義やグラフの間の写像, つまりグラフの圏に関することをまとめた。

まずはグラフの定義であるが, 頂点の集合と辺の集合という二つの集合を用いるのが普通だろう。 私は, 2つの集合 \(\Gamma _{0}\) と \(\Gamma _{1}\) と写像 \[ v: \Gamma _{1} \rarrow {} \Gamma _{0}\times \Gamma _{2}/\Sigma _{2} \] の3つ組 \(\Gamma =(\Gamma _{0},\Gamma _{1},v)\) と定義するのが良いと思う。 ここで, \(\Sigma _{2}\) は2次の対称群であり, \(\Gamma _{0}\times \Gamma _{0}\) に座標に入れ替えで作用する。 \(\Gamma _{0}\) が頂点の集合, \(\Gamma _{1}\) が辺の集合, そして \(v\) が辺に対してその両端の頂点を対応させる写像である。 このように考えると, quiver (directed graph) との対応を付け易い。

Getzler と Kapranov の [GK98] では, 頂点と half-edge による定義が用いられていて面白い。 これは Kontsevich と Manin [KM94] に依るもののようである。 Kock [Koc18] によると Kontsevich と Manin の定義の欠点は, 構造を保つ写像として graph の morphism を定義すると, 必要以上に多くの情報を保存してしまうことである。 そこで, Borison と Manin [BM96; BM08] により定義された morphism を使うのが普通のようである。

• Borisov-Manin category of graphs

Kock は Joyal と共に [JK] で別の half-edge を用いた定義を導入している。

• Kock-Joyal category of graphs

もちろん, 通常の頂点集合と辺集合によるグラフの定義でも, グラフの 圏を考えることもできる。 例えば, Igusa と Klein と Williams の [IKW] などで使われている。

• グラフの間の collapsing morphism
• rank \(n\) のグラフの圏 \(\mathcal {G}(n)\)の分類空間は rank \(n\)の free group の outer automorphism group の分類空間とホモトピー同値である。 [CV86]

また Lovász [Lov78]により導入された “graph の間の準同型の成す polyhedral complex”, すなわち Hom complex は, Kozlov ら [BK06; BK07; Koz08] を中心に研究されている。Kozlov の survey [Koz07]が詳しい。その主題は graph の chromatic number であるが。

• グラフの Hom complex

グラフの圏では被覆空間も定義でき, 位相空間の被覆空間の理論と同様のことが成り立つようである。 Deick と Pask と Raeburn の [DPR] など。 Pask と Raeburn は, Quigg と共に [PQR05] でその \(k\)-graph に関する類似を考えている。

• グラフの被覆空間

組み合せ論では主に有限グラフが考えられている ようであるが, 無限グラフを調べる方法も色々考えられているようである。

• 無限グラフ

References

[Big74]

Norman Biggs. Algebraic graph theory. Cambridge Tracts in Mathematics, No. 67. London: Cambridge University Press, 1974, pp. vii+170.

[BK06]

Eric Babson and Dmitry N. Kozlov. “Complexes of graph homomorphisms”. In: Israel J. Math. 152 (2006), pp. 285–312. arXiv: math/0310056. url: http://dx.doi.org/10.1007/BF02771988.

[BK07]

Eric Babson and Dmitry N. Kozlov. “Proof of the Lovász conjecture”. In: Ann. of Math. (2) 165.3 (2007), pp. 965–1007. arXiv: math/0402395. url: http://dx.doi.org/10.4007/annals.2007.165.965.

[BM08]

Dennis V. Borisov and Yuri I. Manin. “Generalized operads and their inner cohomomorphisms”. In: Geometry and dynamics of groups and spaces. Vol. 265. Progr. Math. Basel: Birkhäuser, 2008, pp. 247–308. arXiv: math/0609748. url: http://dx.doi.org/10.1007/978-3-7643-8608-5_4.

[BM96]

K. Behrend and Yu. Manin. “Stacks of stable maps and Gromov-Witten invariants”. In: Duke Math. J. 85.1 (1996), pp. 1–60. arXiv: alg-geom/9506023. url: http://dx.doi.org/10.1215/S0012-7094-96-08501-4.

[Bol98]

Béla Bollobás. Modern graph theory. Vol. 184. Graduate Texts in Mathematics. New York: Springer-Verlag, 1998, pp. xiv+394. isbn: 0-387-98488-7. url: http://dx.doi.org/10.1007/978-1-4612-0619-4.

[CDS95]

Dragoš M. Cvetković, Michael Doob, and Horst Sachs. Spectra of graphs. Third. Theory and applications. Johann Ambrosius Barth, Heidelberg, 1995, pp. ii+447. isbn: 3-335-00407-8.

[Chu97]

Fan R. K. Chung. Spectral graph theory. Vol. 92. CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997, pp. xii+207. isbn: 0-8218-0315-8.

[CV86]

Marc Culler and Karen Vogtmann. “Moduli of graphs and automorphisms of free groups”. In: Invent. Math. 84.1 (1986), pp. 91–119. url: http://dx.doi.org/10.1007/BF01388734.

[Die10]

Reinhard Diestel. Graph theory. Fourth. Vol. 173. Graduate Texts in Mathematics. Springer, Heidelberg, 2010, pp. xviii+437. isbn: 978-3-642-14278-9. url: http://dx.doi.org/10.1007/978-3-642-14279-6.

[DPR]

Klaus Deicke, David Pask, and Iain Raeburn. Coverings of Directed Graphs and Crossed Products of \(C^*\)-algebras by Coactions of Homogeneous Spaces. arXiv: math/0201033.

[GK98]

E. Getzler and M. M. Kapranov. “Modular operads”. In: Compositio Math. 110.1 (1998), pp. 65–126. arXiv: dg-ga/9408003. url: http://dx.doi.org/10.1023/A:1000245600345.

[IKW]

Kiyoshi Igusa, John Klein, and E. Bruce Williams. Outer authomorphisms and the Jacobian. arXiv: math/0502266.

[JK]

André Joyal and Joachim Kock. Feynman graphs, and nerve theorem for compact symmetric multicategories (extended abstract). arXiv: 0908.2675.

[KM94]

M. Kontsevich and Yu. Manin. “Gromov-Witten classes, quantum cohomology, and enumerative geometry”. In: Comm. Math. Phys. 164.3 (1994), pp. 525–562. arXiv: hep-th/9402147. url: http://projecteuclid.org/euclid.cmp/1104270948.

[Koc18]

Joachim Kock. “Cospan construction of the graph category of Borisov and Manin”. In: Publ. Mat. 62.2 (2018), pp. 331–353. arXiv: 1611.10342. url: https://doi.org/10.5565/PUBLMAT6221802.

[Koz07]

Dmitry N. Kozlov. “Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes”. In: Geometric combinatorics. Vol. 13. IAS/Park City Math. Ser. Providence, RI: Amer. Math. Soc., 2007, pp. 249–315. arXiv: math/0505563.

[Koz08]

Dmitry N. Kozlov. “Cohomology of colorings of cycles”. In: Amer. J. Math. 130.3 (2008), pp. 829–857. arXiv: math/0507117. url: http://dx.doi.org/10.1353/ajm.0.0007.

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

[PQR05]

David Pask, John Quigg, and Iain Raeburn. “Coverings of \(k\)-graphs”. In: J. Algebra 289.1 (2005), pp. 161–191. arXiv: math.OA/0401017. url: http://dx.doi.org/10.1016/j.jalgebra.2005.01.051.