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.
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.35
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}, pages = {603--651}, publisher = {MathOA foundation}, volume = {1}, number = {5}, year = {2018}, doi = {10.5802/alco.35}, zbl = {06987760}, mrnumber = {3887405}, language = {en}, url = {http://archive.numdam.org/articles/10.5802/alco.35/} }
TY - JOUR AU - Dupont, Clément AU - Fink, Alex AU - Moci, Luca TI - Universal Tutte characters via combinatorial coalgebras JO - Algebraic Combinatorics PY - 2018 SP - 603 EP - 651 VL - 1 IS - 5 PB - MathOA foundation UR - http://archive.numdam.org/articles/10.5802/alco.35/ DO - 10.5802/alco.35 LA - en ID - ALCO_2018__1_5_603_0 ER -
%0 Journal Article %A Dupont, Clément %A Fink, Alex %A Moci, Luca %T Universal Tutte characters via combinatorial coalgebras %J Algebraic Combinatorics %D 2018 %P 603-651 %V 1 %N 5 %I MathOA foundation %U http://archive.numdam.org/articles/10.5802/alco.35/ %R 10.5802/alco.35 %G en %F 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. http://archive.numdam.org/articles/10.5802/alco.35/
[1] Hopf monoids and generalized permutahedra (2017) (https://arxiv.org/abs/1709.07504)
[2] Monoidal functors, species and Hopf algebras, CRM Monograph Series, 29, American Mathematical Society, 2010, lii+784 pages | MR | Zbl
[3] A convolution formula for Tutte polynomials of arithmetic matroids and other combinatorial structures (2016) (https://arxiv.org/abs/1602.02664) | Zbl
[4] 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] A polynomial of graphs on surfaces, Math. Ann., Volume 323 (2002) no. 1, pp. 81-96 | DOI | MR | Zbl
[6] Greedy algorithm and symmetric matroids, Math. Program., Volume 38 (1987) no. 2, pp. 147-159 | DOI | MR | Zbl
[7] Maps and -matroids, Discrete Math., Volume 78 (1989) no. 1-2, pp. 59-71 | DOI | MR | Zbl
[8] The multivariate arithmetic Tutte polynomial, Trans. Am. Math. Soc., Volume 366 (2014) no. 10, pp. 5523-5540 | DOI | MR | Zbl
[9] A decomposition for combinatorial geometries, Trans. Am. Math. Soc., Volume 171 (1972), pp. 235-282 | DOI | MR | Zbl
[10] A quasi-tree expansion of the Krushkal polynomial, Adv. Appl. Math., Volume 94 (2016), pp. 3-22 | DOI | MR | Zbl
[11] The Tutte polynomial of a ported matroid, J. Comb. Theory, Ser. B, Volume 46 (1989) no. 1, pp. 96-117 | DOI | MR | Zbl
[12] Constructions in Combinatorial Geometry, Lecture Notes for the Combinatorial Theory Advanced Science Seminar, Bowdoin College. Brunswick, ME (1971)
[13] Arithmetic matroids, the Tutte polynomial and toric arrangements, Adv. Math., Volume 232 (2013) no. 1, pp. 335-367 | DOI | MR | Zbl
[14] 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] 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] 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] Submodular functions, matroids, and certain polyhedra, Combinatorial structures and their applications (Calgary, 1969), Gordon and Breach, 1970 | Zbl
[18] External and internal elements of a matroid basis, Discrete Math., Volume 179 (1998) no. 1-3, pp. 111-119 | DOI | MR | Zbl
[19] Matroids over a ring, J. Eur. Math. Soc., Volume 18 (2016) no. 4, pp. 681-731 | DOI | MR | Zbl
[20] On the random-cluster model. I. Introduction and relation to other models, Physica, Volume 57 (1972), pp. 536-564 | DOI | MR
[21] Strong maps of geometries, J. Comb. Theory, Volume 5 (1968), pp. 185-191 | DOI | MR | Zbl
[22] Coalgebras and bialgebras in combinatorics, Stud. Appl. Math., Volume 61 (1979) no. 2, pp. 93-139 | DOI | MR | Zbl
[23] Une théorie combinatoire des séries formelles, Adv. Math., Volume 42 (1981) no. 1, pp. 1-82 | DOI | MR | Zbl
[24] A decomposition theorem for the linking polynomial of two matroids, Discrete Math., Volume 308 (2008) no. 4, pp. 583-596 | DOI | MR | Zbl
[25] On the activities of -basis of matroid perspectives, Discrete Math., Volume 339 (2016) no. 6, pp. 1629-1639 | DOI | MR | Zbl
[26] A convolution formula for the Tutte polynomial, J. Comb. Theory, Ser. B, Volume 76 (1999) no. 2, pp. 297-300 | DOI | MR | Zbl
[27] Hopf algebras and Tutte polynomials, Adv. Appl. Math., Volume 95 (2018), pp. 271-330 | DOI | MR | Zbl
[28] Graphs, links, and duality on surfaces, Comb. Probab. Comput., Volume 20 (2011) no. 2, pp. 267-287 | DOI | MR | Zbl
[29] Strong maps, Theory of matroids (Encyclopedia of Mathematics and Its Applications), Volume 26, Cambridge University Press, 1986, pp. 224-253 | DOI | MR | Zbl
[30] 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] 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] 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] -Tutte polynomials and abelian Lie group arrangements (2017) (https://arxiv.org/abs/1707.04551)
[34] A Tutte polynomial for toric arrangements, Trans. Am. Math. Soc., Volume 364 (2012) no. 2, pp. 1067-1088 | DOI | MR | Zbl
[35] Matroidal frameworks for topological Tutte polynomials, J. Comb. Theory, Ser. B, Volume 133 (2018), pp. 1-31 | DOI | MR | Zbl
[36] Matroid theory, Oxford Graduate Texts in Mathematics, 21, Oxford University Press, 2011, xiv+684 pages | DOI | MR | Zbl
[37] 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] Permutohedra, associahedra, and beyond, Int. Math. Res. Not., Volume 2009 (2009) no. 6, pp. 1026-1106 | DOI | MR | Zbl
[39] An interpretation for the Tutte polynomial, Eur. J. Comb., Volume 20 (1999) no. 2, pp. 149-161 | DOI | MR | Zbl
[40] Hopf algebras of combinatorial structures, Can. J. Math., Volume 45 (1993) no. 2, pp. 412-428 | DOI | MR | Zbl
[41] Incidence Hopf algebras, Journal of Pure and Applied Algebra, Volume 96 (1994) no. 3, pp. 299-330 | DOI | MR | Zbl
[42] 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] 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] 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] On dichromatic polynomials, J. Comb. Theory, Volume 2 (1967) no. 3, pp. 301-320 | DOI | Zbl
[46] Möbius conjugation and convolution formulae, J. Comb. Theory, Ser. B, Volume 115 (2015), pp. 117-131 | DOI | MR | Zbl
[47] Strong Tutte functions of matroids and graphs, Trans. Am. Math. Soc., Volume 334 (1992) no. 1, pp. 317-347 | DOI | MR | Zbl
Cited by Sources: