logo ANNALES DE L'INSTITUT FOURIER

With cedram.org
Table of contents for this issue | Previous article | Next article
Michel Las Vergnas
The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives
Annales de l'institut Fourier, 49 no. 3 (1999), p. 973-1015, doi: 10.5802/aif.1702
Article PDF | Reviews MR 2000f:05024 | Zbl 0917.05019

Résumé - 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.

Bibliography

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