×
Bajo, Carlos; Burdick, Bradley; Chmutov, Sergei

On the Tutte-Krushkal-Renardy polynomial for cell complexes. (English) Zbl 1281.05132

J. Comb. Theory, Ser. A 123, 186-201 (2014).
Summary: Recently V. Krushkal and D. Renardy [“A polynomial invariant and duality for triangulations”, Preprint, arXiv1012.1310v2] generalized the Tutte polynomial from graphs to cell complexes. We show that evaluating this polynomial at the origin gives the number of cellular spanning trees in the sense of A. Duval et al. [Trans. Am. Math. Soc. 361, No. 11, 6073–6114 (2009; Zbl 1207.05227); Adv. Appl. Math. 46, No. 1–4, 247–274 (2011; Zbl 1227.05166)]. Moreover, after a slight modification, the Tutte-Krushkal-Renardy polynomial evaluated at the origin gives a weighted count of cellular spanning trees, and therefore its free term can be calculated by the cellular matrix-tree theorem of Duval et al. In the case of cell decompositions of a sphere, this modified polynomial satisfies the same duality identity as the original polynomial. We find that evaluating the Tutte-Krushkal-Renardy along a certain line gives the Bott polynomial. Finally we prove skein relations for the Tutte-Krushkal-Renardy polynomial.

Cited in 2 Reviews
Cited in 7 Documents

MSC:

05E45 Combinatorial aspects of simplicial complexes
05A15 Exact enumeration problems, generating functions
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C31 Graph polynomials

Keywords:

cell complexes; Tutte polynomial; Krushkal-Renardy polynomial; cellular spanning trees; duality; Bott polynomial

Citations:

Zbl 1207.05227; Zbl 1227.05166
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Beck, M.; Kemper, Y., Flows on simplicial complexes, (24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012). 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), Discrete Math. Theor. Comput. Sci. (2012)), 817-826 · Zbl 1412.05228
[2] Bokowski, J.; Cara, P.; Mock, S., On a self dual 3-sphere of Peter McMullen, Period. Math. Hungar., 39, 17-32 (1999) · Zbl 1062.52015
[3] Bollobás, B., Modern Graph Theory, Grad. Texts in Math., vol. 184 (1998), Springer: Springer New York · Zbl 0902.05016
[4] Bollobás, B.; Riordan, O., A polynomial of graphs on surfaces, Math. Ann., 323, 81-96 (2002) · Zbl 1004.05021
[5] Bott, R., Two new combinatorial invariants for polyhedra, Portugualiae Math., 11, 35-40 (1952) · Zbl 0047.42003
[6] Bott, R., Reflections of the theme of the posters, (Topological Methods in Modern Mathematics, A Symposium in Honor of John Milnorʼs Sixtieth Birthday (1993), Goldberg and Phillips), 125-135 · Zbl 0817.57003
[7] Brändén, P.; Moci, L., The multivariate arithmetic Tutte polynomial, To appear in Trans. Amer. Math. Soc · Zbl 1300.05133
[8] Coxeter, H. S.M., Regular Polytopes (1973), Dover · Zbl 0031.06502
[9] DʼAdderio, M.; Moci, L., Arithmetic matroids, Tutte polynomial, and toric arrangements, Adv. Math., 232, 1, 335-367 (2013) · Zbl 1256.05039
[10] Duval, A.; Klivans, C.; Martin, J., Cellular matrix-tree theorems, Trans. Amer. Math. Soc., 361, 11, 6073-6114 (2009) · Zbl 1207.05227
[11] Duval, A.; Klivans, C.; Martin, J., Cellular spanning trees and Laplacians of cubical complexes, Adv. in Appl. Math., 46, 247-274 (2011) · Zbl 1227.05166
[12] Duval, A.; Klivans, C.; Martin, J., Cuts and flows of cell complexes, preprint · Zbl 1294.05087
[13] Godkin, L., Aspheric orientations of simplicial complexes (2012), San Francisco State University, MA Thesis
[14] Hatcher, A., Algebraic Topology (2009), Cambridge University Press
[15] Kalai, G., Enumeration of \(Q\)-acyclic cellular complexes, Israel J. Math., 45, 337-351 (1983) · Zbl 0535.57011
[16] Krushkal, V., Graphs, links, and duality on surfaces, Combin. Probab. Comput., 20, 267-287 (2011) · Zbl 1211.05029
[17] Krushkal, V.; Renardy, D., A polynomial invariant and duality for triangulations, preprint · Zbl 1301.05381
[18] Masbaum, G.; Vaintrob, A., A new matrix-tree theorem, Int. Math. Res. Not. IMRN, 27, 1397-1426 (2002) · Zbl 1008.05100
[19] Masbaum, G.; Vaintrob, A., Milnor numbers, spanning trees, and the Alexander-Conway polynomial, Adv. Math., 180, 765-797 (2003) · Zbl 1041.57005
[20] Maxwell, M., Enumerating bases of self-dual matroids, J. Combin. Theory Ser. A, 116, 351-378 (2009) · Zbl 1229.05077
[21] Oxley, J., Matroid Theory (2011), Oxford University Press · Zbl 1254.05002
[22] Peterson, A., Enumerations of spanning trees in simplicial complexes, U.U.D.M. Report, 13, 1-57 (2009)
[23] Rourke, C.; Sanderson, B., Introduction to Piecewise-Linear Topology (1972), Springer-Verlag · Zbl 0254.57010
[24] Wang, Z., On Bott polynomials, J. Knot Theory Ramifications, 3, 4, 537-546 (1994) · Zbl 0847.57004
[25] Welsh, D. J.A., Matroid Theory (2010), Academic Press: Dover · Zbl 0343.05002
[26] Whitney, H., A set of topological invariants for graphs, Amer. J. Math., 55, 231-235 (1933) · JFM 59.1235.02
[27] Whitney, H., On the abstract properties of linear dependence, Amer. J. Math., 57, 3, 509-533 (1935) · JFM 61.0073.03
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.