Ordered \(h\)-hypertrees (Q1199491)

In a previous paper [J. Comb. Theory, Ser. B 41, 209-217 (1986; Zbl 0577.05052)] the author introduced a combinatorial structure, called \(h\)- hypertree, which is an \(h\)-uniform hypergraph satisfying some conditions, in order to improve Bonferroni inequalities by including an additional term determined by such a hypertree. In this paper a special class of \(h\)-hypertrees, called \(\mu\)-ordered \(h\)-hypertrees relatively to a total order \(\mu\) on the vertex set, is introduced. Seven other equivalent definitions of such hypertrees are proposed involving the notions of \(\mu\)-ordered path and \(\mu\)-ordered cycle, some of them being similar to well-known characterizations of trees (case \(h=2)\). It is also proved that for a fixed order \(\mu\), the sets of edges of \(\mu\)-ordered \(h\)- hypertrees with the same vertex set is the set of bases of a graphic matroid and every \(h\)-hypertree can be recognized in polynomial time. However the problem of deciding whether there exists a spanning \(h\)- hypertree of the complete \(h\)-hypergraph \(K^ h_ n\) having the cost less than \(k\) is an NP-complete problem even for \(h=3\) [\textit{I. Tomescu} and \textit{M. Zimand}, Minimum spanning hypertrees, to be published in Discrete App. Math.].