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), p. 973-1015 / Harvested from Numdam

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\rightarrow M^{\prime }$ est équivalent pour le calcul aux $r(M)-r(M^{\prime })+1$ polynômes de Tutte à 2 variables des matroïdes de sa factorisation de Higgs.

Abstract

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\rightarrow M^{\prime }$ is computationally equivalent to the $r(M)-r(M^{\prime })+1$ two-variable Tutte polynomials of the matroids of its Higgs factorization.

Détail

Publié le : 1999-01-01

MR 2000f:05024 | Zbl 0917.05019

DOI : https://doi.org/10.5802/aif.1702

Bibliographie

[1] M. Aigner, Combinatorial Theory, Springer, 1979. | MR 80h:05002 | Zbl 0415.05001

[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 46 #8869 | Zbl 0248.05019

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

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

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

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

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

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

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

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

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

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

[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 84k:05032 | Zbl 0539.05024

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

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

[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 51 #5347 | Zbl 0302.05025

[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 54 #7295 | Zbl 0327.05034

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

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

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

[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 83a:05087 | Zbl 0472.05043

[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 87j:05057 | Zbl 0556.05013

[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 30 #4688 | Zbl 0121.02406

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

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

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

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

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

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