×

Matroids, delta-matroids and embedded graphs. (English) Zbl 1417.05103

Summary: Matroid theory is often thought of as a generalisation of graph theory. In this paper we propose an analogous correspondence between embedded graphs and delta-matroids. We show that delta-matroids arise as the natural extension of graphic matroids to the setting of embedded graphs. We show that various basic ribbon graph operations and concepts have delta-matroid analogues, and illustrate how the connections between embedded graphs and delta-matroids can be exploited. Also, in direct analogy with the fact that the Tutte polynomial is matroidal, we show that several polynomials of embedded graphs from the literature, including the Las Vergnas, Bollabás-Riordan and Krushkal polynomials, are in fact delta-matroidal.

MSC:

05C35 Extremal problems in graph theory
05C31 Graph polynomials
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Askanazi, R.; Chmutov, S.; Estill, C.; Michel, J.; Stollenwerk, P., Polynomial invariants of graphs on surfaces, Quantum Topol., 4, 77-90 (2013) · Zbl 1257.05065
[2] Bollobás, B.; Riordan, O., A polynomial for graphs on orientable surfaces, Proc. Lond. Math. Soc., 83, 513-531 (2001) · Zbl 1015.05024
[3] Bollobás, B.; Riordan, O., A polynomial of graphs on surfaces, Math. Ann., 323, 81-96 (2002) · Zbl 1004.05021
[4] Bouchet, A., Representability of Δ-matroids, (Proceedings of the 6th Hungarian Colloquium of Combinatorics. Proceedings of the 6th Hungarian Colloquium of Combinatorics, Colloq. Math. Soc. János Bolyai (1987)), 167-182
[5] Bouchet, A., Greedy algorithm and symmetric matroids, Math. Program., 38, 147-159 (1987) · Zbl 0633.90089
[6] Bouchet, A., Maps and delta-matroids, Discrete Math., 78, 59-71 (1989) · Zbl 0719.05019
[7] Bouchet, A., Circle graph obstructions, J. Combin. Theory Ser. B, 60, 107-144 (1994) · Zbl 0793.05116
[8] Bouchet, A., Coverings and delta-coverings, (Balas, E.; Clausen, J., Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 920 (1995), Springer: Springer Berlin), 228-243 · Zbl 1498.90182
[9] Bouchet, A., Multimatroids III. Tightness and fundamental graphs, European J. Combin., 22, 657-677 (2001) · Zbl 0982.05034
[10] Bouchet, A.; Cunningham, W., Delta-matroids, jump systems, and bisubmodular polyhedra, SIAM J. Discrete Math., 8, 17-32 (1995) · Zbl 0821.05010
[11] Bouchet, A.; Duchamp, A., Representability of delta-matroids over \(G F(2)\), Linear Algebra Appl., 146, 67-78 (1991) · Zbl 0738.05027
[12] Bouchet, A.; Schwärzler, W., The delta-sum of matching delta-matroids, Discrete Appl. Math., 181, 53-63 (1998) · Zbl 0901.05025
[13] Brijder, R.; Hoogeboom, H., The group structure of pivot and loop complementation on graphs and set systems, European J. Combin., 32, 1353-1367 (2011) · Zbl 1230.05197
[14] Brijder, R.; Hoogeboom, H., Nullity and loop complementation for delta-matroids, SIAM J. Discrete Math., 27, 492-506 (2013) · Zbl 1268.05040
[15] Brijder, R.; Hoogeboom, H., Interlace polynomials for multimatroids and delta-matroids, European J. Combin., 40, 142-167 (2014) · Zbl 1300.05051
[16] Brijder, R.; Traldi, L., Isotropic matroids. II. Circle graphs, Electron. J. Combin., 23 (2016), paper 4.2 · Zbl 1351.05044
[17] Brylawski, T., A decomposition for combinatorial geometries, J. Combin. Theory Ser. B, 171, 235-282 (1972) · Zbl 0224.05007
[18] Brylawski, T.; Oxley, J., The Tutte polynomial and its applications, (Matroid Applications. Matroid Applications, Encyclopedia Math. Appl., vol. 40 (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 123-225 · Zbl 0769.05026
[19] Butler, C., A quasi-tree expansion of the Krushkal polynomial, Adv. in Appl. Math., 94, 3-22 (2018) · Zbl 1387.05117
[20] Champanerkar, A.; Kofman, I.; Stoltzfus, N., Quasi-tree expansion for the Bollobás-Riordan-Tutte polynomial, Bull. Lond. Math. Soc., 43, 972-984 (2011) · Zbl 1230.05167
[21] Chmutov, S.; Pak, I., The Kauffman bracket of virtual links and the Bollobás-Riordan polynomial, Mosc. Math. J., 7, 409-418 (2007) · Zbl 1155.57004
[22] Chmutov, S., Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial, J. Combin. Theory Ser. B, 99, 617-638 (2009) · Zbl 1172.05015
[23] Chmutov, S.; Voltz, J., Thistlethwaite’s theorem for virtual links, J. Knot Theory Ramifications, 17, 1189-1198 (2008) · Zbl 1163.57001
[24] Chun, C.; Chun, D.; Noble, S. D., Inductive tools for connected delta-matroids and multimatroids, European J. Combin., 63, 59-69 (2017) · Zbl 1365.05040
[25] C. Chun, I. Moffatt, S.D. Noble, R. Rueckriemen, On the interplay between embedded graphs and delta-matroids, preprint.; C. Chun, I. Moffatt, S.D. Noble, R. Rueckriemen, On the interplay between embedded graphs and delta-matroids, preprint. · Zbl 1410.05029
[26] Dasbach, O.; Futer, D.; Kalfagianni, E.; Lin, X.-S.; Stoltzfus, N., Alternating sum formulae for the determinant and other link invariants, J. Knot Theory Ramifications, 19, 765-782 (2010) · Zbl 1200.57008
[28] Duchamp, A., Delta-matroids whose fundamental graphs are bipartite, Linear Algebra Appl., 160, 99-112 (1992) · Zbl 0749.05025
[29] Ellis-Monaghan, J.; Merino, C., Graph polynomials and their applications I: the Tutte polynomial, (Structural Analysis of Complex Networks (2011), Birkhäuser), 219-255 · Zbl 1221.05002
[30] Ellis-Monaghan, J.; Sarmiento, I., A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan, European J. Combin., 32, 782-794 (2011) · Zbl 1223.05039
[31] Ellis-Monaghan, J.; Moffatt, I., Twisted duality for embedded graphs, Trans. Amer. Math. Soc., 364, 1529-1569 (2012) · Zbl 1238.05067
[32] Ellis-Monaghan, J.; Moffatt, I., Graphs on Surfaces: Dualities, Polynomials, and Knots (2013), Springer · Zbl 1283.57001
[33] Ellis-Monaghan, J.; Moffatt, I., Evaluations of topological Tutte polynomials, Combin. Probab. Comput., 24, 556-583 (2015) · Zbl 1371.05134
[34] Ellis-Monaghan, J.; Sarmiento, I., A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan, European J. Combin., 32, 782-794 (2011) · Zbl 1223.05039
[35] Farr, G., Tutte-Whitney polynomials: some history and generalizations, (Grimmett, G. R.; McDiarmid, C. J.H., Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh (2007), Oxford University Press), 28-52 · Zbl 1124.05020
[36] Geelen, J.; Gerards, B.; Whittle, G., Structure in minor-closed classes of matroids, (Blackburn, S. R.; Gerke, S.; Wildon, M., Surveys in Combinatorics 2013. Surveys in Combinatorics 2013, London Math. Soc. Lecture Notes, vol. 409 (2013), Cambridge University Press), 327-362 · Zbl 1318.05015
[37] Geelen, J.; Iwata, S.; Murota, K., The linear delta-matroid parity problem, J. Combin. Theory Ser. B, 88, 377-398 (2003) · Zbl 1021.05019
[38] Geelen, J.; Oum, S., Circle graph obstructions under pivoting, J. Graph Theory, 61, 1-11 (2009) · Zbl 1207.05189
[39] Gross, J.; Tucker, T., Topological Graph Theory (1987), Wiley-Interscience Publication
[40] M. Korn, I. Pak, Combinatorial evaluations of the Tutte polynomial, preprint.; M. Korn, I. Pak, Combinatorial evaluations of the Tutte polynomial, preprint.
[41] Kotzig, A., Eulerian lines in finite 4-valent graphs and their transformations, (Theory of Graphs (Proc. Colloq. Tihany, 1966) (1968), Academic Press: Academic Press New York), 219-230
[42] Krajewski, T.; Moffatt, I.; Tanasa, A., Hopf algebras and Tutte polynomials, Adv. in Appl. Math., 95, 271-330 (2018) · Zbl 1379.05057
[43] Krushkal, S., Graphs, links, and duality on surfaces, Combin. Probab. Comput., 20, 267-287 (2011) · Zbl 1211.05029
[44] Las, M., Vergnas, Eulerian circuits of 4-valent graphs imbedded in surfaces, (Algebraic Methods in Graph Theory, vol. I, II. Algebraic Methods in Graph Theory, vol. I, II, Szeged, 1978. Algebraic Methods in Graph Theory, vol. I, II. Algebraic Methods in Graph Theory, vol. I, II, Szeged, 1978, Colloq. Math. Soc. János Bolyai, vol. 25 (1981), North-Holland: North-Holland Amsterdam-New York), 451-477
[45] Las Vergnas, M., Extensions normales d’un matroïde, polynôme de Tutte d’un morphisme, C. R. Acad. Sci. Paris Sér. A-B, 22, 1479-1482 (1975) · Zbl 0327.05034
[46] Las Vergnas, M., Sur les activités des orientations d’une géométrie combinatoire, (Colloque Mathématiques Discrètes: Codes et Hypergraphes. Colloque Mathématiques Discrètes: Codes et Hypergraphes, Brussels, 1978. Colloque Mathématiques Discrètes: Codes et Hypergraphes. Colloque Mathématiques Discrètes: Codes et Hypergraphes, Brussels, 1978, Cahiers Centre Études Rech. Opér., vol. 20 (1978)), 293-300 · Zbl 0404.05018
[47] Las Vergnas, M., On the Tutte polynomial of a morphism of matroids, Ann. Discrete Math., 8, 7-20 (1980) · Zbl 0462.05021
[48] Moffatt, I., Knot invariants and the Bollobás-Riordan polynomial of embedded graphs, European J. Combin., 29, 95-107 (2008) · Zbl 1142.57003
[49] Moffatt, I., A characterization of partially dual graphs, J. Graph Theory, 67, 198-217 (2011) · Zbl 1232.05059
[50] Moffatt, I., Partial duals of plane graphs, separability and the graphs of knots, Algebr. Geom. Topol., 12, 1099-1136 (2012) · Zbl 1245.05030
[51] Moffatt, I., Separability and the genus of a partial dual, European J. Combin., 34, 355-378 (2013) · Zbl 1254.05047
[52] Moffatt, I., Excluded minors and the ribbon graphs of knots, J. Graph Theory, 81, 329-341 (2016) · Zbl 1333.05279
[53] Moffatt, I.; Strömberg, J., On the ribbon graphs of links in real projective space, Involve, 9, 133-153 (2016) · Zbl 1345.57004
[54] Oxley, J., On the interplay between graphs and matroids, (Hirschfeld, J. W.P., Surveys in Combinatorics, 2001. Surveys in Combinatorics, 2001, London Math. Soc. Lecture Notes, vol. 288 (2001), Cambridge University Press: Cambridge University Press Cambridge), 199-239 · Zbl 0979.05030
[55] Oxley, J., Matroid Theory (2011), Oxford University Press: Oxford University Press New York · Zbl 1254.05002
[57] Seymour, P., A note on the production of matroid minors, J. Combin. Theory Ser. B, 22, 289-295 (1977) · Zbl 0385.05021
[58] Thistlethwaite, M. B., A spanning tree expansion of the Jones polynomial, Topology, 26, 297-309 (1987) · Zbl 0622.57003
[59] Traldi, L., Binary nullity, Euler circuits and interlace polynomials, European J. Combin., 32, 944-950 (2011) · Zbl 1227.05168
[60] Traldi, L., Binary matroids and local complementation, European J. Combin., 45, 21-40 (2015) · Zbl 1304.05015
[61] Traldi, L., The transition matroid of a 4-regular graph: an introduction, European J. Combin., 50, 180-207 (2015) · Zbl 1319.05034
[62] Tutte, W., A ring in graph theory, Math. Proc. Cambridge Philos. Soc., 43, 26-40 (1947) · Zbl 0031.41803
[63] Tutte, W., Lectures on matroids, J. Res. Natl. Bur. Stand. B, 69B, 1-47 (1965) · Zbl 0151.33801
[64] Tutte, W., Connectivity in matroids, Canad. J. Math., 18, 1301-1324 (1966) · Zbl 0149.21501
[65] Vignes-Tourneret, F., Non-orientable quasi-trees for the Bollobás-Riordan polynomial, European J. Combin., 32, 510-532 (2011) · Zbl 1226.05104
[66] Welsh, D. J.A., Complexity: Knots, Colouring and Counting (1993), Cambridge University Press · Zbl 0799.68008
[67] Wu, P.-L., An upper bound on the number of edges of a 2-connected graph, Combin. Probab. Comput., 6, 107-113 (1997) · Zbl 0867.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.