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 -