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
Additional Information
- Art M. Duval
- Affiliation: Department of Mathematical Sciences, University of Texas at El Paso, El Paso, Texas 79968-0514
- Caroline J. Klivans
- Affiliation: Departments of Mathematics and Computer Science, The University of Chicago, Chicago, Illinois 60637
- MR Author ID: 754274
- Jeremy L. Martin
- Affiliation: Department of Mathematics, University of Kansas, Lawrence, Kansas 66047
- MR Author ID: 717661
- Received by editor(s): February 27, 2008
- Published electronically: June 15, 2009
- Additional Notes: The second author was partially supported by NSF VIGRE grant DMS-0502215
The third author was partially supported by an NSA Young Investigators Grant - © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 361 (2009), 6073-6114
- MSC (2000): Primary 05A15; Secondary 05E99, 05C05, 05C50, 15A18, 57M15
- DOI: https://doi.org/10.1090/S0002-9947-09-04898-3
- MathSciNet review: 2529925