论文标题
关于随机三合会过程的注释
A note on the random triadic process
论文作者
论文摘要
对于固定的整数$ r \ geqslant 3 $，令$ \ mathbb {h} _r（n，p）$是一个随机的$ r $ r $ rub-rystriform HyperGraph in Vertex Set $ [n] $，其中每个$ r $ - set都是随机且独立于Proborepity $ p $的边缘。随机$ r $ generalized Tiardic过程以一个完整的两部分图$ k_ {r-2，n-r+2} $在同一顶点集上，选择两个不同的顶点$ x $和$ y $均匀地随机，迭代性地添加$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ y \ \ \ y \ \ y \ y \ \ $ z = \ {z_1，\ cdots，z_ {r-2} \} $，以至于$ \ {x，z_i \} $和$ \ {y，z_i \} $ for $ 1 \ leqslant i \ leqslant i \ leqslant i \ leqslant r-2 $已经在图表中Edges和$ \ \ \ \ \ \ \ \ x，y，y，y，y，y，y，y，y，y， z_1，\ cdots，z_ {r-2} \} $是$ \ mathbb {h} _r（n，p）$中的边缘。随机三合会过程是随机$ 3 $综合的三合会过程的缩写。 Korándi等。事实证明，对于随机三元过程的传播是一个急剧的阈值概率，也就是说，如果$ p = cn^{ - \ frac 12} $对于某些正常数$ c $，则具有很高的概率，当$ c> \ frac 12 $且停止以$ o（n^^{n^freac frac 32 $ ed）时，三合会过程将达到完整的图形。在本说明中，我们考虑$ p = o（n^{ - \ frac 12} \ log^{α（3-r）} n）$的最终大小，并使用常数$α> \ frac 12 $。我们表明，该过程的生成图基本上表现为$ \ mathbb {g}（n，p）$。该过程中添加的边缘的最终数与$ \ frac {1} {2} {2} n^{2} p（1 \ pm o（1））$提供$ p =ω（n^{ - 2}）$。结果部分补充了$ r = 3 $的情况。
For a fixed integer $r\geqslant 3$, let $\mathbb{H}_r(n,p)$ be a random $r$-uniform hypergraph on the vertex set $[n]$, where each $r$-set is an edge randomly and independently with probability $p$. The random $r$-generalized triadic process starts with a complete bipartite graph $K_{r-2,n-r+2}$ on the same vertex set, chooses two distinct vertices $x$ and $y$ uniformly at random and iteratively adds $\{x,y\}$ as an edge if there is a subset $Z$ with size $r-2$, denoted as $Z=\{z_1,\cdots,z_{r-2}\}$, such that $\{x,z_i\}$ and $\{y,z_i\}$ for $1\leqslant i\leqslant r-2$ are already edges in the graph and $\{x,y, z_1,\cdots,z_{r-2}\}$ is an edge in $\mathbb{H}_r(n,p)$. The random triadic process is an abbreviation for the random $3$-generalized triadic process. Korándi et al. proved a sharp threshold probability for the propagation of the random triadic process, that is, if $p= cn^{ - \frac 12}$ for some positive constant $c$, with high probability, the triadic process reaches the complete graph when $c> \frac 12$ and stops at $O(n^{\frac 32})$ edges when $c< \frac 12$. In this note, we consider the final size of the random $r$-generalized triadic process when $p=o( n^{- \frac 12}\log^{ α(3-r)} n)$ with a constant $α> \frac 12$. We show that the generated graph of the process essentially behaves like $\mathbb{G}(n,p)$. The final number of added edges in the process, with high probability, equals $ \frac {1}{2}n^{2}p(1\pm o(1))$ provided that $p=ω(n^{-2})$. The results partially complement the ones on the case of $r=3$.
