Cellular spanning trees and Laplacians of cubical complexes

We prove a Matrix-Tree Theorem enumerating the spanning trees of a cell complex in terms of the eigenvalues of its cellular Laplacian operators, generalizing a previous result for simplicial complexes. As an application, we obtain explicit formulas for spanning tree enumerators and Laplacian eigenva...

Full description

Saved in:
Bibliographic Details
Published in:Advances in applied mathematics 2011-01, Vol.46 (1-4), p.247-274
Main Authors: Duval, Art M., Klivans, Caroline J., Martin, Jeremy L.
Format: Article
Language:English
Subjects:
Cell complex
Cellular
Cubical complex
Eigenvalues
Enumeration
Integers
Laplacian
Mathematical analysis
Recursive
Shifted cubical complex
Spanning tree
Spectra
Theorems
Tree enumeration
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove a Matrix-Tree Theorem enumerating the spanning trees of a cell complex in terms of the eigenvalues of its cellular Laplacian operators, generalizing a previous result for simplicial complexes. As an application, we obtain explicit formulas for spanning tree enumerators and Laplacian eigenvalues of cubes; the latter are integers. We prove a weighted version of the eigenvalue formula, providing evidence for a conjecture on weighted enumeration of cubical spanning trees. We introduce a cubical analogue of shiftedness, and obtain a recursive formula for the Laplacian eigenvalues of shifted cubical complexes, in particular, these eigenvalues are also integers. Finally, we recover Adinʼs enumeration of spanning trees of a complete colorful simplicial complex from the Cellular Matrix-Tree Theorem together with a result of Kook, Reiner and Stanton.
ISSN:0196-8858
1090-2074
DOI:10.1016/j.aam.2010.05.005