Back to Search
Start Over
Color-avoiding percolation in edge-colored Erd\H{o}s-R\'enyi graphs
- Source :
- Color-avoiding percolation and branching processes. Journal of Applied Probability. Published online 2024:1-25
- Publication Year :
- 2022
-
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\H{o}s-R\'{e}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.<br />Comment: 59 pages + Appendix + List of notation. Added reference to the recent arXiv preprint arXiv:2211.16086
- Subjects :
- Mathematics - Probability
Mathematical Physics
Subjects
Details
- Database :
- arXiv
- Journal :
- Color-avoiding percolation and branching processes. Journal of Applied Probability. Published online 2024:1-25
- Publication Type :
- Report
- Accession number :
- edsarx.2208.12727
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1017/jpr.2023.115