Spanning trees in random regular uniform hypergraphs. (26th January 2022) - Greenhill, Catherine; Isaev, Mikhail; Liang, Gary
Abstract: Let 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 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 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 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 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 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.