BICYCLE DIMENSION AND SPECIAL POINTS OF THE TUTTE POLYNOMIAL

For each pair of algebraic numbers (x, y) and each field F, the comple xity of computing the Tutte polynomial T(M; x, y) of a matroid M repre sentable over F is determined. This computation is found to be <(#P)ov er bar>-complete except when (x - 1)(y - 1) = 1 or when \F\ divides (x - 1)(y - 1) and (x, y) is one of the seven points (0, -1), (-1, 0), ( i, - i), (-i, i), (j, j(2)), (j(2), j) or (-1, -1), where j = e(2 pi i /3). Expressions are given for the Tutte polynomial in the exceptional cases. These expressions involve the bicycle dimension of M over F. A related result determines when this bicycle dimension is well defined . (C) 1998 Academic Press.