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

DOI10.1016/J.JCTA.2018.03.009zbMATH Open1391.05023arXiv1510.00033OpenAlexW2239748920MaRDI QIDQ721053FDOQ721053

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)

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.

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

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

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)

Cites Work

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

Cited In (8)

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

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)