Spanning trees in random regular uniform hypergraphs

Catherine Greenhill, Mikhail Isaev, Gary Liang

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Let Gn,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 Gn,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 Gn,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 Gn,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 Gn,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 Gn,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.

Original languageEnglish
Pages (from-to)29-53
Number of pages25
JournalCombinatorics, Probability and Computing
Volume31
Issue number1
DOIs
Publication statusPublished - Jan 2022

Cite this