The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives

Las Vergnas, Michel 

Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 973-1015

Abstract (VO)

We study the basic algebraic properties of a 3-variable Tutte polynomial the author has associated with a morphism of matroids, more precisely with a matroid strong map, or matroid perspective in the present paper, or, equivalently by the Factorization Theorem, with a matroid together with a distinguished subset of elements. Most algebraic properties of the usual 2-variable Tutte polynomial of a matroid generalize to the 3-variable polynomial. Among specific properties we show that the 3-variable Tutte polynomial of a matroid $M$ pointed by a normal subset can be used to abridge the computation of the 2-variable Tutte polynomial of $M$, and that the 3-variable Tutte polynomial of a matroid perspective $M\to M^{\prime }$ is computationally equivalent to the $r\left(M\right)-r\left(M^{\prime }\right)+1$ two-variable Tutte polynomials of the matroids of its Higgs factorization.

Résumé

On étudie les propriétés algébriques fondamentales d’un polynôme de Tutte à 3 variables que l’auteur a associé à un morphisme de matroïdes - plus précisément à un morphisme fort, ou perspective dans le présent article, ou encore, de façon équivalente d’après le Théorème de Factorisation, à un matroïde muni d’un sous-ensemble distingué d’éléments. La plupart des propriétés algébriques du polynôme de Tutte habituel à 2 variables se généralisent au polynôme à 3 variables. Parmi les propriétés spécifiques on montre que le polynôme à 3 variables d’un matroïde $M$ pointé par un sous-ensemble normal peut être utilisé pour raccourcir le calcul du polynôme de Tutte (à 2 variables) de $M$, et que le polynôme de Tutte à 3 variables d’une perspective de matroïdes $M\to M^{\prime }$ est équivalent pour le calcul aux $r\left(M\right)-r\left(M^{\prime }\right)+1$ polynômes de Tutte à 2 variables des matroïdes de sa factorisation de Higgs.

Détail

DOI : 10.5802/aif.1702