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

Michel Las Vergnas

Annales de l'institut Fourier (1999)

  • Volume: 49, Issue: 3, page 973-1015
  • ISSN: 0373-0956

Abstract

top
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 → M ' is computationally equivalent to the r ( M ) - r ( M ' ) + 1 two-variable Tutte polynomials of the matroids of its Higgs factorization.

How to cite

top

Las Vergnas, Michel. "The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives." Annales de l'institut Fourier 49.3 (1999): 973-1015. <http://eudml.org/doc/75373>.

@article{LasVergnas1999,
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.},
author = {Las Vergnas, Michel},
journal = {Annales de l'institut Fourier},
keywords = {matroid; combinatorial geometry; strong map; matroid perspective; Tutte polynomial; normal subset; Higgs lift; Higgs factorization; lattice of flats; Möbius function; modular flat; basis activity},
language = {eng},
number = {3},
pages = {973-1015},
publisher = {Association des Annales de l'Institut Fourier},
title = {The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives},
url = {http://eudml.org/doc/75373},
volume = {49},
year = {1999},
}

TY - JOUR
AU - Las Vergnas, Michel
TI - The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives
JO - Annales de l'institut Fourier
PY - 1999
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 3
SP - 973
EP - 1015
AB - 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.
LA - eng
KW - matroid; combinatorial geometry; strong map; matroid perspective; Tutte polynomial; normal subset; Higgs lift; Higgs factorization; lattice of flats; Möbius function; modular flat; basis activity
UR - http://eudml.org/doc/75373
ER -

References

top
  1. [1] M. AIGNER, Combinatorial Theory, Springer, 1979. Zbl0415.05001MR80h:05002
  2. [2] D. BÉNARD, A. BOUCHET, A. DUCHAMP, On the Martin and Tutte polynomial, J. Combinatorial Theory, ser.B, to appear (26 p.). 
  3. [3] T. BRYLAWSKI, A decomposition for combinatorial geometries, Trans. Amer. Math. Soc., 171 (1972), 235-282. Zbl0224.05007MR46 #8869
  4. [4] T. BRYLAWSKI, Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc., 203 (1975), 1-44. Zbl0299.05023MR50 #9631
  5. [5] T. BRYLAWSKI, A combinatorial perspective on the Radon convexity theorem, Geometriæ Dedicata, 5 (1976), 459-466. Zbl0361.52002MR55 #13340
  6. [6] T. BRYLAWSKI, The broken-circuit complex, Trans. Amer. Math. Soc., 234 (1977), 417-433. Zbl0368.05022MR80a:05055
  7. [7] T. BRYLAWSKI, D. LUCAS, Uniquely representable combinatorial geometries, Teorie Combinatorie (vol. 1), B. Serge ed., Accademia Nazionale dei Lincei, Roma, 1976, 83-108. Zbl0392.51007
  8. [8] T. BRYLAWSKI, J. OXLEY, The Tutte polynomial and its applications, chapter 6 in : White N. (ed.), Matroid Applications, Cambridge University Press, 1992. Zbl0769.05026MR93k:05060
  9. [9] S. CHAIKEN, The Tutte polynomial of a ported matroid, J. Combinatorial Theory, ser. B, 46 (1989), 96-117. Zbl0614.05017MR90d:05066
  10. [10] R. CORDOVIL, M. LAS VERGNAS, A. MANDEL, Euler's relation, Möbius functions, and matroid identities, Geometriæ Dedicata, 12 (1982), 147-162. Zbl0476.52010MR83d:05030
  11. [11] H.H. CRAPO, A higher invariant for matroids, J. Combinatorial Theory, 2 (1967), 406-416. Zbl0168.26203MR35 #6579
  12. [12] H.H. CRAPO, Möbius inversions in lattices, Arch. Math. (Basel), 19 (1968), 595-607. Zbl0208.29303MR39 #6791
  13. [13] H.H. CRAPO, The Tutte polynomial, Aequationes Mathematicæ, 3 (1969), 211-229. Zbl0197.50202MR41 #6705
  14. [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. Zbl1041.05015
  15. [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. Zbl0539.05024MR84k:05032
  16. [16] F. JAEGER, On Tutte polynomials of matroids representable over GF(q), European J. Combinatorics, 10 (1989), 247-255. Zbl0679.05017MR91a:05022
  17. [17] M. LAS VERGNAS, Matroïdes orientables, C.R. Acad. Sci. Paris, sér. A, 280 (1975), 61-64. Zbl0304.05013MR51 #7910
  18. [18] M. LAS VERGNAS, Sur les extensions principales d'un matroïde C.R. Acad. Sci. Paris, sér. A, 280 (1975), 187-190. Zbl0302.05025MR51 #5347
  19. [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. Zbl0327.05034MR54 #7295
  20. [20] M. LAS VERGNAS, Acyclic and totally cyclic orientations of combinatorial geometries, Discrete Mathematics, 20 (1977), 51-61. Zbl0404.05017MR57 #2957
  21. [21] M. LAS VERGNAS, Convexity in oriented matroids, J. Combinatorial Theory, ser. B, 29 (1980), 231-243. Zbl0443.05026MR82f:05027
  22. [22] M. LAS VERGNAS, On the Tutte polynomial of a morphism of matroid, Annals Discrete Mathematics, 8 (1980), 7-20. Zbl0462.05021MR81m:05057
  23. [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. Zbl0472.05043MR83a:05087
  24. [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. Zbl0556.05013MR87j:05057
  25. [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. Zbl0121.02406MR30 #4688
  26. [26] R. STANLEY, Modular elements of geometric lattices, Algebra Universalis, 1 (1971), 214-217. Zbl0229.05032MR45 #5037
  27. [27] R. STANLEY, Acyclic orientations of graphs, Discrete Mathematics, 5 (1973), 171-178. Zbl0258.05113MR47 #6537
  28. [28] W.T. TUTTE, A contribution to the theory of dichromatic polynomials, Canadian J. Math., 6 (1954), 80-91. Zbl0055.17101MR15,814c
  29. [29] W.T. TUTTE, The dichromatic polynomial, Proc. Fifth Bristish Combinatorial Conference (Aberdeen 1975), Utilitas Math., Winnipeg 1976, 605-635. Zbl0339.05105MR53 #186
  30. [30] N. WHITE (ed.), Theory of Matroids, Cambridge University Press, 1986. Zbl0579.00001MR87k:05054
  31. [31] T. ZASLAVSKY, Facing up to arrangements: face-count formulas for partitions of spaces by hyperplanes, Memoirs Amer. Math. Soc., 154 (1975). Zbl0296.50010MR50 #9603

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.