Simplicial matrix-tree theorems

Duval, Art; Klivans, Caroline; Martin, Jeremy

doi:10.1090/S0002-9947-09-04898-3

Simplicial matrix-tree theorems
HTML articles powered by AMS MathViewer

by Art M. Duval, Caroline J. Klivans and Jeremy L. Martin PDF

Trans. Amer. Math. Soc. 361 (2009), 6073-6114 Request permission

Abstract:

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.

References

Ron M. Adin, Counting colorful multi-dimensional trees, Combinatorica 12 (1992), no. 3, 247–260. MR 1195888, DOI 10.1007/BF01285814
Eric Babson and Isabella Novik, Face numbers and nongeneric initial ideals, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 25, 23. MR 2195431
Matthias Beck and Serkan Hoşten, Cyclotomic polytopes and growth series of cyclotomic lattices, Math. Res. Lett. 13 (2006), no. 4, 607–622. MR 2250495, DOI 10.4310/MRL.2006.v13.n4.a10
L. W. Beineke and R. E. Pippert, Properties and characterizations of $k$-trees, Mathematika 18 (1971), 141–151. MR 288046, DOI 10.1112/S0025579300008500
Anders Björner and Gil Kalai, An extended Euler-Poincaré theorem, Acta Math. 161 (1988), no. 3-4, 279–303. MR 971798, DOI 10.1007/BF02392300
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. MR 1253009, DOI 10.1112/jlms/49.1.25
Ethan D. Bolker, Simplicial geometry and transportation polytopes, Trans. Amer. Math. Soc. 217 (1976), 121–142. MR 411983, DOI 10.1090/S0002-9947-1976-0411983-9
Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR 1633290, DOI 10.1007/978-1-4612-0619-4
Arthur Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376–378.
A. K. Dewdney, Higher-dimensional tree structures, J. Combinatorial Theory Ser. B 17 (1974), 160–169. MR 369115, DOI 10.1016/0095-8956(74)90083-5
Xun Dong and Michelle L. Wachs, Combinatorial Laplacian of the matching complex, Electron. J. Combin. 9 (2002), no. 1, Research Paper 17, 11. MR 1912799
Art M. Duval, A relative Laplacian spectral recursion, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 26, 19. MR 2224939
Art M. Duval and Victor Reiner, Shifted simplicial complexes are Laplacian integral, Trans. Amer. Math. Soc. 354 (2002), no. 11, 4313–4344. MR 1926878, DOI 10.1090/S0002-9947-02-03082-9
Richard Ehrenborg and Stephanie van Willigenburg, Enumerative properties of Ferrers graphs, Discrete Comput. Geom. 32 (2004), no. 4, 481–492. MR 2096744, DOI 10.1007/s00454-004-1135-1
Sara Faridi, The facet ideal of a simplicial complex, Manuscripta Math. 109 (2002), no. 2, 159–174. MR 1935027, DOI 10.1007/s00229-002-0293-9
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). MR 0097071
Joel Friedman and Phil Hanlon, On the Betti numbers of chessboard complexes, J. Algebraic Combin. 8 (1998), no. 2, 193–203. MR 1648484, DOI 10.1023/A:1008693929682
Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
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. MR 1702104
Gil Kalai, Enumeration of $\textbf {Q}$-acyclic simplicial complexes, Israel J. Math. 45 (1983), no. 4, 337–351. MR 720308, DOI 10.1007/BF02804017
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. MR 1890098, DOI 10.2969/aspm/03310121
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.
Caroline Klivans, Obstructions to shiftedness, Discrete Comput. Geom. 33 (2005), no. 3, 535–545. MR 2121994, DOI 10.1007/s00454-004-1103-9
W. Kook, V. Reiner, and D. Stanton, Combinatorial Laplacians of matroid complexes, J. Amer. Math. Soc. 13 (2000), no. 1, 129–148. MR 1697094, DOI 10.1090/S0894-0347-99-00316-1
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. MR 1417258
Jeremy L. Martin and Victor Reiner, Cyclotomic and simplicial matroids, Israel J. Math. 150 (2005), 229–240. MR 2255809, DOI 10.1007/BF02762381
Jeremy L. Martin and Victor Reiner, Factorization of some weighted spanning tree enumerators, J. Combin. Theory Ser. A 104 (2003), no. 2, 287–300. MR 2019276, DOI 10.1016/j.jcta.2003.08.003
Gregor Masbaum and Arkady Vaintrob, A new matrix-tree theorem, Int. Math. Res. Not. 27 (2002), 1397–1426. MR 1908476, DOI 10.1155/S1073792802111044
J. W. Moon, Counting labelled trees, Canadian Mathematical Monographs, No. 1, Canadian Mathematical Congress, Montreal, Que., 1970. From lectures delivered to the Twelfth Biennial Seminar of the Canadian Mathematical Congress (Vancouver, 1969). MR 0274333
Gerald Allen Reisner, Cohen-Macaulay quotients of polynomial rings, Advances in Math. 21 (1976), no. 1, 30–49. MR 407036, DOI 10.1016/0001-8708(76)90114-6
Jeffery B. Remmel and S. Gill Williamson, Spanning trees and function classes, Electron. J. Combin. 9 (2002), no. 1, Research Paper 34, 24. MR 1928786
Richard P. Stanley, Combinatorics and commutative algebra, 2nd ed., Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1996. MR 1453579
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. MR 1442260, DOI 10.1017/CBO9780511805967
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. MR 1676282, DOI 10.1017/CBO9780511609589
Vladimir Turaev, Introduction to combinatorial torsions, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2001. Notes taken by Felix Schlenk. MR 1809561, DOI 10.1007/978-3-0348-8321-4