Séminaire des Doctorants et Doctorantes

Color-avoiding percolation on random graphs

par Lyuben Lichev

Europe/Paris
Fokko Ducloux (ICJ)

Fokko Ducloux

ICJ

Description
We will consider a recently introduced model of color-avoiding percolation defined as follows. Every edge in a graph G is colored in some of k 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.
 
In this talk, we will study the structure of CA-components in a randomly colored random graph. Our main focus will be on the size of the largest CA-component. We will see that one may naturally define three regimes - a supercritical, an intermediate, and a subcritical one. After a general introduction to the topic, we will explain the reasons for this change in behavior and study the size of the largest component in all three regimes.