A weighted cellular matrix-tree theorem, with applications to complete colorful and cubical complexes

DOI10.1016/J.JCTA.2018.03.009MaRDI QIDQ721053zbMATH OpenOpenAlexFDO

Authors G. Aalipour, Art M. Duval, Woong Kook, Kang-Ju Lee, Jeremy L. Martin

Publication date 18 July 2018

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.00033

zbMATH Keywords

hypercubeEuler characteristicLaplacianmatrix-tree theoremcomplete colorful complex

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30)

Abstract: We present a version of the weighted cellular matrix-tree theorem that is suitable for calculating explicit generating functions for spanning trees of highly structured families of simplicial and cell complexes. We apply the result to give weighted generalizations of the tree enumeration formulas of Adin for complete colorful complexes, and of Duval, Klivans and Martin for skeleta of hypercubes. We investigate the latter further via a logarithmic generating function for weighted tree enumeration, and derive another tree-counting formula using the unsigned Euler characteristics of skeleta of a hypercube and the Crapo $$-invariant of uniform matroids.

Recommendations

• Cellular spanning trees and laplacians of cubical complexes
• Simplicial matrix-tree theorems
• Weighted tree-numbers of matroid complexes
• Linear algebraic techniques for weighted spanning tree enumeration
• Factorizations of some weighted spanning tree enumerators

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2076810 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• A higher Boltzmann distribution
• A new algebraic criterion for shellability
• Cellular spanning trees and laplacians of cubical complexes
• Combinatorics and commutative algebra.
• Computing Betti numbers via combinatorial Laplacians
• Counting colorful multi-dimensional trees
• Enumeration of \({\mathbb{Q}}\)-acyclic simplicial complexes
• Factorizations of some weighted spanning tree enumerators
• Kirchhoff's theorems in higher dimensions and Reidemeister torsion
• Logarithmic tree-numbers for acyclic complexes
• Pseudodeterminants and perfect square spanning tree counts
• Shifted simplicial complexes are Laplacian integral
• Simplical Geometry and Transportation Polytopes
• Simplicial and cellular trees
• Simplicial matrix-tree theorems
• Spanning trees and function classes
• The Enumeration of Point Labelled Chromatic Graphs and Trees
• Weighted tree-numbers of matroid complexes

Cited in

(9)

• Simplicial networks and effective resistance
• Enumeration of one class of plane weighted trees
• Weighted tree-numbers of matroid complexes
• Cellular spanning trees and laplacians of cubical complexes
• Torsion-weighted spanning acycle entropy in cubical lattices and Mahler measures
• Simplicial matrix-tree theorems
• Pseudodeterminants and perfect square spanning tree counts
• Decorated hypertrees
• Factorizations of some weighted spanning tree enumerators

This page was built for publication: A weighted cellular matrix-tree theorem, with applications to complete colorful and cubical complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q721053)