Polynomial Invariants for Embedded Graphs

Bollobás-Riordan polynomial を始めとして, ribbon˙graphや 曲面に埋め込まれたgraph に対し, graph の多項式不変量を一般化しようという試みは, 色々行われている。

• Bollobás-Riordan polynomial

最近でも, Krushkal [Kru11] によるものがある。

• Krushkal polynomial

一方で, 埋め込む前の graph については, 様々な不変量がある。 グラフの組み合せ論的構造を matroid として抽出する と, matroid の不変量を考えることができる。 Askanazi, Chmutov, Estill, Michel, Stollenwerk [Ask+] は, Las Vergnas により, matroid の写像に対し定義された多項式不変量 [Las78; Las80; Las81] と Krushkal polynomial の関係を調べている。

Ellis-Monaghan と Moffatt が拡張を色々考えていて, [EM12] では, transition polynomial の拡張, [EM13] では, 平面グラフの Penrose polynomial [Pen71] の拡張を考えている。

Chun, Moffatt, Noble, Rueckriemen [Chu+] によると, \(\Delta \)-matroid にも一般化できるようである。

References

[Ask+]

R. Askanazi, S. Chmutov, C. Estill, J. Michel, and P. Stollenwerk. Polynomial invariants of graphs on surfaces. arXiv: 1012.5053.

[Chu+]

Carolyn Chun, Iain Moffatt, Steven D. Noble, and Ralf Rueckriemen. Matroids, Delta-matroids and Embedded Graphs. arXiv: 1403.0920.

[EM12]

Joanna A. Ellis-Monaghan and Iain Moffatt. “Twisted duality for embedded graphs”. In: Trans. Amer. Math. Soc. 364.3 (2012), pp. 1529–1569. arXiv: 0906.5557. url: https://doi.org/10.1090/S0002-9947-2011-05529-7.

[EM13]

Joanna A. Ellis-Monaghan and Iain Moffatt. “A Penrose polynomial for embedded graphs”. In: European J. Combin. 34.2 (2013), pp. 424–445. arXiv: 1106.5279. url: https://doi.org/10.1016/j.ejc.2012.06.009.

[Kru11]

Vyacheslav Krushkal. “Graphs, links, and duality on surfaces”. In: Combin. Probab. Comput. 20.2 (2011), pp. 267–287. arXiv: 0903.5312. url: http://dx.doi.org/10.1017/S0963548310000295.

[Las78]

Michel Las Vergnas. “Sur les activités des orientations d’une géométrie combinatoire”. In: Cahiers Centre Études Rech. Opér. 20.3-4 (1978). Colloque Mathématiques Discrètes: Codes et Hypergraphes (Brussels, 1978), pp. 293–300.

[Las80]

Michel Las Vergnas. “On the Tutte polynomial of a morphism of matroids”. In: Ann. Discrete Math. 8 (1980). Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part I, pp. 7–20.

[Las81]

M. Las Vergnas. “Eulerian circuits of \(4\)-valent graphs imbedded in surfaces”. In: Algebraic methods in graph theory, Vol. I, II (Szeged, 1978). Vol. 25. Colloq. Math. Soc. János Bolyai. Amsterdam: North-Holland, 1981, pp. 451–477.

[Pen71]

Roger Penrose. “Applications of negative dimensional tensors”. In: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969). London: Academic Press, 1971, pp. 221–244.