7
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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).

Improve this answer
$\endgroup$
5
  • 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
    Commented Feb 9, 2019 at 21:39
  • $\begingroup$ Sam: that's a good reference. I have seen others definitions of trees as well. $\endgroup$
    – Hailong Dao
    Commented 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$
    – Hailong Dao
    Commented 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$
    – Jeremy Martin
    Commented Feb 15, 2019 at 12:33
  • $\begingroup$ Jeremy, thanks. I was indeed thinking over $\mathbb Q$. $\endgroup$
    – Hailong Dao
    Commented Feb 17, 2019 at 19:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .