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!


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$ – Sam Hopkins Feb 9 at 21:39
  • $\begingroup$ Sam: that's a good reference. I have seen others definitions of trees as well. $\endgroup$ – Hailong Dao Feb 9 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$ – Hailong Dao Feb 9 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$ – Jeremy Martin 2 days ago
  • $\begingroup$ Jeremy, thanks. I was indeed thinking over $\mathbb Q$. $\endgroup$ – Hailong Dao 9 hours ago

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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