2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Note that the notion of a cycle in a hypergraph is not universally agreed upon, but I think it is clear what you mean. Some other constructions which give you $O(2^n)$ are as follows. Take all hyperedges which contain two fixed vertices. Slightly better is a connected modification of what you suggest at the end. Take all hyperedges on all but one vertex $x$. Then add a hyperedge $e$ of size $n-1$ containing $x$. This makes the hypergraph connected. Then remove all hyperedges of size 2 which meet $e$ in one vertex. This gives $2^{n-1}-(n-3)$ hyperedges. $\endgroup$ – Tony Huynh Nov 3 '14 at 23:24
  • 3
    $\begingroup$ It is not clear to me. How do you get a spanning tree without normal (i.e. size 2) edges? And where is the cycle in the example given on 4 vertices? $\endgroup$ – The Masked Avenger Nov 4 '14 at 0:34
  • 1
    $\begingroup$ My guess is that a cycle is a weak cycle, a cycle of edges such that adjacent edges in the cycle share at least one vertex, and that a spanning tree is a connected subgraph that is acyclic (in this sense) and covers the vertex set. $\endgroup$ – Ben Barber Nov 4 '14 at 8:51
1
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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