Universal Tutte characters via combinatorial coalgebras

Dupont, Clément; Fink, Alex; Moci, Luca

Algebraic Combinatorics, Tome 1 (2018) no. 5, pp. 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.

Classification : 16T10, 16T15, 05B35, 05C31
Mots-clés : coalgebra, bialgebra, Tutte polynomial, dichromatic polynomial, Las Vergnas polynomial, Bollobás–Riordan polynomial, arithmetic Tutte polynomial, minors system, convolution formula

[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, CRM Monograph Series, 29, American Mathematical Society, 2010, lii+784 pages | MR | Zbl

[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) | Zbl

[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) | DOI | MR | Zbl

[5] 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

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

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

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

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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR

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

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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | Numdam | MR | Zbl

[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 | DOI | MR | Zbl

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

[36] Oxley, James Matroid theory, Oxford Graduate Texts in Mathematics, 21, Oxford University Press, 2011, xiv+684 pages | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

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

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