Spanning trees of 3-uniform hypergraphs

DOI10.1016/J.AAM.2011.04.006zbMATH Open1229.05216arXiv1002.3331OpenAlexW2067113416MaRDI QIDQ720597FDOQ720597

Authors: Anna de Mier, Andrew Goodall 

Publication date: 11 October 2011

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

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.

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

Recommendations

• Note on the Pfaffian matrix-tree theorem
• scientific article; zbMATH DE number 1786671
• 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

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)

Cites Work

• Matching theory
• A characterization of convertible (0,1)-matrices
• Paths, Trees, and Flowers
• A survey of Pfaffian orientations of graphs
• Title not available (Why is that?)
• The Factorization of Linear Graphs
• The Complexity of Enumeration and Reliability Problems
• Matching structure and the matching lattice
• Matroid matching and some applications
• Title not available (Why is that?)
• Counting 1-factors in regular bipartite graphs
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• On the theory of Pfaffian orientations. I: Perfect matchings and permanents
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Nonintersecting paths, pfaffians, and plane partitions
• The Grassmann-Berezin calculus and theorems of the matrix-tree type
• Nonisomorphic Steiner triple systems
• Title not available (Why is that?)
• Nearly perfect matchings in regular simple hypergraphs
• An augmenting path algorithm for linear matroid parity
• Title not available (Why is that?)
• An algebraic matching algorithm
• Note on the Pfaffian matrix-tree theorem
• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• Title not available (Why is that?)
• On the Size of a Maximum Transversal in a Steiner Triple System
• Deterministic polynomial time algorithms for matrix completion problems

Cited In (14)

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

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)