Directed rooted forests in higher dimension

MaRDI QIDQ504966zbMATH OpenFDO

Authors Olivier Bernardi, Caroline Klivans

Publication date 18 January 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07757, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p35

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

matrix-tree theoremsimplicial complexes

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial aspects of simplicial complexes (05E45)

Abstract: For a graph G, the generating function of rooted forests, counted by the number of connected components, can be expressed in terms of the eigenvalues of the graph Laplacian. We generalize this result from graphs to cell complexes of arbitrary dimension. This requires generalizing the notion of rooted forest to higher dimension. We also introduce orientations of higher dimensional rooted trees and forests. These orientations are discrete vector fields which lead to open questions concerning expressing homological quantities combinatorially.

Review text

Summary: For a graph \(G\), the generating function of rooted forests, counted by the number of connected components, can be expressed in terms of the eigenvalues of the graph Laplacian. We generalize this result from graphs to cell complexes of arbitrary dimension. This requires generalizing the notion of rooted forest to higher dimension. We also introduce orientations of higher dimensional rooted trees and forests. These orientations are discrete vector fields which lead to open questions concerning expressing homological quantities combinatorially.

Recommendations

• On the topology of rooted forests in higher dimensions
• Complexes of directed trees
• Oriented Forests in Directed Graphs
• Higher Dimensional Trees, Algebraically
• Multidimensional trees
• A representation on the labeled rooted forests
• Reconstruction of rooted directed trees
• Canonical forests in directed families
• A multicomplex of partially edge-rooted forests
• Directed forests and the constancy of Kemeny's constant

Cites work

• A combinatorial decomposition of acyclic simplicial complexes
• A combinatorial decomposition of simplicial complexes
• A user's guide to discrete Morse theory
• Cellular spanning trees and laplacians of cubical complexes
• Counting colorful multi-dimensional trees
• Cuts and flows of cell complexes
• Enumeration of \({\mathbb{Q}}\)-acyclic simplicial complexes
• scientific article; zbMATH DE number 4027487 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• On the spanning trees of the hypercube and other products of graphs
• Pseudodeterminants and perfect square spanning tree counts
• RANDOM COMPLEXES AND ℓ²-BETTI NUMBERS
• Simplicial matrix-tree theorems

Cited in

(14)

• On the topology of rooted forests in higher dimensions
• Enumerative combinatorics of simplicial and cell complexes: Kirchhoff and Trent type theorems
• A colourful path to matrix-tree theorems
• Kirchhoff index of simplicial networks
• The Chow form of a reciprocal linear space
• Graph coverings and twisted operators
• Oriented Forests in Directed Graphs
• Hyperforests on the complete hypergraph by Grassmann integral representation
• scientific article; zbMATH DE number 1305528 (Why is no real title available?)
• scientific article; zbMATH DE number 691512 (Why is no real title available?)
• On the rooted forests in triangulated closed manifolds
• The bi-dimensional directed IDLA forest
• On discrete gradient vector fields and Laplacians of simplicial complexes
• Hypergraphic zonotopes and acyclohedra

This page was built for publication: Directed rooted forests in higher dimension

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