The Tutte polynomial is the most general invariant of matroids and graphs that can be computed recursively by deleting and contracting edges. We generalize this invariant to any class 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, and produce some new convolution formulae. Our principal tools are combinatorial coalgebras and their convolution algebras. Our results generalize in an intrinsic way the recent results of Krajewski--Moffatt--Tanasa.

Dupont C, Fink A, Moci L (2018). Universal Tutte characters via combinatorial coalgebras. ALGEBRAIC COMBINATORICS, 1(5), 603-651 [10.5802/alco.35].

Universal Tutte characters via combinatorial coalgebras

Moci L
2018

Abstract

The Tutte polynomial is the most general invariant of matroids and graphs that can be computed recursively by deleting and contracting edges. We generalize this invariant to any class 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, and produce some new convolution formulae. Our principal tools are combinatorial coalgebras and their convolution algebras. Our results generalize in an intrinsic way the recent results of Krajewski--Moffatt--Tanasa.
2018
Dupont C, Fink A, Moci L (2018). Universal Tutte characters via combinatorial coalgebras. ALGEBRAIC COMBINATORICS, 1(5), 603-651 [10.5802/alco.35].
Dupont C; Fink A; Moci L
File in questo prodotto:
File Dimensione Formato  
ALCO_2018__1_5_603_0.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 864.3 kB
Formato Adobe PDF
864.3 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/676958
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact