×

On the evaluation at \(( - \iota ,\iota )\) of the Tutte polynomial of a binary matroid. (English) Zbl 1287.05020

The complexity of determining the value of the Tutte polynomial \(T(x,y)\) of a matroid for various choices of \((x,y)\) has been extensively examined. In this paper, it is shown that for binary matroids the evaluation \(T(-\iota,\iota)\) depends on a specific quadratic form associated with the matroid. Using this connection, the paper establishes that \(T(-\iota,\iota)\) can be computed in polynomial time for a binary matroid; related invariants are also computed. Finally the use of these invariants in isomorphism testing for matroids is discussed.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
05C31 Graph polynomials
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Software:

SageMath
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Brown, E.H. Jr.: Generalizations of the Kervaire invariant. Ann. Math. (2) 95, 368-383 (1972) · Zbl 0241.57014 · doi:10.2307/1970804
[2] Geelen, J., Kung, J.P.S., Whittle, G.: Growth rates of minor-closed classes of matroids. J. Comb. Theory, Ser. B 99(2), 420-427 (2009) · Zbl 1229.05072 · doi:10.1016/j.jctb.2008.08.006
[3] Gioan, E., Las Vergnas, M.: On the evaluation at (j,j2) of the Tutte polynomial of a ternary matroid. J. Algebr. Comb. 25(1), 1-6 (2007) · Zbl 1106.05021 · doi:10.1007/s10801-006-0035-2
[4] Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001) · Zbl 0968.05002 · doi:10.1007/978-1-4613-0163-9
[5] Greene, C.: Weight enumeration and the geometry of linear codes. Stud. Appl. Math. 55(2), 119-128 (1976) · Zbl 0331.05019
[6] Haggard, G., Pearce, D.J., Royle, G.: Computing Tutte polynomials. ACM Trans. Math. Softw. 37(3), Art. 24, 17 (2010) · Zbl 1364.05072
[7] Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Philos. Soc. 108(1), 35-53 (1990) · Zbl 0747.57006 · doi:10.1017/S0305004100068936
[8] Jaeger, F.: Tutte polynomials and bicycle dimension of ternary matroids. Proc. Am. Math. Soc. 107(1), 17-25 (1989) · Zbl 0669.05023 · doi:10.1090/S0002-9939-1989-0979049-1
[9] McKay, B. D., Practical graph isomorphism, Winnipeg, Man., 1980
[10] Oxley, J.: Matroid Theory, 2nd edn. Oxford Graduate Texts in Mathematics, vol. 21. Oxford University Press, Oxford (2011) · Zbl 1254.05002
[11] Pendavingh, R.A., van Zwam, S.H.M.: Skew partial fields, multilinear representations of matroids, and a matrix tree theorem. Adv. Appl. Math. 50(1), 201-227 (2013) · Zbl 1256.05047 · doi:10.1016/j.aam.2011.08.003
[12] Rosenstiehl, P., Read, R.C.: On the principal edge tripartition of a graph. Ann. Discrete Math. 3, 195-226 (1978) · Zbl 0392.05059 · doi:10.1016/S0167-5060(08)70508-9
[13] Stein, W.A., et al.: Sage Mathematics Software (Version 4.8.0). The Sage Development Team, 2012. http://www.sagemath.org
[14] Vertigan, D.: Bicycle dimension and special points of the Tutte polynomial. J. Comb. Theory, Ser. B 74(2), 378-396 (1998) · Zbl 1023.05030 · doi:10.1006/jctb.1998.1860
[15] Wood, J.A.: Witt’s extension theorem for mod four valued quadratic forms. Trans. Am. Math. Soc. 336(1), 445-461 (1993) · Zbl 0766.15033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.