Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Transactions of the American Mathematical Society
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
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?)

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

PII: S 0002-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.

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia