The Tutte polynomial of a morphism of matroids 4. Computational complexity

Michel Las Vergnas

Type: Article

Publication Date: 2007-09-30

Citations: 8

DOI: https://doi.org/10.4171/pm/1788

Abstract

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.

Locations

Portugaliae Mathematica - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives	1999	Michel Las Vergnas
+	On the Tutte Polynomial of a Morphism of Matroids	1980	Michel Las Vergnas
+	The Tutte polynomial of a morphism of matroids	2003	Gwihen Etienne Michel Las Vergnas
+	Interpretations for the Tutte polynomials of morphisms of matroids	2022	Martin Kochol
+	The Tutte polynomial of a ported matroid	1989	Seth Chaiken
+	Tutte polynomials for regular oriented matroids	2023	Jordan Awan Olivier Bernardi
+	On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids	2021	Emeric Gioan
+	Tutte polynomials for regular oriented matroids	2022	Jordan Awan Olivier Bernardi
+	The Tutte Polynomial of a Morphism of Matroids 5. Derivatives as Generating Functions of Tutte Activities	2012	Michel Las Vergnas
+	A generalization of the Tutte polynomials	2018	Tsuyoshi Miezaki Manabu Oura Tadashi Sakuma Hidehiro Shinohara
+ PDF Chat	A generalization of the Tutte polynomials	2019	Tsuyoshi Miezaki Manabu Oura Tadashi Sakuma Hidehiro Shinohara
+	Matroids and the Tutte polynomial	2018	Scott Corry David Perkinson
+	Set of independencies and Tutte polynomial of matroids over a domain	2019	Alessio Borzì Ivan Martino
+ PDF Chat	On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids	2022	Emeric Gioan
+	The Tutte polynomial of a morphism of matroids — 5. Derivatives as generating functions of Tutte activities	2013	Michel Las Vergnas
+	The Tutte Polynomial of a Morphism of Matroids 6. A Multi-Faceted Counting Formula for Hyperplane Regions and Acyclic Orientations	2012	Michel Las Vergnas
+	Irreducibility of the Tutte Polynomial of a Connected Matroid	2001	Criel Merino Anna de Mier Marc Noy
+ PDF Chat	Tutte polynomials of matroids as universal valuative invariants	2024	Luis Ferroni Benjamin Schröter
+	On matroids determined by their Tutte polynomials	2005	Anna de Mier Marc Noy
+	The Tutte polynomial of matroid perspectives	2022	Emeric Gioan

Works That Cite This (7)

Action	Title	Year	Authors
+	A parity result of Fraysseix, computational complexity of Tutte polynomials, and a conjecture on planar graphs	2008	Michel Las Vergnas
+	The Tutte polynomial of a morphism of matroids — 5. Derivatives as generating functions of Tutte activities	2013	Michel Las Vergnas
+	Logarithmic concavity for morphisms of matroids	2020	Christopher Eur June Huh
+ PDF Chat	K-theoretic Tutte polynomials of morphisms of matroids	2021	Rodica Dinu Christopher Eur Tim Seynnaeve
+	The Las Vergnas polynomial for embedded graphs	2015	Joanna A. Ellis-Monaghan Iain Moffatt
+	The Tutte Polynomial of a Morphism of Matroids 6. A Multi-Faceted Counting Formula for Hyperplane Regions and Acyclic Orientations	2012	Michel Las Vergnas
+ PDF Chat	Linear relations on the coefficients of the linking polynomial	2016	Koko K. Kayibi S. Pirzada Ahmad M. Alghamdi

Works Cited by This (5)

Action	Title	Year	Authors
+ PDF Chat	On the evaluation at (j, j 2) of the Tutte polynomial of a ternary matroid	2006	Emeric Gioan Michel Las Vergnas
+	A linking polynomial of two matroids	2003	Dominic Welsh Koko K. Kayibi
+	The Tutte polynomial of a ported matroid	1989	Seth Chaiken
+	On the Tutte Polynomial of a Morphism of Matroids	1980	Michel Las Vergnas
+ PDF Chat	A Decomposition for Combinatorial Geometries	1972	Thomas Brylawski