Universal Tutte characters via combinatorial coalgebras
Algebraic Combinatorics, Volume 1 (2018) no. 5, p. 603-651
This work discusses the extraction of meaningful invariants of combinatorial objects from coalgebra or bialgebra structures. The Tutte polynomial is an invariant of graphs well known for the formula which computes it recursively by deleting and contracting edges, and for its universality with respect to similar recurrence. We generalize this to all classes of combinatorial objects with deletion and contraction operations, associating to each such class a universal Tutte character by a functorial procedure. We show that these invariants satisfy a universal property and convolution formulae similar to the Tutte polynomial. With this machinery we recover classical invariants for delta-matroids, matroid perspectives, relative and colored matroids, generalized permutohedra, and arithmetic matroids. We also produce some new invariants along with new convolution formulae.
Received : 2017-11-24
Revised : 2018-05-17
Accepted : 2018-07-11
Published online : 2018-11-30
DOI : https://doi.org/10.5802/alco.35
Classification:  16T10,  16T15,  05B35,  05C31
Keywords: coalgebra, bialgebra, Tutte polynomial, dichromatic polynomial, Las Vergnas polynomial, Bollobás–Riordan polynomial, arithmetic Tutte polynomial, minors system, convolution formula
@article{ALCO_2018__1_5_603_0,
     author = {Dupont, Cl\'ement and Fink, Alex and Moci, Luca},
     title = {Universal Tutte characters via combinatorial coalgebras},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {1},
     number = {5},
     year = {2018},
     pages = {603-651},
     doi = {10.5802/alco.35},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2018__1_5_603_0}
}
Dupont, Clément; Fink, Alex; Moci, Luca. Universal Tutte characters via combinatorial coalgebras. Algebraic Combinatorics, Volume 1 (2018) no. 5, pp. 603-651. doi : 10.5802/alco.35. https://alco.centre-mersenne.org/item/ALCO_2018__1_5_603_0/

