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.

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.

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.

[1] M. Aigner, Combinatorial Theory, Springer, 1979. | MR | Zbl

[2] D. Bénard, A. Bouchet, A. Duchamp, On the Martin and Tutte polynomial, J. Combinatorial Theory, ser.B, to appear (26 p.).

[3] T. Brylawski, A decomposition for combinatorial geometries, Trans. Amer. Math. Soc., 171 (1972), 235-282. | MR | Zbl

[4] T. Brylawski, Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc., 203 (1975), 1-44. | MR | Zbl

[5] T. Brylawski, A combinatorial perspective on the Radon convexity theorem, Geometriæ Dedicata, 5 (1976), 459-466. | MR | Zbl

[6] T. Brylawski, The broken-circuit complex, Trans. Amer. Math. Soc., 234 (1977), 417-433. | MR | Zbl

[7] T. Brylawski, D. Lucas, Uniquely representable combinatorial geometries, Teorie Combinatorie (vol. 1), B. Serge ed., Accademia Nazionale dei Lincei, Roma, 1976, 83-108. | Zbl

[8] T. Brylawski, J. Oxley, The Tutte polynomial and its applications, chapter 6 in : White N. (ed.), Matroid Applications, Cambridge University Press, 1992. | MR | Zbl

[9] S. Chaiken, The Tutte polynomial of a ported matroid, J. Combinatorial Theory, ser. B, 46 (1989), 96-117. | MR | Zbl

[10] R. Cordovil, M. Las Vergnas, A. Mandel, Euler's relation, Möbius functions, and matroid identities, Geometriæ Dedicata, 12 (1982), 147-162. | MR | Zbl

[11] H.H. Crapo, A higher invariant for matroids, J. Combinatorial Theory, 2 (1967), 406-416. | MR | Zbl

[12] H.H. Crapo, Möbius inversions in lattices, Arch. Math. (Basel), 19 (1968), 595-607. | MR | Zbl

[13] H.H. Crapo, The Tutte polynomial, Aequationes Mathematicæ, 3 (1969), 211-229. | MR | Zbl

[14] G. Etienne, M. Las Vergnas, The Tutte polynomial of a morphism of matroids, III. Vectorial matroids, 19 pp., J. Combinatorial Theory, ser. B, to appear.

[15] C. Greene, T. Zaslavsky, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions and orientations of graphs, Trans. Amer. Math. Soc., 280 (1983), 97-126. | MR | Zbl

[16] F. Jaeger, On Tutte polynomials of matroids representable over GF(q), European J. Combinatorics, 10 (1989), 247-255. | MR | Zbl

[17] M. Las Vergnas, Matroïdes orientables, C.R. Acad. Sci. Paris, sér. A, 280 (1975), 61-64. | MR | Zbl

[18] M. Las Vergnas, Sur les extensions principales d'un matroïde C.R. Acad. Sci. Paris, sér. A, 280 (1975), 187-190. | MR | Zbl

[19] M. Las Vergnas, Extensions normales d'un matroïde, polynôme de Tutte d'un morphisme, C.R. Acad. Sci. Paris, sér. A, 280 (1975), 1479-1482. | MR | Zbl

[20] M. Las Vergnas, Acyclic and totally cyclic orientations of combinatorial geometries, Discrete Mathematics, 20 (1977), 51-61. | MR | Zbl

[21] M. Las Vergnas, Convexity in oriented matroids, J. Combinatorial Theory, ser. B, 29 (1980), 231-243. | MR | Zbl

[22] M. Las Vergnas, On the Tutte polynomial of a morphism of matroid, Annals Discrete Mathematics, 8 (1980), 7-20. | MR | Zbl

[23] M. Las Vergnas, Eulerian circuits of 4-valent graphs imbedded in surfaces, in: L. Lovász & V. Sós (eds.), Algebraic Methods in Graph Theory, North-Holland, 1981, 451-478. | MR | Zbl

[24] M. Las Vergnas, The Tutte polynomial of a morphism of matroids, II. Activities of orientations, in: J.A. Bondy & U.S.R. Murty (eds.), Progress in Graph Theory, Academic Press, 1984, 367-380. | MR | Zbl

[25] G-C. Rota, On the foundations of combinatorial theory. I: Theory of Möbius functions, Z. für Wahrscheinlichkeitstheorie und verw. Gebiete, 2 (1964), 340-368. | MR | Zbl

[26] R. Stanley, Modular elements of geometric lattices, Algebra Universalis, 1 (1971), 214-217. | MR | Zbl

[27] R. Stanley, Acyclic orientations of graphs, Discrete Mathematics, 5 (1973), 171-178. | MR | Zbl

[28] W.T. Tutte, A contribution to the theory of dichromatic polynomials, Canadian J. Math., 6 (1954), 80-91. | MR | Zbl

[29] W.T. Tutte, The dichromatic polynomial, Proc. Fifth Bristish Combinatorial Conference (Aberdeen 1975), Utilitas Math., Winnipeg 1976, 605-635. | MR | Zbl

[30] N. White (ed.), Theory of Matroids, Cambridge University Press, 1986. | MR | Zbl

[31] T. Zaslavsky, Facing up to arrangements: face-count formulas for partitions of spaces by hyperplanes, Memoirs Amer. Math. Soc., 154 (1975). | MR | Zbl