Spanning trees in random regular uniform hypergraphs
| Autor: | Greenhill, Catherine, Isaev, Mikhail, Liang, Gary |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Combinator. Probab. Comp. 31 (2022) 29-53 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1017/S0963548321000158 |
| Popis: | Let $\mathcal{G}_{n,r,s}$ denote a uniformly random $r$-regular $s$-uniform hypergraph on the vertex set $\{1,2,\ldots, 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\geq 5$, there is a positive constant $\rho(s)$ such that for any $r\geq 2$, the probability that $\mathcal{G}_{n,r,s}$ contains a spanning tree tends to 1 if $r > \rho(s)$, and otherwise this probability tends to zero. The threshold value $\rho(s)$ grows exponentially with $s$. As $\mathcal{G}_{n,r,s}$ is connected with probability which tends to 1, this implies that when $r \leq \rho(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 which tends to 1, for any $r\geq 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\geq 2$. TPreviously, this asymptotic distribution was only known in the trivial case of 2-regular graphs, or for cubic graphs. Comment: 40 pages. Fixed some typos |
| Databáze: | arXiv |
| Externí odkaz: |
|