[1] Aguiar, Marcelo; Ardila, Federico Hopf monoids and generalized permutahedra (2017) (https://arxiv.org/abs/1709.07504 )

[2] Aguiar, Marcelo; Mahajan, Swapneel Monoidal functors, species and Hopf algebras, American Mathematical Society, CRM Monograph Series, Volume 29 (2010), lii+784 pages | MR 2724388 | Zbl 1209.18002

[3] Backman, Spencer; Lenz, Matthias A convolution formula for Tutte polynomials of arithmetic matroids and other combinatorial structures (2016) (https://arxiv.org/abs/1602.02664 )

[4] Bollobás, Béla; Riordan, Oliver A Tutte polynomial for coloured graphs, Comb. Probab. Comput., Volume 8 (1999) no. 1-2, pp. 45-93 (Recent trends in combinatorics (Mátraháza, 1995)) | Article | MR 1684623 | Zbl 0926.05017

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

[6] Bouchet, André Greedy algorithm and symmetric matroids, Math. Program., Volume 38 (1987) no. 2, pp. 147-159 | Article | MR 904585 | Zbl 0633.90089

[7] Bouchet, André Maps and Δ-matroids, Discrete Math., Volume 78 (1989) no. 1-2, pp. 59-71 | Article | MR 1020647 | Zbl 0719.05019

[8] Brändén, Petter; Moci, Luca The multivariate arithmetic Tutte polynomial, Trans. Am. Math. Soc., Volume 366 (2014) no. 10, pp. 5523-5540 | Article | MR 3240933 | Zbl 1300.05133

[9] Brylawski, Thomas H. A decomposition for combinatorial geometries, Trans. Am. Math. Soc., Volume 171 (1972), pp. 235-282 | Article | MR 0309764 | Zbl 0224.05007

[10] Butler, Clark A quasi-tree expansion of the Krushkal polynomial, Adv. Appl. Math., Volume 94 (2016), pp. 3-22 | Zbl 1387.05117

[11] Chaiken, Seth The Tutte polynomial of a ported matroid, J. Comb. Theory, Ser. B, Volume 46 (1989) no. 1, pp. 96-117 | Article | MR 982858 | Zbl 0614.0517

[12] Crapo, Henry Constructions in Combinatorial Geometry, Lecture Notes for the Combinatorial Theory Advanced Science Seminar, Bowdoin College. Brunswick, ME (1971)

[13] D’Adderio, Michele; Moci, Luca Arithmetic matroids, the Tutte polynomial and toric arrangements, Adv. Math., Volume 232 (2013) no. 1, pp. 335-367 | Article | MR 2989987 | Zbl 1256.05039

[14] Delucchi, Emanuele; Moci, Luca Products of arithmetic matroids and quasipolynomial invariants of CW-complexes, J. Comb. Theory, Ser. A, Volume 157 (2018), pp. 28-40 | Article | MR 3780405 | Zbl 1385.05029

[15] Diao, Yuanan; Hetyei, Gábor Relative Tutte polynomials for coloured graphs and virtual knot theory, Comb. Probab. Comput., Volume 19 (2010) no. 3, pp. 343-369 | Article | MR 2607372 | Zbl 1202.05064

[16] Duchamp, Gérard H. E.; Hoang-Nghia, Nguyen; Krajewski, Thomas; Tanasa, Adrian Recipe theorem for the Tutte polynomial for matroids, renormalization group-like approach, Adv. Appl. Math., Volume 51 (2013) no. 3, pp. 345-358 | Article | MR 3084503 | Zbl 1281.05040

[17] Edmonds, Jack Submodular functions, matroids, and certain polyhedra, Combinatorial structures and their applications (Calgary, 1969), Gordon and Breach (1970) | Zbl 0268.05019

[18] Etienne, Gwihen; Las Vergnas, Michel External and internal elements of a matroid basis, Discrete Math., Volume 179 (1998) no. 1-3, pp. 111-119 | Article | MR 1489076 | Zbl 0887.05012

[19] Fink, Alex; Moci, Luca Matroids over a ring, J. Eur. Math. Soc., Volume 18 (2016) no. 4, pp. 681-731 | Article | MR 3474454 | Zbl 1335.05031

[20] Fortuin, Cornelius M.; Kasteleyn, Pieter W. On the random-cluster model. I. Introduction and relation to other models, Physica, Volume 57 (1972), pp. 536-564 | Article | MR 0359655

[21] Higgs, Denis A. Strong maps of geometries, J. Comb. Theory, Volume 5 (1968), pp. 185-191 | Article | MR 0231761 | Zbl 0164.20602

[22] Joni, Saj-Nicole A.; Rota, Gian-Carlo Coalgebras and bialgebras in combinatorics, Stud. Appl. Math., Volume 61 (1979) no. 2, pp. 93-139 | Article | MR 544721 | Zbl 0471.05020

[23] Joyal, André Une théorie combinatoire des séries formelles, Adv. Math., Volume 42 (1981) no. 1, pp. 1-82 | Article | MR 633783 | Zbl 0491.05007

[24] Kayibi, Koko K. A decomposition theorem for the linking polynomial of two matroids, Discrete Math., Volume 308 (2008) no. 4, pp. 583-596 | Article | MR 2376481 | Zbl 1140.05018

[25] Kayibi, Koko K.; Pirzada, Shariefuddin On the activities of p-basis of matroid perspectives, Discrete Math., Volume 339 (2016) no. 6, pp. 1629-1639 | Article | MR 3477092 | Zbl 1333.05064

[26] Kook, Woong; Reiner, Victor; Stanton, Dennis A convolution formula for the Tutte polynomial, J. Comb. Theory, Ser. B, Volume 76 (1999) no. 2, pp. 297-300 | Article | MR 1699230 | Zbl 0936.05028

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

[28] Krushkal, Vyacheslav Graphs, links, and duality on surfaces, Comb. Probab. Comput., Volume 20 (2011) no. 2, pp. 267-287 | Article | MR 2769192 | Zbl 1211.05029

[29] Kung, Joseph P. S. Strong maps, Theory of matroids, Cambridge University Press (Encyclopedia of Mathematics and Its Applications) Volume 26 (1986), pp. 224-253 | MR 849397 | Zbl 0596.05014

[30] Kung, Joseph P. S. Convolution-multiplication identities for Tutte polynomials of graphs and matroids, J. Comb. Theory, Ser. B, Volume 100 (2010) no. 6, pp. 617-624 | Article | MR 2718681 | Zbl 1230.05169

[31] Las Vergnas, Michel Extensions normales d’un matroïde, polynôme de Tutte d’un morphisme, C. R. Acad. Sci. Paris, Sér. A-B, Volume 280 (1975) no. 22, pp. 1479-1482 | MR 0419272 | Zbl 0327.05034

[32] Las Vergnas, Michel The Tutte polynomial of a morphism of matroids. I. Set-pointed matroids and matroid perspectives, Ann. Inst. Fourier, Volume 49 (1999) no. 3, pp. 973-1015 | Article | Numdam | MR 1703434 | Zbl 0917.05019

[33] Liu, Ye; Tran, Tan Nhat; Yoshinaga, Masahiko G-Tutte polynomials and abelian Lie group arrangements (2017) (https://arxiv.org/abs/1707.04551 )

[34] Moci, Luca A Tutte polynomial for toric arrangements, Trans. Am. Math. Soc., Volume 364 (2012) no. 2, pp. 1067-1088 | Article | MR 2846363 | Zbl 1235.52038

[35] Moffatt, Iain; Smith, Ben Matroidal frameworks for topological Tutte polynomials, J. Comb. Theory, Ser. B, Volume 133 (2018), pp. 1-31 | Article | MR 3856702 | Zbl 1397.05084

[36] Oxley, James Matroid theory, Oxford University Press, Oxford Graduate Texts in Mathematics, Volume 21 (2011), xiv+684 pages | Article | MR 2849819 | Zbl 1254.05002

[37] Oxley, James; Whittle, Geoff A characterization of Tutte invariants of 2-polymatroids, J. Comb. Theory, Ser. B, Volume 59 (1993) no. 2, pp. 210-244 | Article | MR 1244932 | Zbl 0793.05042

[38] Postnikov, Alexander Permutohedra, associahedra, and beyond, Int. Math. Res. Not., Volume 2009 (2009) no. 6, pp. 1026-1106 | Article | MR 2487491 | Zbl 1162.52007

[39] Reiner, Victor An interpretation for the Tutte polynomial, Eur. J. Comb., Volume 20 (1999) no. 2, pp. 149-161 | Article | MR 1676189 | Zbl 0924.05015

[40] Schmitt, William R. Hopf algebras of combinatorial structures, Can. J. Math., Volume 45 (1993) no. 2, pp. 412-428 | Article | MR 1208124 | Zbl 0781.16026

[41] Schmitt, William R. Incidence Hopf algebras, Journal of Pure and Applied Algebra, Volume 96 (1994) no. 3, pp. 299-330 | Article | MR 1303288 | Zbl 0808.05101

[42] Sokal, Alan D. The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, Surveys in combinatorics 2005, Cambridge University Press (London Mathematical Society Lecture Note Series) Volume 327 (2005), pp. 173-226 | MR 2187739 | Zbl 1110.05020

[43] Tardos, Éva Generalized matroids and supermodular colourings, Matroid theory (Szeged, 1982), North-Holland (Colloquia Mathematica Societatis János Bolyai) Volume 40 (1985), pp. 359-382 | MR 843383 | Zbl 0602.05020

[44] Traldi, Lorenzo A dichromatic polynomial for weighted graphs and link polynomials, Proc. Am. Math. Soc., Volume 106 (1989) no. 1, pp. 279-286 | Article | MR 955462 | Zbl 0713.57003

[45] Tutte, William T. On dichromatic polynomials, J. Comb. Theory, Volume 2 (1967) no. 3, pp. 301-320 | Article | Zbl 0147.42902

[46] Wang, Suijie Möbius conjugation and convolution formulae, J. Comb. Theory, Ser. B, Volume 115 (2015), pp. 117-131 | Article | MR 3383253 | Zbl 1319.05073

[47] Zaslavsky, Thomas Strong Tutte functions of matroids and graphs, Trans. Am. Math. Soc., Volume 334 (1992) no. 1, pp. 317-347 | Article | MR 1080738 | Zbl 0781.05012