论文标题
Erdős-rényi随机图上的避免色彩的渗透
Color-avoiding percolation on the Erdős-Rényi random graph
论文作者
论文摘要
我们考虑了最近引入的避免色彩渗透的模型，定义为如下。图$ g $中的每个边缘均以$ k \ ge 2 $颜色的颜色为颜色。如果$ u $和$ v $可以使用$ k-1 $的任何子集连接，则据说两个顶点$ u $和$ v $ in $ g $是连接的。 CA连接性定义了$ g $的顶点集的等价关系，其类称为CA组件。 我们研究了恒定平均度的随机颜色Erdős-rényi随机图的组件结构。我们区分了最大组成部分规模的三个制度：超临界状态，所谓的中间制度和一个亚临界体制，其中最大的CA组件分别具有线性，对数和有限的大小。有趣的是，在亚临界方面，界限是确定性的，并且由颜色数量给出。
We consider a recently introduced model of color-avoiding percolation defined as follows. Every edge in a graph $G$ is colored in some of $k\ge 2$ colors. Two vertices $u$ and $v$ in $G$ are said to be CA-connected if $u$ and $v$ may be connected using any subset of $k-1$ colors. CA-connectivity defines an equivalence relation on the vertex set of $G$ whose classes are called CA-components. We study the component structure of a randomly colored Erdős-Rényi random graph of constant average degree. We distinguish three regimes for the size of the largest component: a supercritical regime, a so-called intermediate regime, and a subcritical regime, in which the largest CA-component has respectively linear, logarithmic, and bounded size. Interestingly, in the subcritical regime, the bound is deterministic and given by the number of colors.
