グラフの基本

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

ここでは, トポロジーとの関係から, グラフについて知っておいた方が良いことをまとめた。

まずはグラフの定義であるが, 頂点の集合と辺の集合という二つの集合を用いるのが普通だろう。 Getzler と Kapranov の [GK98] では, 集合とその上の involution と partition を用いた定義が用いられていて面白い。 彼らは, その集合の元のことを flag と呼んでいるが, その呼び方は Kontsevich と Manin [KM94] に依るものなのだろうか。

• Getzler と Kapranov によるグラフの定義

グラフに対する操作としては, 辺を潰す (edge contraction) のと取り除く (deletion) のが基本である。 もちろん, 他にも様々な操作が考えられている。

• グラフに対する各種操作

グラフの間の“写像’’を考え, graph の圏を考えることもできる。 例えば, 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 に関する類似を考えている。

• グラフの被覆空間

離散モース理論では, poset の Hasse diagram の上の partial matching が中心となる。他にもgraph を扱うときは, その上での matching を考えることは基本的である。 Matching については, Lovász と Plummer の本 [LP09] がある。

• partial matching
• perfect matching

Turaev [Tur] は, perfect matching のことを dimer covering と呼んでいる。Turaevによると, perfect matching の研究は, 1960年代以降 統計物理などの要請で進んだようである。 例えば dimer model など [Ken04]。

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

• 無限グラフ

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.

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

[Ken04]

Richard Kenyon. “An introduction to the dimer model”. In: School and Conference on Probability Theory. ICTP Lect. Notes, XVII. Abdus Salam Int. Cent. Theoret. Phys., Trieste, 2004, 267–304 (electronic). arXiv: math/0310326.

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

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

[LP09]

László Lovász and Michael D. Plummer. Matching theory. Corrected reprint of the 1986 original [MR0859549]. AMS Chelsea Publishing, Providence, RI, 2009, pp. xxxiv+554. isbn: 978-0-8218-4759-6.

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

[Tur]

Vladimir Turaev. Dimer spaces and gliding systems. arXiv: 1211.3975.