Loading...
Simplicial and Cellular Trees
Duval, Art M. Klivans, Caroline J. Martin, Jeremy L.
Duval, Art M.
Klivans, Caroline J.
Martin, Jeremy L.
An error occurred retrieving the object's statistics
Citations
Altmetric:
Abstract
Much information about a graph can be obtained by studying its spanning trees. On the other hand, a graph can be regarded as a 1-dimensional cell complex, raising the question of developing a theory of trees in higher dimension. As observed first by Bolker, Kalai, and Adin, and more recently by numerous authors, the fundamental topological properties of a tree — namely acyclicity and connectedness — can be generalized to arbitrary dimension as the vanishing of certain cellular homology groups. This point of view is consistent with the matroid-theoretic approach to graphs, and yields higher-dimensional analogues of classical enumerative results including Cayley’s formula and the matrix-tree theorem. A subtlety of the higher-dimensional case is that enumeration must account for the possibility of torsion homology in trees, which is always trivial for graphs. Cellular trees are the starting point for further high-dimensional extensions of concepts from algebraic graph theory including the critical group, cut and flow spaces, and discrete dynamical systems such as the abelian sandpile model.
Description
Date
2016-04-16
Journal Title
Journal ISSN
Volume Title
Publisher
Springer International Publishing
Collections
Research Projects
Organizational Units
Journal Issue
Keywords
Tree, Forest, Spanning tree, Matrix-tree theorem, Matroid, Simplicial complex, Cell complex, Combinatorial laplacian, Critical group
Citation
Art M. Duval, Caroline J. Klivans and Jeremy L. Martin. Simplicial and Cellular Trees. Recent Trends in Combinatorics (A. Beveridge, J. Griggs, L. Hogben, G. Musiker and P. Tetali, eds.), 713-752, IMA Vol. Math. Appl. 159, Springer, 2016.