随机树对交集中的公共边数：从完全图到Erd?s–Rényi随机图与完全多部图的Poisson极限律

《European Journal of Combinatorics》：On the intersection of pairs of trees

　　

研究人员考虑图G的两棵独立随机生成树的公共边数。对于完全图K_n，研究人员给出了Moon最初所得结果的一个新证明，即该分布收敛于期望值为2的Poisson分布（Poisson distribution）。该结果被用于证明：对于常数p，Erd?s–Rényi随机图G(n,p)的两棵独立随机生成树的公共边数满足Poisson极限律（Poisson limit law）；并在p→0且p≥n^?2/3+ε的情形下证明中心极限定理（central limit theorem）。研究人员亦用同一方法证明了完全多部图（complete multipartite graphs）的类似结果。

研究人员研究同一图G上独立均匀选取的两棵随机生成树的公共边数问题。对于完全图K_n，已有Moon给出的隐式结果表明公共边数依分布收敛于期望值为2的Poisson分布（Poisson distribution），近期Fuchs和Steel用不同方法也证明了该结果，其动机来自医学生物信息学。研究人员旨在给出该Poisson极限的一个基于矩收敛的新证明，并将其推广至Erd?s–Rényi随机图G(n,p)以及完全多部图。研究人员首先利用森林扩张计数公式（Lemma 1）计算固定边集同时含于随机生成树的概率，证明不相交边对应的指示变量渐近独立，进而通过矩方法证明完全图中公共边数的各阶矩收敛于参数为2的Poisson分布的各阶矩，并用Chen–Stein方法给出全变差距离（total variation distance）上界27/n。随后通过Bayes公式与条件化论证，将完全图结果推广到常数p的G(n,p)，得到参数为2/p的Poisson极限；在p→0且p≥n^?2/3+ε时，通过对P(|T₁∩T₂|=m)的精细渐近分析证明局部中心极限定理。最后借助Li–Chen–Yan关于完全多部图含固定森林的生成树计数公式，证明完全多部图中公共边数收敛于期望值为∑_{1≤icicj(2?ci?cj)²/((1?ci)²(1?cj)²)的Poisson分布。研究表明稀疏与稠密图结构下公共边数的Poisson型普适行为，并为一般图的类似问题提供了判据性讨论。主要关键技术方法包括：森林扩张计数公式（Lemma 1）用于计算含固定边集的生成树数目；矩方法（method of moments）通过指示变量分解与渐近独立性证明矩收敛；Chen–Stein方法给出全变差距离界；Bayes公式与条件化论证将完全图结果迁移至G(n,p)；对P(|T1∩T2|=m)的渐近展开结合Poisson分布Chernoff界证明局部中心极限定理；以及Li–Chen–Yan完全多部图生成树计数公式。样本队列来源为完全图Kn、Erd?s–Rényi随机图G(n,p)与完全多部图Kn1,…,nd，无实际数据队列。研究结果如下：2. 完全图（Complete graphs）：通过矩方法证明公共边数Xn的第r阶矩渐近等于e^?2∑k≥02^kk^r/k!，即收敛于参数2的Poisson分布的第r阶矩，并由矩唯一性得依分布收敛；进一步用Chen–Stein方法得全变差距离dTV(Xn,Poi(2))≤27/n。3. Erd?s–Rényi随机图（Erd?s–Rényi random graphs）：对常数p，通过Bayes公式与条件化论证证明X依分布收敛于Poi(2/p)；对p→0且p≥n^?2/3+ε，通过对rm(n)的渐近展开（Lemma 6、Lemma 7）证明局部中心极限定理，即λnP(X=mn)→(1/√(2π))e^?α2/2，并得λn^?1/2(X?λn)依分布收敛于N(0,1)。4. 完全多部图（Complete multipartite graphs）：利用Li–Chen–Yan公式证明不相交边集渐近独立，通过矩方法得公共边数收敛于期望值为∑1≤icicj(2?ci?cj)²/((1?ci)²(1?cj)²)的Poisson分布；特别地，完全二部图情形期望值化为1/(c1c2)，正则多部图情形化为2d/(d?1)。讨论部分指出，Poisson行为并非对所有图成立：若G为n顶点树，则公共边数恒为n?1；完全二部图Kk,n?k（k固定）的公共边数渐近服从二项分布Bin(n?k,1/k)，从而渐近正态；含桥的图中桥必为公共边；由两个Kn/2经固定数目k条不相交边连接而成的图，每条连接边属于随机生成树的概率有下界1/k，亦导致非Poisson分布。研究人员认为较稠密图预期出现Poisson分布，但桥等结构会破坏该性质，并猜测定理5中指数2/3并非最优，或可推广至连通性阈值以上的全部p。研究结论部分翻译如下：研究人员考虑图G的两棵独立随机生成树的公共边数。对于完全图Kn，研究人员给出了Moon最初所得结果的一个新证明，即该分布收敛于期望值为2的Poisson分布。该结果被用于证明：对于常数p，Erd?s–Rényi随机图G(n,p)的两棵独立随机生成树的公共边数满足Poisson极限律；并在p→0且p≥n^?2/3+ε的情形下证明中心极限定理。研究人员亦用同一方法证明了完全多部图的类似结果。}