Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Simplicial matrix-tree theorems


Authors: Art M. Duval, Caroline J. Klivans and Jeremy L. Martin
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
Published electronically: June 15, 2009
MathSciNet review: 2529925
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Ron Adin, Counting colorful multi-dimensional trees, Combinatorica 12, no. 3 (1992), 247-260. MR 1195888 (93j:05036)
  • 2. Eric Babson and Isabella Novik, Face numbers and nongeneric initial ideals, Electron. J. Combin. 11, no. 2 (2004/06), Research Paper #R25, 23 pp. (electronic) MR 2195431 (2007c:05202)
  • 3. Matthias Beck and Serkan Hoşten, Cyclotomic polytopes and growth series of cyclotomic lattices, Math. Res. Lett. 13, no. 4 (2006), 607-622. MR 2250495 (2007h:52018)
  • 4. L.W. Beineke and R.E. Pippert, Properties and characterizations of $ k$-trees, Mathematika 18 (1971), 141-151. MR 0288046 (44:5244)
  • 5. Anders Björner and Gil Kalai, An extended Euler-Poincaré theorem, Acta Math. 161, no. 3-4 (1988), 279-303. MR 971798 (89m:52009)
  • 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. MR 1253009 (95c:52021)
  • 7. Ethan Bolker, Simplicial geometry and transportation polytopes, Trans. Amer. Math. Soc. 217 (1976), 121-142. MR 0411983 (54:112)
  • 8. Béla Bollobás, Modern Graph Theory. Graduate Texts in Mathematics, 184. Springer, New York, 1998. MR 1633290 (99h:05001)
  • 9. Arthur Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376-378.
  • 10. A.K. Dewdney, Higher-dimensional tree structures, J. Comb. Theory Ser. B 17 (1974), 160-169. MR 0369115 (51:5351)
  • 11. Xun Dong and Michelle L. Wachs, Combinatorial Laplacian of the matching complex, Electron. J. Combin. 9 (2002), no. 1, Research Paper #R17, 11 pp. (electronic) MR 1912799 (2003g:05131)
  • 12. Art M. Duval, A relative Laplacian spectral recursion, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper #R26, 19 pp. (electronic) MR 2224939 (2007d:05037)
  • 13. Art M. Duval and Victor Reiner, Shifted simplicial complexes are Laplacian integral, Trans. Amer. Math. Soc. 354, no. 11 (2002), 4313-4344. MR 1926878 (2003j:15017)
  • 14. Richard Ehrenborg and Stephanie van Willigenburg, Enumerative properties of Ferrers graphs, Discrete Comput. Geom. 32 (2004), no. 4, 481-492. MR 2096744 (2005j:05076)
  • 15. Sara Faridi, The facet ideal of a simplicial complex, Manuscripta Math. 109, no. 2 (2002), 159-174. MR 1935027 (2003k:13027)
  • 16. Miroslav Fiedler and Jiří Sedláček, Über Wurzelbasen von gerichteten Graphen, Časopis Pěst. Mat. 83 (1958), 214-225. MR 0097071 (20:3551)
  • 17. Joel Friedman and Phil Hanlon, On the Betti numbers of chessboard complexes, J. Algebraic Combin. 8 (1998), 193-203. MR 1648484 (2000c:05155)
  • 18. Allen Hatcher, Algebraic Topology. Cambridge University Press, Cambridge, 2002. Also available online at http://www.math.cornell.edu/$ \sim$hatcher/AT/ATpage.html. MR 1867354 (2002k: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), 157-167, Lecture Notes in Pure and Appl. Math., 206, Dekker, New York, 1999. MR 1702104 (2001b:13017)
  • 20. Gil Kalai, Enumeration of $ Q$-acyclic simplicial complexes, Israel J. Math. 45, no. 4 (1983), 337-351. MR 720308 (85a:55006)
  • 21. Gil Kalai, Algebraic shifting, Computational commutative algebra and combinatorics (Osaka, 1999), 121-163, Adv. Stud. Pure Math., 33, Math. Soc. Japan, Tokyo, 2002. MR 1890098 (2003e:52024)
  • 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), 535-545. MR 2121994 (2005k:06008)
  • 24. W. Kook, V. Reiner, and D. Stanton, Combinatorial Laplacians of matroid complexes, J. Amer. Math. Soc. 13 (2002), 129-148. MR 1697094 (2001e:05028)
  • 25. N.V.R. Mahadev and U.N. Peled, Threshold graphs and related topics. Annals of Discrete Mathematics, 56. North-Holland Publishing Co., Amsterdam, 1995. MR 1417258 (97h:05001)
  • 26. Jeremy L. Martin and Victor Reiner, Cyclotomic and simplicial matroids, Israel J. Math. 150 (2005), 229-240. MR 2255809 (2007g:05040)
  • 27. Jeremy L. Martin and Victor Reiner, Factorization of some weighted spanning tree enumerators, J. Combin. Theory Ser. A 104, no. 2 (2003), 287-300. MR 2019276 (2004i:05070)
  • 28. Gregor Masbaum and Arkady Vaintrob, A new matrix-tree theorem, Int. Math. Res. Not. 2002, no. 27, 1397-1426. MR 1908476 (2003a:05107)
  • 29. J.W. Moon, Counting Labeled Trees. Canadian Mathematical Monographs, No. 1, Canadian Mathematical Congress, Montreal, 1970. MR 0274333 (43:98)
  • 30. Gerald Reisner, Cohen-Macaulay quotients of polynomial rings, Adv. Math. 21 (1976), no. 1, 30-49. MR 0407036 (53:10819)
  • 31. Jeffrey B. Remmel and S. Gill Williamson, Spanning trees and function classes, Electron. J. Combin. 9, no. 1 (2002), Research Paper #R34, 24 pp. (electronic) MR 1928786 (2003g:05067)
  • 32. Richard P. Stanley, Combinatorics and Commutative Algebra, 2nd ed., Birkhäuser, Boston, 1996. MR 1453579 (98h:05001)
  • 33. Richard P. Stanley, Enumerative Combinatorics, volume I. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, 1997. MR 1442260 (98a:05001)
  • 34. Richard P. Stanley, Enumerative Combinatorics, volume II. Cambridge Studies in Advanced Mathematics, 62. Cambridge University Press, 1999. MR 1676282 (2000k:05026)
  • 35. Vladimir Turaev, Introduction to combinatorial torsions, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2001. MR 1809561 (2001m:57042)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05A15, 05E99, 05C05, 05C50, 15A18, 57M15

Retrieve articles in all journals with MSC (2000): 05A15, 05E99, 05C05, 05C50, 15A18, 57M15


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

Jeremy L. Martin
Affiliation: Department of Mathematics, University of Kansas, Lawrence, Kansas 66047

DOI: https://doi.org/10.1090/S0002-9947-09-04898-3
Keywords: Simplicial complex, spanning tree, tree enumeration, Laplacian, spectra, eigenvalues, shifted complex
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
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society