ALGEBRAIC COMBINATORICS

no. 6
Irreducibility of the Tutte polynomial of an embedded graph
Ellis-Monaghan, Joanna A.1; Goodall, Andrew J.2; Moffatt, Iain3; Noble, Steven D.4; Vena, Lluís5
1 Korteweg-de Vries Instituut voor Wiskunde Universiteit van Amsterdam Science Park 105-107 1098 XG Amsterdam, The Netherlands
2 Computer Science Institute (IÚUK) Charles University Malostranské nám. 25 118 00 Praha 1 Czech Republic
3 Department of Mathematics Royal Holloway University of London Egham TW20 0EX United Kingdom
4 Department of Economics, Mathematics and Statistics Birkbeck University of London London WC1E 7HX United Kingdom
5 Department of Mathematics Universitat Politècnica de Catalunya Jordi Girona 1-3 08034 Barcelona Spain
Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1337-1351.

We prove that the ribbon graph polynomial of a graph embedded in an orientable surface is irreducible if and only if the embedded graph is neither the disjoint union nor the join of embedded graphs. This result is analogous to the fact that the Tutte polynomial of a graph is irreducible if and only if the graph is connected and non-separable.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.252
Classification: 05C31, 05B35
Keywords: Bollobás–Riordan polynomial, delta-matroid, irreducible, ribbon graph, ribbon graph polynomial, separable, Tutte polynomial
Ellis-Monaghan, Joanna A. 1; Goodall, Andrew J. 2; Moffatt, Iain 3; Noble, Steven D. 4; Vena, Lluís 5

1 Korteweg-de Vries Instituut voor Wiskunde Universiteit van Amsterdam Science Park 105-107 1098 XG Amsterdam, The Netherlands
2 Computer Science Institute (IÚUK) Charles University Malostranské nám. 25 118 00 Praha 1 Czech Republic
3 Department of Mathematics Royal Holloway University of London Egham TW20 0EX United Kingdom
4 Department of Economics, Mathematics and Statistics Birkbeck University of London London WC1E 7HX United Kingdom
5 Department of Mathematics Universitat Politècnica de Catalunya Jordi Girona 1-3 08034 Barcelona Spain
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2022__5_6_1337_0,
     author = {Ellis-Monaghan, Joanna A. and Goodall, Andrew J. and Moffatt, Iain and Noble, Steven D. and Vena, Llu{\'\i}s},
     title = {Irreducibility of the {Tutte} polynomial of an embedded graph},
     journal = {Algebraic Combinatorics},
     pages = {1337--1351},
     publisher = {The Combinatorics Consortium},
     volume = {5},
     number = {6},
     year = {2022},
     doi = {10.5802/alco.252},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.252/}
}
TY  - JOUR
AU  - Ellis-Monaghan, Joanna A.
AU  - Goodall, Andrew J.
AU  - Moffatt, Iain
AU  - Noble, Steven D.
AU  - Vena, Lluís
TI  - Irreducibility of the Tutte polynomial of an embedded graph
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 1337
EP  - 1351
VL  - 5
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.252/
DO  - 10.5802/alco.252
LA  - en
ID  - ALCO_2022__5_6_1337_0
ER  - 
%0 Journal Article
%A Ellis-Monaghan, Joanna A.
%A Goodall, Andrew J.
%A Moffatt, Iain
%A Noble, Steven D.
%A Vena, Lluís
%T Irreducibility of the Tutte polynomial of an embedded graph
%J Algebraic Combinatorics
%D 2022
%P 1337-1351
%V 5
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.252/
%R 10.5802/alco.252
%G en
%F ALCO_2022__5_6_1337_0
Ellis-Monaghan, Joanna A.; Goodall, Andrew J.; Moffatt, Iain; Noble, Steven D.; Vena, Lluís. Irreducibility of the Tutte polynomial of an embedded graph. Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1337-1351. doi : 10.5802/alco.252. https://alco.centre-mersenne.org/articles/10.5802/alco.252/

