论文标题
边缘颜色的Erdős-rényi图中避免色彩的渗透图
Color-avoiding percolation in edge-colored Erdős-Rényi graphs
论文作者
论文摘要
我们研究了Krause等人引入的避免色彩的渗透模型的变体，即我们研究了（不一定正确）边缘色的Erdős-rényi随机图上的避免色彩的键渗透设置。我们说，如果除去任何颜色的边缘之后，则两个顶点是在边缘颜色的图中连接的，它们在其余图中处于相同的组件中。边缘颜色图的避免色彩的组件是最大的顶点集，因此其中任何两个都是避免色彩的。 我们考虑给定尺寸的避免色彩的组件中包含的顶点的比例以及避免巨型色彩连接的组件中包含的顶点的比例。在某些对颜色浓度的轻度假设下，我们证明这些数量会融合和限制以与边缘色的分支过程树相关的概率来表达。我们提供明确的公式，以实现巨型避免色彩成分的归一化尺寸的限制，在两色的情况下，我们还为给定尺寸的避免色彩的连接组件中包含的顶点的限制提供了明确的公式。
We study a variant of the color-avoiding percolation model introduced by Krause et al., namely we investigate the color-avoiding bond percolation setup on (not necessarily properly) edge-colored Erdős-Rényi random graphs. We say that two vertices are color-avoiding connected in an edge-colored graph if after the removal of the edges of any color, they are in the same component in the remaining graph. The color-avoiding connected components of an edge-colored graph are maximal sets of vertices such that any two of them are color-avoiding connected. We consider the fraction of vertices contained in color-avoiding connected components of a given size as well as the fraction of vertices contained in the giant color-avoiding connected component. Under some mild assumptions on the color-densities, we prove that these quantities converge and the limits can be expressed in terms of probabilities associated to edge-colored branching process trees. We provide explicit formulas for the limit of the normalized size of the giant color-avoiding component, and in the two-colored case we also provide explicit formulas for the limit of the fraction of vertices contained in color-avoiding connected components of a given size.
