✦ LIBER ✦

An Interpretation for the Tutte Polynomial

✍ Scribed by V Reiner

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 204 KB
Volume: 20
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1998.0275

No coin nor oath required. For personal study only.

✦ Synopsis

For any matroid M realizable over Q , we give a combinatorial interpretation of the Tutte polynomial T M (x, y) which generalizes many of its known interpretations and specializations, including Tutte's coloring and flow interpretations of T M (1t, 0), T M (0, 1t); Crapo and Rota's finite field interpretation of T M (1q k , 0); the interpretation in terms of the Whitney corank-nullity polynomial; Greene's interpretation as the weight enumerator of a linear code and its recent generalization to higher weight enumerators by Barg; Jaeger's interpretation in terms of linear code words and dual code words with disjoint support; and Brylawksi and Oxley's two-variable coloring formula.

📜 SIMILAR VOLUMES

The Tutte polynomial

✍ Dominic Welsh 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

This is a close approximation to the content of my lecture. After a brief survey of well known properties, I present some new interpretations relating to random graphs, lattice point enumeration, and chip firing games. I then examine complexity issues and concentrate in particular, on the existence

A Convolution Formula for the Tutte Poly

A Convolution Formula for the Tutte Polynomial

✍ W. Kook; V. Reiner; D. Stanton 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 75 KB

Following Crapo [2], let `(x, y)(M)=x r(M) y r(M\*) , where K=Z[x, y]. Lemma 1. `(x, y) &1 =`(&x, &y).

Splitting Formulas for Tutte Polynomials

✍ Artur Andrzejak 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 371 KB

We present two splitting formulas for calculating the Tutte polynomial of a matroid. The first one is for a generalized parallel connection across a 3-point line of two matroids and the second one is applicable to a 3-sum of two matroids. An important tool used is the bipointed Tutte polynomial of a

Interval Partitions and Activities for t

Interval Partitions and Activities for the Greedoid Tutte Polynomial

✍ Gary Gordon; Elizabeth McMahon 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 184 KB

The Coefficients of the Tutte Polynomial

The Coefficients of the Tutte Polynomial Are Not Unimodal

✍ W. Schwarzler 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 102 KB

W. T. Tutte conjectured that the coefficients \(t_{i, j}\) of his dichromate form unimodal sequences in \(i\) and \(j\) separately. P. D. Seymour and D. J. A. Welsh conjectured more generally that the same holds for the coefficients of the Tutte polynomial of an arbitrary matroid. We show, by an exa

Bicycle Dimension and Special Points of

Bicycle Dimension and Special Points of the Tutte Polynomial

✍ Dirk Vertigan 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 308 KB

For each pair of algebraic numbers (x, y) and each field F, the complexity of computing the Tutte polynomial T(M; x, y) of a matroid M representable over F is determined. This computation is found to be \*P-complete except when (x&1)( y&1)=1 or when |F| divides (x&1)( y&1) and (x, y) is one of the s