TY - JOUR
T1 - Spanning trees in random regular uniform hypergraphs
AU - Greenhill, Catherine
AU - Isaev, Mikhail
AU - Liang, Gary
N1 - Publisher Copyright:
© The Author(s), 2021. Published by Cambridge University Press.
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2022/1
Y1 - 2022/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85107005421&partnerID=8YFLogxK
U2 - 10.1017/S0963548321000158
DO - 10.1017/S0963548321000158
M3 - Article
AN - SCOPUS:85107005421
SN - 0963-5483
VL - 31
SP - 29
EP - 53
JO - Combinatorics, Probability and Computing
JF - Combinatorics, Probability and Computing
IS - 1
ER -