论文标题
在随机常规统一超图中跨越树木
Spanning trees in random regular uniform hypergraphs
论文作者
论文摘要
令$ \ MATHCAL {G} _ {n，r，s} $表示均匀的随机$ r $ -R $ -S $ s $ s $ s $ suriform hypergraph in Vertex Set $ \ \ {1,2，\ ldots，n \} $。我们为在$ \ mathcal {g} _ {n，r，s} $中存在的生成树建立了一个阈值结果，限制在满足必要的划分条件下的$ n $。具体来说，我们表明，当$ s \ geq 5 $时，有一个正常的$ρ（s）$，因此对于任何$ r \ geq 2 $，$ \ nathcal {g} _ {g} _ {n，r，s} $的概率包含一个跨度树包含一个跨度为1，如果$ r>ρ（s）$，否则可能会倾向于zere。阈值$ρ（s）$以$ s $成倍增长。由于$ \ Mathcal {g} _ {n，r，s} $与概率相连，这意味着当$ r \ r \ leqρ（s）$，大多数$ r $ r $ r $ -s $ s $ s $ surominal Sifortraphs已连接但没有跨度树。当$ s = 3,4 $时，我们证明$ \ mathcal {g} _ {n，r，s} $包含一个跨度树，概率为1，对于任何$ r \ geq 2 $。我们的证明还提供了$ \ Mathcal {g} _ {n，r，s} $中所有固定整数$ r，s \ geq 2 $中的跨度树数的渐近分布。 tppivey，这种渐近分布仅在2个规则图的微不足道或立方图中已知。
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 $ρ(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 > ρ(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 which tends to 1, this implies that when $r \leq ρ(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.
