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 条
  • [11] Linear relations for a generalized Tutte polynomial
    Gordon, Gary
    ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (01)
  • [12] Series and parallel reductions for the Tutte polynomial
    Traldi, L
    DISCRETE MATHEMATICS, 2000, 220 (1-3) : 291 - 297
  • [13] Fourientations and the Tutte polynomial
    Backman, Spencer
    Hopkins, Sam
    RESEARCH IN THE MATHEMATICAL SCIENCES, 2017, 4
  • [14] On the polymatroid Tutte polynomial
    Guan, Xiaxia
    Yang, Weiling
    Jin, Xian'an
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2024, 201
  • [15] Inapproximability of the Tutte Polynomial
    Goldberg, Leslie Ann
    Jerrum, Mark
    STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, : 459 - 468
  • [16] The Tutte polynomial of a morphism of matroids - III. Vectorial matroids
    Etienne, G
    Vergnas, ML
    ADVANCES IN APPLIED MATHEMATICS, 2004, 32 (1-2) : 198 - 211
  • [17] Fourientations and the Tutte polynomial
    Spencer Backman
    Sam Hopkins
    Research in the Mathematical Sciences, 4
  • [18] On the Evaluation of the Tutte Polynomial at the Points (1, –1) and (2, –1)
    A. J. Goodall
    C. Merino
    A. de Mier
    M. Noy
    Annals of Combinatorics, 2013, 17 : 311 - 332
  • [19] On the Evaluation of the Tutte Polynomial at the Points (1,-1) and (2,-1)
    Goodall, A. J.
    Merino, C.
    de Mier, A.
    Noy, M.
    ANNALS OF COMBINATORICS, 2013, 17 (02) : 311 - 332
  • [20] On the half-plane property and the Tutte group of a matroid
    Branden, Petter
    D'Leon, Rafael S. Gonzalez
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2010, 100 (05) : 485 - 492