Color-avoiding percolation in edge-colored Erdős–Rényi graphs

Fekete, Panna Tímea and Molontay, Roland and Ráth, Balázs and Varga, Kitti Katalin (2024) Color-avoiding percolation in edge-colored Erdős–Rényi graphs. JOURNAL OF APPLIED PROBABILITY. ISSN 0021-9002

Preview

Text 2208.12727v3.pdf Available under License Creative Commons Attribution. Download (683kB) | Preview

Abstract

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-avoidin g connected component. It is known 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 fraction of vertices contained in the giant color-avoiding connected component, and we give a simpler asymptotic expression for it in the barely supercritical regime. In addition, 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.

Actions (login required)

Edit Item