论文标题
随机树加权图
Random tree-weighted graphs
论文作者
论文摘要
对于每个$ n \ ge 1 $，让$ \ mathrm {d}^n =（d^{n}（i），1 \ le i \ le n）$是一系列积极的插入序列，均匀$ \ sum_ {i = 1}^n d^n（i = 1}^n d^n（i）\ ge 2n $。令$（g_n，t_n，γ_n）$均匀分布在一组简单的图表上，$ g_n $，带有度序列$ \ mathrm {d}^n $，并赋予了一个跨度树$ t_n $，并扎根于方向上的边缘$γ_n$ g_n $的$ g_n $，这不是$ g_n $的$ g_n $。在$ g_n $中的学位上的有限差异假设下，我们表明，在重新续订后，$ t_n $将分配收敛到$ n \ to \ infty $。我们的主要工具是Pitman的添加剂合并的新版本（https://doi.org/10.1006/jcta.1998.2919），可用于构建具有固定度序列的随机树和带有固定度序列的随机树赋予图。作为证明的输入，我们还为固定图的叠加中的环数和多个边数和多个边缘的泊松定理得出了泊松近似定理，并根据配置模型采样了给定度序列的随机图；我们发现这具有独立的兴趣。
For each $n \ge 1$, let $\mathrm{d}^n=(d^{n}(i),1 \le i \le n)$ be a sequence of positive integers with even sum $\sum_{i=1}^n d^n(i) \ge 2n$. Let $(G_n,T_n,Γ_n)$ be uniformly distributed over the set of simple graphs $G_n$ with degree sequence $\mathrm{d}^n$, endowed with a spanning tree $T_n$ and rooted along an oriented edge $Γ_n$ of $G_n$ which is not an edge of $T_n$. Under a finite variance assumption on degrees in $G_n$, we show that, after rescaling, $T_n$ converges in distribution to the Brownian continuum random tree as $n \to \infty$. Our main tool is a new version of Pitman's additive coalescent (https://doi.org/10.1006/jcta.1998.2919), which can be used to build both random trees with a fixed degree sequence, and random tree-weighted graphs with a fixed degree sequence. As an input to the proof, we also derive a Poisson approximation theorem for the number of loops and multiple edges in the superposition of a fixed graph and a random graph with a given degree sequence sampled according to the configuration model; we find this to be of independent interest.
