<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
Coboundaries, Flows, and Tutte Polynomials of Matrices
Joseph P. S. Kung
Department of Mathematics, University of North Texas, P.O. Box 311430, Denton TX 76203, USA
Annals of Combinatorics 12 (2) p.183-194 June, 2008
AMS Subject Classification: 05B35, 05C10
Using matroid duality and the critical problem, we show that certain evaluations of the Tutte polynomial of a matroid represented as a matrix over a finite field $\mathrm{GF}(q)$ can be interpreted as weighted sums over pairs $f,\,g$ of functions defined from the ground set to $\mathrm{GF}(q)$ whose difference $f-g$ is the restriction of a linear functional on the column
space of the matrix. Similar interpretations are given for the characteristic polynomial evaluated at $q$. These interpretations extend and elaborate interpretations for Tutte and chromatic polynomials of graphs due to Goodall and Matiyasevich.
Keywords: flows, Tutte polynomials, chromatic polynomials


1. T. Brylawski and J.G. Oxley, The Tutte polynomial and its applications, In: Matroid Applications, Cambridge Univ. Press, Cambridge, (1992) pp. 123-–225.

2. A.J. Goodall, Some new evaluation of the Tutte polynomial, J. Combin. Theory Ser. B 96 (2) (2006) 207-–224.

3. A.J. Goodall, Fourier analysis on nite Abelian groups: some graphical applications, In: Combinatorics, Complexity, and Chance, G. Grimmett, C. McDiarmid Eds., Oxford Univ. Press, Oxford, (2007) pp. 103–-129.

4. H.H. Crapo, The Tutte polynomial, Aequationes Math. 3 (1969) 211-–229.

5. H.H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries, MIT Press, Cambridge MA, 1970.

6. J.P.S. Kung, Critical problems, In: Matroid Theory, J.E. Bonin, J.G. Oxley, and B. Servatius Eds., Amer. Math. Soc., Providence RI, (1996) pp. 1–1-27.

7. J.P.S. Kung, Twelve views of matroid theory, In: Combinatorial and Computational Mathematics: Present and Future, S. Hong, J.H. Kwak, K.H. Kim, and F.W. Roush Eds., World Scientic, Singapore, (2001) pp. 56–-96.

8. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.

9. Y. Matiyasevich, Some probabilistic restatements of the four color conjecture, J. Graph Theory 46 (3) (2004) 167-–179.

10. J.G. Oxley, Matroid Theory, Oxford Univ. Press, Oxford, 1992.

11. V. Pless, An Introduction to the Theory of Error-correcting Codes, 3rd Ed., Wiley, New York, 1998.

12. C. Semple and G. Whittle, Partial elds and matroid representation, Adv. Appl. Math. 17 (2) (1996) 184-–208.

13. W.T. Tutte, A ring in graph theory, Proc. Cambridge Philos. Soc. 43 (1947) 26–-40.

14. W.T. Tutte, On dichromatic polynomials, J. Combin. Theory 2 (1967) 301-–320.