[1] Bollobás, Béla Modern graph theory, Graduate Texts in Mathematics, 184, Springer-Verlag, New York, 1998, xiv+394 pages | DOI

[2] Bollobás, Béla; Riordan, Oliver A polynomial invariant of graphs on orientable surfaces, Proc. London Math. Soc., Volume 83 (2001) no. 3, pp. 513-531 | DOI | MR | Zbl

[3] Bollobás, Béla; Riordan, Oliver A polynomial of graphs on surfaces, Math. Ann., Volume 323 (2002) no. 1, pp. 81-96 | DOI | MR | Zbl

[4] Bouchet, André Greedy algorithm and symmetric matroids, Math. Programming, Volume 38 (1987) no. 2, pp. 147-159 | DOI | MR | Zbl

[5] Bouchet, André Representability of ▵-matroids, Combinatorics (Eger, 1987) (Colloq. Math. Soc. János Bolyai), Volume 52, North-Holland, Amsterdam, 1988, pp. 167-182 | MR | Zbl

[6] Bouchet, André Maps and ▵-matroids, Discrete Math., Volume 78 (1989) no. 1-2, pp. 59-71 | DOI | MR | Zbl

[7] Bouchet, André Multimatroids. III. Tightness and fundamental graphs, European J. Combin., Volume 22 (2001) no. 5, pp. 657-677 Combinatorial geometries (Luminy, 1999) | DOI | MR | Zbl

[8] Brylawski, Thomas H. A decomposition for combinatorial geometries, Trans. Amer. Math. Soc., Volume 171 (1972), pp. 235-282 | DOI | MR | Zbl

[9] Brylawski, Thomas H.; Oxley, James G. The Tutte polynomial and its applications, Matroid applications (Encyclopedia Math. Appl.), Volume 40, Cambridge Univ. Press, Cambridge, 1992, pp. 123-225 | DOI | MR | Zbl

[10] Chandrasekaran, Ramaswamy; Kabadi, Santosh N. Pseudomatroids, Discrete Math., Volume 71 (1988) no. 3, pp. 205-217 | DOI | MR | Zbl

[11] Chun, Carolyn; Chun, Deborah; Noble, Steven D. Inductive tools for connected delta-matroids and multimatroids, European J. Combin., Volume 63 (2017), pp. 59-69 | DOI | MR | Zbl

[12] Chun, Carolyn; Moffatt, Iain; Noble, Steven D.; Rueckriemen, Ralf Matroids, delta-matroids and embedded graphs, J. Combin. Theory Ser. A, Volume 167 (2019), pp. 7-59 | DOI | MR | Zbl

[13] Chun, Carolyn; Moffatt, Iain; Noble, Steven D.; Rueckriemen, Ralf On the interplay between embedded graphs and delta-matroids, Proc. London Math. Soc., Volume 118 (2019) no. 3, pp. 675-700 | DOI | MR | Zbl

[14] Crapo, Henry H. The Tutte polynomial, Aequationes Math., Volume 3 (1969), pp. 211-229 | DOI | MR | Zbl

[15] Dress, Andreas; Havel, Timothy F. Some combinatorial properties of discriminants in metric vector spaces, Adv. in Math., Volume 62 (1986) no. 3, pp. 285-312 | DOI | MR | Zbl

[16] Duchamp, Alain Delta matroids whose fundamental graphs are bipartite, Linear Algebra Appl., Volume 160 (1992), pp. 99-112 | DOI | MR | Zbl

[17] Dupont, Clément; Fink, Alex; Moci, Luca Universal Tutte characters via combinatorial coalgebras, Algebr. Comb., Volume 1 (2018) no. 5, pp. 603-651 | Numdam | MR | Zbl

[18] Ellis-Monaghan, Joanna A.; Merino, Criel Graph polynomials and their applications I: The Tutte polynomial, Structural analysis of complex networks, Birkhäuser/Springer, New York, 2011, pp. 219-255 | DOI | Zbl

