The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives
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→M′ est équivalent pour le calcul aux r(M)-r(M′)+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→M′ is computationally equivalent to the r(M)-r(M′)+1 two-variable Tutte polynomials of the matroids of its Higgs factorization.

@article{AIF_1999__49_3_973_0,
     author = {Las Vergnas, Michel},
     title = {The {Tutte} polynomial of a morphism of matroids {I.} {Set-pointed} matroids and matroid perspectives},
     journal = {Annales de l'Institut Fourier},
     pages = {973--1015},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {49},
     number = {3},
     year = {1999},
     doi = {10.5802/aif.1702},
     mrnumber = {2000f:05024},
     zbl = {0917.05019},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/aif.1702/}
}
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
SP  - 973
EP  - 1015
VL  - 49
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - https://www.numdam.org/articles/10.5802/aif.1702/
DO  - 10.5802/aif.1702
LA  - en
ID  - AIF_1999__49_3_973_0
ER  - 
%0 Journal Article
%A Las Vergnas, Michel
%T The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives
%J Annales de l'Institut Fourier
%D 1999
%P 973-1015
%V 49
%N 3
%I Association des Annales de l’institut Fourier
%U https://www.numdam.org/articles/10.5802/aif.1702/
%R 10.5802/aif.1702
%G en
%F AIF_1999__49_3_973_0
Las Vergnas, Michel. The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 973-1015. doi : 10.5802/aif.1702. https://www.numdam.org/articles/10.5802/aif.1702/

[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

  • Pierson, Laura On the Compatible Sets Expansion of the Tutte Polynomial, Annals of Combinatorics, Volume 28 (2024) no. 1, p. 33 | DOI:10.1007/s00026-023-00657-z
  • Kochol, Martin One-to-one correspondence between interpretations of the Tutte polynomials, Journal of Combinatorial Theory, Series B, Volume 162 (2023), p. 134 | DOI:10.1016/j.jctb.2023.05.002
  • Kochol, Martin Interpretations for the Tutte polynomials of morphisms of matroids, Discrete Applied Mathematics, Volume 322 (2022), p. 210 | DOI:10.1016/j.dam.2022.08.026
  • Gioan, Emeric On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids, Discrete Mathematics, Volume 345 (2022) no. 7, p. 112796 | DOI:10.1016/j.disc.2022.112796
  • Goodall, Andrew; Litjens, Bart; Regts, Guus; Vena, Lluís Tutte’s dichromate for signed graphs, Discrete Applied Mathematics, Volume 289 (2021), p. 153 | DOI:10.1016/j.dam.2020.09.021
  • Dinu, Rodica; Eur, Christopher; Seynnaeve, Tim K-theoretic Tutte polynomials of morphisms of matroids, Journal of Combinatorial Theory, Series A, Volume 181 (2021), p. 105414 | DOI:10.1016/j.jcta.2021.105414
  • Eur, Christopher; Huh, June Logarithmic concavity for morphisms of matroids, Advances in Mathematics, Volume 367 (2020), p. 107094 | DOI:10.1016/j.aim.2020.107094
  • Kayibi, Koko K.; Samee, U.; Pirzada, S. Cyclic flats and corners of the linking polynomial, Acta Universitatis Sapientiae, Mathematica, Volume 10 (2018) no. 1, p. 189 | DOI:10.2478/ausm-2018-0016
  • Krajewski, Thomas; Moffatt, Iain; Tanasa, Adrian Hopf algebras and Tutte polynomials, Advances in Applied Mathematics, Volume 95 (2018), p. 271 | DOI:10.1016/j.aam.2017.12.001
  • Kayibi, Koko K.; Pirzada, S. On the activities of p-basis of matroid perspectives, Discrete Mathematics, Volume 339 (2016) no. 6, p. 1629 | DOI:10.1016/j.disc.2016.01.013
  • Butler, Clark; Chmutov, Sergei Bollobás–Riordan and Relative Tutte Polynomials, Arnold Mathematical Journal, Volume 1 (2015) no. 3, p. 283 | DOI:10.1007/s40598-015-0021-7
  • Ellis-Monaghan, Joanna A.; Moffatt, Iain The Las Vergnas polynomial for embedded graphs, European Journal of Combinatorics, Volume 50 (2015), p. 97 | DOI:10.1016/j.ejc.2015.03.009
  • DIAO, Y.; HETYEI, G. Relative Tutte Polynomials of Tensor Products of Coloured Graphs, Combinatorics, Probability and Computing, Volume 22 (2013) no. 6, p. 801 | DOI:10.1017/s0963548313000370
  • Las Vergnas, Michel The Tutte polynomial of a morphism of matroids — 5. Derivatives as generating functions of Tutte activities, European Journal of Combinatorics, Volume 34 (2013) no. 8, p. 1390 | DOI:10.1016/j.ejc.2013.05.003
  • Welsh, D.J.A.; Kayibi, K.K. Corrigendum to “A linking polynomial of two matroids” [Adv. in Appl. Math. 32 (1–2) (2004) 391–419], Advances in Applied Mathematics, Volume 49 (2012) no. 1, p. 78 | DOI:10.1016/j.aam.2012.04.001
  • DIAO, Y.; HETYEI, G. Relative Tutte Polynomials for Coloured Graphs and Virtual Knot Theory, Combinatorics, Probability and Computing, Volume 19 (2010) no. 3, p. 343 | DOI:10.1017/s0963548309990484
  • Kayibi, Koko Kalambay A decomposition theorem for the linking polynomial of two matroids, Discrete Mathematics, Volume 308 (2008) no. 4, p. 583 | DOI:10.1016/j.disc.2007.03.026
  • Las Vergnas, Michel A parity result of Fraysseix, computational complexity of Tutte polynomials, and a conjecture on planar graphs, Electronic Notes in Discrete Mathematics, Volume 31 (2008), p. 119 | DOI:10.1016/j.endm.2008.06.024
  • Etienne, Gwihen; Las Vergnas, Michel The Tutte polynomial of a morphism of matroids, Advances in Applied Mathematics, Volume 32 (2004) no. 1-2, p. 198 | DOI:10.1016/s0196-8858(03)00080-0
  • Welsh, D.J.A.; Kayibi, K.K. A linking polynomial of two matroids, Advances in Applied Mathematics, Volume 32 (2004) no. 1-2, p. 391 | DOI:10.1016/s0196-8858(03)00091-5

Cité par 20 documents. Sources : Crossref