On the evaluation at (-ι,ι) of the Tutte polynomial of a binary matroid

被引:1
|
作者
Pendavingh, R. A. [1 ]
机构
[1] Eindhoven Univ Technol, NL-5600 MB Eindhoven, Netherlands
关键词
Matroid; Binary matroid; Tutte polynomial; Computational complexity; BICYCLE DIMENSION;
D O I
10.1007/s10801-013-0442-0
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Vertigan has shown that if M is a binary matroid, then |T (M) (-iota,iota)|, the modulus of the Tutte polynomial of M as evaluated in (-iota,iota), can be expressed in terms of the bicycle dimension of M. In this paper, we describe how the argument of the complex number T (M) (-iota,iota) depends on a certain -valued quadratic form that is canonically associated with M. We show how to evaluate T (M) (-iota,iota) in polynomial time, as well as the canonical tripartition of M and further related invariants.
引用
收藏
页码:141 / 152
页数:12
相关论文
共 50 条