For usual graphs on $n$ vertices, a edge-minimal connected graph is nothing but a spanning tree of this graph. It is well-known that any spanning tree has $n-1$ edges.

I would like to know whether there is a similar definition of connectivity for $3$-uniform hypergraphs which preserves this property. To be more specific, is there any known definition of connectivity for $3$-uniform hypergraphs such that every edge-minimal connected graph on $n$ vertices has exactly $\binom{n-1}{2}$ edges?

I personally have a definition for any $k$-uniform hypergraphs which satisfies this property, and I just want to know whether some definitions have already been posed before. Thanks!


1 Answer 1


Think of the hypergraph as a simplicial complex $\Delta$, with the facets being the hyperedges. Consider property (*) as:

1) The $i$-skeleton of $\Delta$ is full for $0\leq i\leq k-2$ and 2) $\tilde H_i(\Delta)=0$ for $0\leq i\leq k-2$

Then these conditions force $f_{k-1}-\binom{n-1}{k-1}= \dim \tilde H_{k-1}(\Delta)$.

Thus a minimal complex satisfying * would have $f_{k-1}=\binom{n-1}{k-1}$. Such complex would have full $i$-skeleton up to $i=k-2$ and acyclic, so a reasonable generalization of trees. Of course, they will not be "spanning" in general as not all connected complex contains one, but if you restricts to (*) complexes, perhaps they will.

I am not an expert, but remember seeing many papers studying higher-dimensional trees, so you may find this somewhere (or people who really know this area may be able to locate a reference).

  • 1
    $\begingroup$ There is a definition of spanning tree for a simplicial complex going back to Kalai; it is normal to weight these in terms of torsoin to, e.g., recover the Matrix Tree Theorem from classical graph theory- see: arxiv.org/pdf/0802.2576.pdf. $\endgroup$ Feb 9, 2019 at 21:39
  • $\begingroup$ Sam: that's a good reference. I have seen others definitions of trees as well. $\endgroup$ Feb 9, 2019 at 21:46
  • $\begingroup$ So my guess is that the Kalai-spanning trees of the full $k-1$ skeleton of the $n$-simplex would be the trees I define. $\endgroup$ Feb 9, 2019 at 22:30
  • 1
    $\begingroup$ Long, your guess is right. The simplicial spanning trees of the simplex skeleton are bases of the matroid represented by the columns of the simplicial boundary map, so in particular they all have the same cardinality. One note: your $\tilde{H}$ should be interpreted as having coefficients in $\mathbb{Q}$, since, as Sam pointed out, there can be torsion present (this first occurs when $n=6$, when the tree is a triangulation of the real projective plane). $\endgroup$ Feb 15, 2019 at 12:33
  • $\begingroup$ Jeremy, thanks. I was indeed thinking over $\mathbb Q$. $\endgroup$ Feb 17, 2019 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.