论文标题
在渗透密集的图序列中的K核
K-core in percolated dense graph sequences
论文作者
论文摘要
我们确定了一大类密集的图形序列中的$ k $ core的大小。令$ g_n $为一系列无方向的，$ n $ vertex图形，具有边缘$ \ {a^n_ {a^n_ {i，j} _ {i，j \ in [n]} $，将其收敛到内核$ w：[0,1]^2 \ to [0,1]^2 \ to [0,1]^to [0,+\ festty）。保留$ g_n $的边缘$（i，j）$ a概率$ \ min \ {{a^n_ {i，j}}}/{n}/{n}，1 \} $独立地，我们获得了一系列随机图$ g_n（\ frac {1}} {n}）$。用$ \ Mathcal {a} $表示分支过程的属性，即初始粒子至少有$ k $的儿童，每个粒子至少有$ k-1 $的孩子，每个孩子至少有$ k-1 $ $ k-1 $的孩子，依此类推。使用分支过程和密度图限制的理论，在温和的假设下，我们获得了$ k $ - 随机图的大小$ g_n（\ frac {1} {n} {n}）$，\ begin {align*} \ text \ text { \ Mathbb {p} _ {X^w} \ left（\ Mathcal {a} \ right） +o_p（n）。 \ end {align*}我们的结果也可以用于获得$ k $ core $ n $的外观阈值。
We determine the size of $k$-core in a large class of dense graph sequences. Let $G_n$ be a sequence of undirected, $n$-vertex graphs with edge weights $\{a^n_{i,j}\}_{i,j \in [n]}$ that converges to a kernel $W:[0,1]^2\to [0,+\infty)$ in the cut metric. Keeping an edge $(i,j)$ of $G_n$ with probability $\min \{ {a^n_{i,j}}/{n},1 \}$ independently, we obtain a sequence of random graphs $G_n(\frac{1}{n})$. Denote by $\mathcal{A}$ the property of a branching process that the initial particle has at least $k$ children, each of which has at least $k-1$ children, each of which has at least $k-1$ children, and so on. Using branching process and the theory of dense graph limits, under mild assumptions we obtain the size of $k$-core of random graphs $G_n(\frac{1}{n})$, \begin{align*} \text{size of $k$-core of } G_n\left(\frac{1}{n}\right) =n \mathbb{P}_{X^W}\left(\mathcal{A}\right) +o_p(n). \end{align*} Our result can also be used to obtain the threshold of appearance of a $k$-core of order $n$.
