×

zbMATH — the first resource for mathematics

Simplicial matrix-tree theorems. (English) Zbl 1207.05227
Summary: We generalize the definition and enumeration of spanning trees from the setting of graphs to that of arbitrary-dimensional simplicial complexes \( \Delta\), extending an idea due to G. Kalai. We prove a simplicial version of the Matrix-Tree Theorem that counts simplicial spanning trees, weighted by the squares of the orders of their top-dimensional integral homology groups, in terms of the Laplacian matrix of \( \Delta\). As in the graphic case, one can obtain a more finely weighted generating function for simplicial spanning trees by assigning an indeterminate to each vertex of \( \Delta\) and replacing the entries of the Laplacian with Laurent monomials. When \( \Delta\) is a shifted complex, we give a combinatorial interpretation of the eigenvalues of its weighted Laplacian and prove that they determine its set of faces uniquely, generalizing known results about threshold graphs and unweighted Laplacian eigenvalues of shifted complexes.

MSC:
05E45 Combinatorial aspects of simplicial complexes
05A15 Exact enumeration problems, generating functions
05E99 Algebraic combinatorics
05C05 Trees
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
57M15 Relations of low-dimensional topology with graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Ron M. Adin, Counting colorful multi-dimensional trees, Combinatorica 12 (1992), no. 3, 247 – 260. · Zbl 0773.05038
[2] Eric Babson and Isabella Novik, Face numbers and nongeneric initial ideals, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 25, 23. · Zbl 1085.52004
[3] Matthias Beck and Serkan Hoşten, Cyclotomic polytopes and growth series of cyclotomic lattices, Math. Res. Lett. 13 (2006), no. 4, 607 – 622. · Zbl 1175.11030
[4] L. W. Beineke and R. E. Pippert, Properties and characterizations of \?-trees, Mathematika 18 (1971), 141 – 151. · Zbl 0221.05057
[5] Anders Björner and Gil Kalai, An extended Euler-Poincaré theorem, Acta Math. 161 (1988), no. 3-4, 279 – 303. · Zbl 0667.52008
[6] A. Björner, L. Lovász, S. T. Vrećica, and R. T. Živaljević, Chessboard complexes and matching complexes, J. London Math. Soc. (2) 49 (1994), no. 1, 25 – 39. · Zbl 0790.57014
[7] Ethan D. Bolker, Simplicial geometry and transportation polytopes, Trans. Amer. Math. Soc. 217 (1976), 121 – 142. · Zbl 0322.55033
[8] Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. · Zbl 0902.05016
[9] Arthur Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376-378. · JFM 21.0687.01
[10] A. K. Dewdney, Higher-dimensional tree structures, J. Combinatorial Theory Ser. B 17 (1974), 160 – 169. · Zbl 0272.05125
[11] Xun Dong and Michelle L. Wachs, Combinatorial Laplacian of the matching complex, Electron. J. Combin. 9 (2002), no. 1, Research Paper 17, 11. · Zbl 0985.05052
[12] Art M. Duval, A relative Laplacian spectral recursion, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 26, 19. · Zbl 1085.15008
[13] Art M. Duval and Victor Reiner, Shifted simplicial complexes are Laplacian integral, Trans. Amer. Math. Soc. 354 (2002), no. 11, 4313 – 4344. · Zbl 1016.05052
[14] Richard Ehrenborg and Stephanie van Willigenburg, Enumerative properties of Ferrers graphs, Discrete Comput. Geom. 32 (2004), no. 4, 481 – 492. · Zbl 1055.05151
[15] Sara Faridi, The facet ideal of a simplicial complex, Manuscripta Math. 109 (2002), no. 2, 159 – 174. · Zbl 1005.13006
[16] Miroslav Fiedler and Jiří Sedláček, Über Wurzelbasen von gerichteten Graphen, Časopis Pěst. Mat. 83 (1958), 214 – 225 (Czech, with Russian and German summaries). · Zbl 0084.19501
[17] Joel Friedman and Phil Hanlon, On the Betti numbers of chessboard complexes, J. Algebraic Combin. 8 (1998), no. 2, 193 – 203. · Zbl 0914.55013
[18] Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. · Zbl 1044.55001
[19] Jürgen Herzog and Enzo Maria Li Marzi, Bounds for the Betti numbers of shellable simplicial complexes and polytopes, Commutative algebra and algebraic geometry (Ferrara), Lecture Notes in Pure and Appl. Math., vol. 206, Dekker, New York, 1999, pp. 157 – 167. · Zbl 0941.52013
[20] Gil Kalai, Enumeration of \?-acyclic simplicial complexes, Israel J. Math. 45 (1983), no. 4, 337 – 351. · Zbl 0535.57011
[21] Gil Kalai, Algebraic shifting, Computational commutative algebra and combinatorics (Osaka, 1999) Adv. Stud. Pure Math., vol. 33, Math. Soc. Japan, Tokyo, 2002, pp. 121 – 163. · Zbl 1034.57021
[22] G. Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. Chem. 72 (1847), 497-508.
[23] Caroline Klivans, Obstructions to shiftedness, Discrete Comput. Geom. 33 (2005), no. 3, 535 – 545. · Zbl 1059.05010
[24] W. Kook, V. Reiner, and D. Stanton, Combinatorial Laplacians of matroid complexes, J. Amer. Math. Soc. 13 (2000), no. 1, 129 – 148. · Zbl 0940.05021
[25] N. V. R. Mahadev and U. N. Peled, Threshold graphs and related topics, Annals of Discrete Mathematics, vol. 56, North-Holland Publishing Co., Amsterdam, 1995. · Zbl 0852.05001
[26] Jeremy L. Martin and Victor Reiner, Cyclotomic and simplicial matroids, Israel J. Math. 150 (2005), 229 – 240. · Zbl 1124.05023
[27] Jeremy L. Martin and Victor Reiner, Factorization of some weighted spanning tree enumerators, J. Combin. Theory Ser. A 104 (2003), no. 2, 287 – 300. · Zbl 1032.05084
[28] Gregor Masbaum and Arkady Vaintrob, A new matrix-tree theorem, Int. Math. Res. Not. 27 (2002), 1397 – 1426. · Zbl 1008.05100
[29] J. W. Moon, Counting labelled trees, From lectures delivered to the Twelfth Biennial Seminar of the Canadian Mathematical Congress (Vancouver, vol. 1969, Canadian Mathematical Congress, Montreal, Que., 1970. · Zbl 0214.23204
[30] Gerald Allen Reisner, Cohen-Macaulay quotients of polynomial rings, Advances in Math. 21 (1976), no. 1, 30 – 49. · Zbl 0345.13017
[31] Jeffery B. Remmel and S. Gill Williamson, Spanning trees and function classes, Electron. J. Combin. 9 (2002), no. 1, Research Paper 34, 24. · Zbl 1005.05015
[32] Richard P. Stanley, Combinatorics and commutative algebra, 2nd ed., Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1996. · Zbl 0838.13008
[33] Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. · Zbl 0889.05001
[34] Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. · Zbl 0928.05001
[35] Vladimir Turaev, Introduction to combinatorial torsions, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2001. Notes taken by Felix Schlenk. · Zbl 0970.57001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.