Generating functions and counting formulas for spanning trees and forests in hypergraphs

DOI10.1016/j.aam.2023.102667OpenAlexW4390928037MaRDI QIDQ6153615

Sheng Gui Zhang, Guihai Yu, Jiuqiang Liu

Publication date: 14 February 2024

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aam.2023.102667

zbMATH Keywords

hypergraphsPfaffiansspanning treesmatrix tree theoremspanning forestsBerezin-Grassmann integralHafnians

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Hypergraphs (05C65) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hafnians, perfect matchings and Gaussian matrices
• Quantum permanents and Hafnians via Pfaffians
• Matrix-tree theorems and discrete path integration
• Hypergraphs and a functional equation of Bouwkamp and de Bruijn
• Matroid matching and some applications
• Matrix tree theorems
• Milnor numbers, spanning trees, and the Alexander-Conway polynomial.
• Nonintersecting paths, pfaffians, and plane partitions
• Pfaffian and Hafnian identities in shuffle algebras
• The Grassmann-Berezin calculus and theorems of the matrix-tree type
• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems
• Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• Zeon Algebra and Combinatorial Identities

This page was built for publication: Generating functions and counting formulas for spanning trees and forests in hypergraphs