Mathematics – Combinatorics
Scientific paper
2010-02-17
Mathematics
Combinatorics
34 pages, 9 figures
Scientific paper
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.
Goodall Andrew
Mier Anna de
No associations
LandOfFree
Spanning trees of 3-uniform hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Spanning trees of 3-uniform hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning trees of 3-uniform hypergraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-52333