Volume 8 (2025)
Lichev, Lyuben;  Schapira, Bruno
Color-avoiding percolation on the Erdős–Rényi random graph
Annales Henri Lebesgue, Volume 8 (2025), pp. 35-65.

Metadata

DOI10.5802/ahl.228
Keywords color-avoiding percolation, Erdős–Rényi random graph

Abstract

We consider a recently introduced model of color-avoiding percolation (abbreviated CA-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.


References

[Bol01] Bollobás, Béla Random Graphs, Cambridge Studies in Advanced Mathematics, 73, Cambridge University Press, 2001 | DOI | Zbl

[Cur17] Curien, Nicolas Random graphs: the local convergence point of view, 2017 (Unpublished lecture notes. Available at https://www.imo.universite-paris-saclay.fr/~nicolas.curien/cours/cours-RG.pdf)

[DZ10] Dembo, Amir; Zeitouni, Ofer Large deviations techniques and applications, Stochastic Modelling and Applied Probability, 38, Springer, 2010 | DOI | Zbl

[FMRV22] Fekete, Panna T.; Molontay, Roland; Ráth, Balázs; Varga, Kitti Color-avoiding percolation in edge-colored Erdős–Rényi graphs (2022) | arXiv

[FMRV24] Fekete, Panna T.; Molontay, Roland; Ráth, Balázs; Varga, Kitti Color-avoiding percolation and branching processes, J. Appl. Probab., Volume 61 (2024) no. 3, pp. 942-966 | DOI | MR | Zbl

[Gri06] Grimmett, Geoffrey R. The random-cluster model, Grundlehren der Mathematischen Wissenschaften, 333, Springer, 2006 | DOI | MR | Zbl

[Hof17] van der Hofstad, Remco Random graphs and complex networks. Volume 1, Cambridge Series in Statistical and Probabilistic Mathematics, 43, Cambridge University Press, 2017 | DOI | MR | Zbl

[Hof24] van der Hofstad, Remco Random graphs and complex networks. Volume 2, Cambridge Series in Statistical and Probabilistic Mathematics, 54, Cambridge University Press, 2024 | DOI | Zbl

[KDZ16] Krause, Sebastian M.; Danziger, Michael M.; Zlatić, Vinko Hidden connectivity in networks with vulnerable classes of nodes, Phys. Rev. X, Volume 6 (2016) no. 4, 041022 | DOI

[KDZ17] Krause, Sebastian M.; Danziger, Michael M.; Zlatić, Vinko Color-avoiding percolation, Phys. Rev. E, Volume 96 (2017) no. 2, 022313 | DOI

[KKCZ18] Kadović, Andrea; Krause, Sebastian M.; Caldarelli, Guido; Zlatić, Vinko Bond and site color-avoiding percolation in scale-free networks, Phys. Rev. E, Volume 98 (2018) no. 6, 062308 | DOI

[KS66] Kesten, H.; Stigum, B. P. A limit theorem for multidimensional Galton–Watson processes, Ann. Math. Stat., Volume 37 (1966) no. 5, pp. 1211-1223 | DOI | MR | Zbl

[LP17] Last, Günter; Penrose, Mathew Lectures on the Poisson process, Institute of Mathematical Statistics Textbooks, 7, Cambridge University Press, 2017 | DOI | MR | Zbl