✦ LIBER ✦

The Tutte polynomial

✍ Scribed by Dominic Welsh

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 151 KB
Volume: 15
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199910/12)15:3/4<210::aid-rsa2>3.0.co;2-r

No coin nor oath required. For personal study only.

✦ Synopsis

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 of randomized approximation schemes.

📜 SIMILAR VOLUMES

An Interpretation for the Tutte Polynomi

An Interpretation for the Tutte Polynomial

✍ V Reiner 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 204 KB

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 inte

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

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

Irreducibility of the Tutte Polynomial o

Irreducibility of the Tutte Polynomial of a Connected Matroid

✍ C. Merino; A. de Mier; M. Noy 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 117 KB