Spanning trees of 3-uniform hypergraphs

DOI10.1016/J.AAM.2011.04.006MaRDI QIDQ720597zbMATHOpenAlexFDO

Authors Anna de Mier, Andrew Goodall

Publication date 11 October 2011

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

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

zbMATH Keywords

orientationsPfaffianspanning tree3-uniform hypergraphmatrix-tree theorem

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Masbaum and Vaintrob's "Pfaffian matrix tree theorem" implies that counting spanning trees of a 3-uniform hypergraph (abbreviated to 3-graph) can be done in polynomial time for a class of "3-Pfaffian" 3-graphs, comparable to and related to the class of Pfaffian graphs. We prove a complexity result for recognizing a 3-Pfaffian 3-graph and describe two large classes of 3-Pfaffian 3-graphs -- one of these is given by a forbidden subgraph characterization analogous to Little's for bipartite Pfaffian graphs, and the other consists of a class of partial Steiner triple systems for which the property of being 3-Pfaffian can be reduced to the property of an associated graph being Pfaffian. We exhibit an infinite set of partial Steiner triple systems that are not 3-Pfaffian, none of which can be reduced to any other by deletion or contraction of triples. We also find some necessary or sufficient conditions for the existence of a spanning tree of a 3-graph (much more succinct than can be obtained by the currently fastest polynomial-time algorithm of Gabow and Stallmann for finding a spanning tree) and a superexponential lower bound on the number of spanning trees of a Steiner triple system.

Recommendations

• Note on the Pfaffian matrix-tree theorem
• Publication:4547979
• Pfaffian formulas for spanning tree probabilities
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Space-efficient counting in graphs on surfaces

Cites work

• scientific article; zbMATH DE number 3904590 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• scientific article; zbMATH DE number 1786671 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• A characterization of convertible (0,1)-matrices
• A survey of Pfaffian orientations of graphs
• An algebraic matching algorithm
• An augmenting path algorithm for linear matroid parity
• Counting 1-factors in regular bipartite graphs
• Deterministic polynomial time algorithms for matrix completion problems
• Matching structure and the matching lattice
• Matching theory
• Matroid matching and some applications
• Nearly perfect matchings in regular simple hypergraphs
• Nonintersecting paths, pfaffians, and plane partitions
• Nonisomorphic Steiner triple systems
• Note on the Pfaffian matrix-tree theorem
• On the Size of a Maximum Transversal in a Steiner Triple System
• On the theory of Pfaffian orientations. I: Perfect matchings and permanents
• Paths, Trees, and Flowers
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• The Complexity of Enumeration and Reliability Problems
• The Factorization of Linear Graphs
• 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

Cited in

(15)

• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Generating functions and counting formulas for spanning trees and forests in hypergraphs
• A note on a spanning 3-tree
• On two conjectures concerning spanning tree edge dependences of graphs
• scientific article; zbMATH DE number 1786671 (Why is no real title available?)
• Note on the Pfaffian matrix-tree theorem
• A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
• On tree 3‐spanners in directed path graphs
• Pfaffian formulas for spanning tree probabilities
• The average number of spanning hypertrees in sparse uniform hypergraphs
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• A recursive formula for the reliability of a \(r\)-uniform complete hypergraph and its applications
• Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
• Principal minors Pfaffian half-tree theorem
• Minimally connected \(r\)-uniform hypergraphs

This page was built for publication: Spanning trees of 3-uniform hypergraphs

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