Spanning trees in random regular uniform hypergraphs. (26th January 2022)

• Record Type: Journal Article
• Authors: Greenhill, Catherine; Isaev, Mikhail; Liang, Gary
• Is Part Of: Combinatorics, probability and computing. Volume 31:Number 1(2022)
• Page Start: 29
• Page End: 53
• Publication Date: 2022-01-26
• Subjects: 05C80 -- 05C65 -- 05C70; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548321000158
• Languages: English
• ISSNs: 0963-5483

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.