Spanning trees in random regular uniform hypergraphs

Abstract

Let ${\mathcal{G}}_{n,r,s}$ denote a uniformly random $r$-regular $s$-uniform hypergraph on the vertex set $\{1,2,\dots ,n\}$. We establish a threshold result for the existence of a spanning tree in ${\mathcal{G}}_{n,r,s}$, restricting to $n$ satisfying the necessary divisibility conditions. Specifically, we show that when $s\ge 5$, there is a positive constant $\rho (s)$ such that for any $r\ge 2$, the probability that ${\mathcal{G}}_{n,r,s}$ contains a spanning tree tends to 1 if $r>\rho (s)$, and otherwise this probability tends to zero. The threshold value $\rho (s)$ grows exponentially with $s$. As ${\mathcal{G}}_{n,r,s}$ is connected with probability which tends to 1, this implies that when $r\le \rho (s)$, most $r$-regular $s$-uniform hypergraphs are connected but have no spanning tree. When $s=3,4$ we prove that ${\mathcal{G}}_{n,r,s}$ contains a spanning tree with probability which tends to 1, for any $r\ge 2$. Our proof also provides the asymptotic distribution of the number of spanning trees in ${\mathcal{G}}_{n,r,s}$ for all fixed integers $r,s\ge 2$. TPreviously, this asymptotic distribution was only known in the trivial case of 2-regular graphs, or for cubic graphs.

40 pages. Fixed some typos

References in corpus (2)

• Spanning trees in complete uniform hypergraphs and a connection to extended r-Shi hyperplane arrangements
• On the enumeration of labelled hypertrees and of labelled bipartite trees

Cited by in corpus (1)

• Random Recursive Hypergraphs