Spanning trees in random regular uniform hypergraphs

Source abstract

Abstract Let $${{\mathcal G}_{n,r,s}}$$ denote a uniformly random r -regular s -uniform hypergraph on the vertex set {1, 2, … , 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 ≥ 5, there is a positive constant ρ ( s ) such that for any r ≥ 2, the probability that $${{\mathcal G}_{n,r,s}}$$ contains a spanning tree tends to 1 if r > ρ ( s ), and otherwise this probability tends to zero. The threshold value ρ ( s ) grows exponentially with s . As $${{\mathcal G}_{n,r,s}}$$ is connected with probability that tends to 1, this implies that when r ≤ ρ ( 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 that tends to 1, for any r ≥ 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 ≥ 2. Previously, this asymptotic distribution was only known in the trivial case of 2-regular graphs, or for cubic graphs.