Maximum number of hyperedges on a hypergraph without a spanning tree

Question

Although every connected graph has a spanning tree, the same is not true for hypergraphs: consider the hypergraph on 4 vertices with all possible edges of size 3. You need to pick at least two edges but any 2 edges form a cycle.

On the other hand, if you make the number of hyperedges increase, eventually you get a spanning tree (in particular, in the complete hypergraph you always have a spanning tree).

So, what is the maximum number of hyperedges on a hypergraph without a spanning tree? I think $2^{|V|-1}$ is a lower bound, since you can do something similar to the example on 4 vertices. For that, take every edge on at least $\big\lceil\frac{|V|}{2}\big\rceil + 1$ vertices, in order to ensure that every pair of edges has intersection of size at least two. Another way of getting this is taking all possible edges on all but one vertex, but in this case the hypergraph is not connected.

Answer 1

Here is an expansion of my comment. Let $f(n)$ be the maximum number of edges of a connected hypergraph with $n$ vertices which does not have a spanning tree.

For the lower bound, fix a vertex $x$ and begin by taking all hyperedges not containing $x$. Then add a hyperedge $e$ of size $n-1$ containing $x$ to make the hypergraph connected. Then delete all hyperedges of size 2 which meet $e$ in exactly one vertex (this destroys all spanning trees containing $e$ and hence all spanning trees). This construction has $2^{n-1}+1-(n-2)=2^{n-1}-(n-3)$ edges.

I claim that $3 \cdot 2^{n-2}$ is an upperbound for $f(n)$. To see this, consider the graph $G$ with vertex set all subsets of $[n]$, and where $A$ and $B$ are adjacent in $G$ if and only if $A \cup B=[n]$ and $|A \cap B|=1$. Observe that for every $A \in 2^{[n]}$, the degree of $A$ in $G$ is simply the number of elements in $A$. Therefore, the number of edges in $G$ is $n2^{n-2}$. Let $\mathcal{H}$ be a hypergraph on $[n]$ with more than $3 \cdot 2^{n-2}$ hyperedges. We prove the stronger claim that $\mathcal{H}$ must contain a spanning tree with exactly two hyperedges (note that there is no connectivity assumption on $\mathcal{H}$ for this upperbound). Suppose not. Then, the hyperedges of $\mathcal{H}$ correspond to an independent set $X$ in $G$. Let $Y=2^{[n]} \setminus X$. Note $|Y| < 2^{n-2}$ and obviously each vertex in $Y$ has maximum degree $n$. Since $X$ is an independent set we have

$$n2^{n-2}=|E(G)| \leq \sum_{y \in Y} deg_G(y) \leq n|Y| < n2^{n-2},$$ which is a contradiction.

Summary. $2^{n-1}-(n-3) \leq f(n) \leq 3 \cdot 2^{n-2}$.