Color-avoiding percolation on the Erdős-Rényi random graph
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912141140819968 |
|---|---|
| author | Lichev, Lyuben Schapira, Bruno |
| author_facet | Lichev, Lyuben Schapira, Bruno |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_16086 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Color-avoiding percolation on the Erdős-Rényi random graph Lichev, Lyuben Schapira, Bruno Probability Combinatorics 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. |
| title | Color-avoiding percolation on the Erdős-Rényi random graph |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2211.16086 |