[19] Ellis-Monaghan, Joanna A.; Moffatt, Iain Graphs on surfaces: Dualities, Polynomials, and Knots, SpringerBriefs in Mathematics, Springer, New York, 2013, xii+139 pages | DOI

[20] Handbook of the Tutte polynomial and related topics (Ellis-Monaghan, Joanna A.; Moffatt, Iain, eds.), CRC Press, 2022 | DOI

[21] Goodall, Andrew; Litjens, Bart; Regts, Guus; Vena, Lluís A Tutte polynomial for maps II: the non-orientable case, European J. Combin., Volume 86 (2020), p. 103095, 32 pages | DOI | MR | Zbl

[22] Goodall, Andrew J.; Krajewski, Thomas; Regts, Guus; Vena, Lluís A Tutte polynomial for maps, Combin. Probab. Comput., Volume 27 (2018) no. 6, pp. 913-945 | DOI | MR | Zbl

[23] Gordon, Gary Linear relations for a generalized Tutte polynomial, Electron. J. Combin., Volume 22 (2015) no. 1, p. P1.79, 30 pages | MR | Zbl

[24] Gross, Jonathan L.; Tucker, Thomas W. Topological graph theory, Wiley, 1987

[25] Huggett, Stephen; Moffatt, Iain Types of embedded graphs and their Tutte polynomials, Math. Proc. Cambridge Philos. Soc., Volume 169 (2020) no. 2, pp. 255-297 | DOI | MR | Zbl

[26] Krajewski, Thomas; Moffatt, Iain; Tanasa, Adrian Hopf algebras and Tutte polynomials, Adv. in Appl. Math., Volume 95 (2018), pp. 271-330 | DOI | MR | Zbl

[27] Krushkal, Vyacheslav Graphs, Links, and Duality on Surfaces, Combin. Probab. Comput., Volume 20 (2011), pp. 267-287 | DOI | MR | Zbl

[28] Las Vergnas, Michel Eulerian circuits of 4-valent graphs imbedded in surfaces, Algebraic Methods in Graph Theory (Lovász, L.; Sós, V., eds.), North Holland, 1981, pp. 451-478 | Zbl

[29] Merino, Criel; de Mier, Anna; Noy, Marc Irreducibility of the Tutte polynomial of a connected matroid, J. Combin. Theory Ser. B, Volume 83 (2001) no. 2, pp. 298-304 | DOI | MR | Zbl

[30] Merino, Criel; Moffatt, Iain; Noble, Steven D. Series–parallel delta-matroids (in preparation)

[31] Moffatt, Iain Delta-matroids for graph theorists, Surveys in combinatorics 2019 (London Math. Soc. Lecture Note Ser.), Volume 456, Cambridge Univ. Press, Cambridge, 2019, pp. 167-220 | DOI | MR | Zbl

[32] Moffatt, Iain; Smith, Ben Matroidal frameworks for topological Tutte polynomials, J. Combin. Theory Ser. B, Volume 133 (2018), pp. 1-31 | DOI | MR | Zbl

[33] Moffatt, Iain; Thompson, Maya Deletion-contraction and the surface Tutte polynomial (in preparation)

[34] Negami, Seiya Polynomial invariants of embeddings of graphs on closed surfaces, Sci. Rep. Yokohama Nat. Univ. Sect. I Math. Phys. Chem. (1995) no. 42, pp. 1-10 | MR

[35] Oxley, James G. Matroid theory, Oxford Graduate Texts in Mathematics, 21, Oxford Univ. Press, Oxford, 2011, xiv+684 pages | DOI

[36] Welsh, Dominic J. A. Complexity: knots, colourings and counting, London Mathematical Society Lecture Note Series, 186, Cambridge University Press, Cambridge, 1993, viii+163 pages

Cited by Sources: