×

The Tutte polynomial of a morphism of matroids. IV: Computational complexity. (English) Zbl 1137.05019

Summary: We determine the easy points of the 3-variable Tutte polynomial of a matroid perspective. It turns out that all but one of the sporadic easy points of the 3-variable Tutte polynomial proceed from the 8 sporadic easy points determined in the seminal paper of Jaeger-Vertigan-Welsh on the computational complexity of the Tutte polynomial of a matroid. The exceptional easy point, namely \((-1,-1,-1)\), can be evaluated with polynomial complexity for binary matroid perspectives by a previous result of the author.
[For part III see G. Etienne and the author, Adv. Appl. Math. 32, No. 1–2, 198–211 (2004; Zbl 1041.05015).]

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices

Citations:

Zbl 1041.05015
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brylawski, T. - A decomposition for combinatorial geometries, Trans. Amer. Math. Soc., 171 (1972), 235-282. · Zbl 0224.05007 · doi:10.2307/1996381
[2] Brylawski, T. and Oxley, J. - The Tutte polynomial and its applications, chap. 6 in “Matroid Applications” (N. White, Ed.), Cambridge University Press (1992), 123-225. · Zbl 0769.05026
[3] Chaiken, S. - The Tutte polynomial of a ported matroid, J. Combin. Theory Ser. B, 46 (1989), 96-117. · Zbl 0614.05017 · doi:10.1016/0095-8956(89)90010-5
[4] Etienne, G. and Las Vergnas, M. - The Tutte polynomial of a morphism of matroids, 3. Vectorial matroids, Advances in Applied Mathematics, 32 (2004), 198-211. · Zbl 1041.05015 · doi:10.1016/S0196-8858(03)00080-0
[5] Gioan, E. and Las Vergnas, M. - On the evaluation at (j, j2) of the Tutte polynomial of a ternary matroid, J. Algebraic Combin., 25 (2007), 1-6. 309 · Zbl 1106.05021 · doi:10.1007/s10801-006-0035-2
[6] Jaeger, F.; Vertigan, D.L. and Welsh, D.J.A. - On the computational com- plexity of the Jones and Tutte polynomial, Math. Proc. Camb. Phil. Soc., 108 (1990), 35-53. · Zbl 0747.57006 · doi:10.1017/S0305004100068936
[7] Kung, J.P.S. - Strong maps, chap. 8 in “Theory of Matroids” (N. White, Ed.), Cambridge Univeristy Press, 1986, pp. 224-253.
[8] Las Vergnas, M. - Extensions normales d’un matroïde, polyn\hat ome de Tutte d’un morphisme, C.R. Acad. Sci. Paris sér. A, 280 (1975), 1479-1482. · Zbl 0327.05034
[9] Las Vergnas, M. - Acyclic and totally cyclic orientations of combinatorial ge- ometries, Discrete Mathematics, 20 (1977), 51-61. · Zbl 0404.05017 · doi:10.1016/0012-365X(77)90042-5
[10] Las Vergnas, M. - On the Tutte polynomial of a morphism of matroids, Annals Discrete Mathematics, 8 (1980), 7-20. · Zbl 0462.05021 · doi:10.1016/S0167-5060(08)70841-0
[11] Las Vergnas, M. - The Tutte polynomial of a morphism of matroids, 1. Set- pointed matroids and matroid perspectives, Annales de l’Institut Fourier, 49 (1999), 973-1015. · Zbl 0917.05019 · doi:10.5802/aif.1702
[12] Oxley, J.G. - Matroid Theory, Oxford Science Publications, 1992.
[13] Welsh, D.J.A. and Kayibi, K.K. - A linking polynomial of two matroids, Advances in Applied Mathematics, 32 (2004), 391-419. · Zbl 1041.05020 · doi:10.1016/S0196-8858(03)00091-5
[14] Welsh, D.J.A. and Kayibi, K.K. - A linking polynomial of two matroids: acknowledgement, Advances in Applied Mathematics, to appear. · Zbl 1041.05020 · doi:10.1016/S0196-8858(03)00091-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.