Color-avoiding percolation of random graphs: between the subcritical and the intermediate regime (Q6080191)

The paper under review is concerned with colour-avoiding (CA) percolation. Here, every edge of a graph \(G=(V,E)\) receives some of \(k\) colours. We say two vertices \(u\) and \(v\) of \(G\) are CA-connected if they can be connected using every \(k-1\) element subset of the \(k\) colours. This is clearly an equivalence relation on \(V\) and the equivalence classes are called CA components. We denote the CA component of a vertex \(u\) by \(\tilde{C}(u)\). In [\textit{L. Lichev} and \textit{B. Schapira}, ``Color-avoiding percolation on the Erdős-Rényi random graph'', Preprint, \url{arXiv:2211.16086}], this is studied for a randomly coloured Erdős-Rényi random graph of constant average degree. It is shown that there are three regimes for this: a supercritical regime in which the CA components have order linear in the number of vertices of \(G\), an intermediate regime in which the CA components have order logarithmic in the number of vertices, and a subcritical regime in which the CA components have a size which is bounded, indeed bounded by the number of colours. Formally, let \(\lambda_{1}\geq \lambda_{2}\dots \geq \lambda_{k}\) be fixed, and \(G_{i}\) be a random graph \(G(n,\lambda_{i}/n)\) (all of these on vertex set \([n]\)) thought of as the edges of colour \(i\). Let \(G\) be the union of these graphs and \(G^{\ell}\) the union of the \(G_{i}\) for all \(1\leq i\leq k\) with \(i\neq \ell\). Similarly let \(\Lambda=\sum_{i=1}^{k}\lambda_{i}\) and \(\lambda_{i}^{\ast}=\Lambda-\lambda_{i}\) for every \(i\) so that the \(\lambda_{i}^{\ast}\) are now an increasing sequence. Then the result is that \(\max_{u\in [n]}\vert \tilde{C}(u)\vert/n\) converges in probability to a constant \(a_{1}\), which is strictly positive if and only if \(\lambda_{1}^{\ast}>1\). If instead we have \(\lambda_{k}^{\ast}>1>\lambda_{k-1}^{\ast}\), then \(\max_{u\in V}\vert \tilde{C}(u)\vert/\log(n)\) converges in probability to a constant \(a_{2}\) and finally if \(\lambda_{k}^{\ast}<1\) then the largest CA component order is bounded above by \(k\) with probability tending to 1. The main contribution of the paper under review is to understand more fully the transition between the subcritical and intermediate regimes. In detail, let \(\zeta=\zeta(n)\) tend to 0 as \(n\rightarrow\infty\). Let \(\lambda_{k}^{\ast}=1+\zeta\) and \(\lambda_{k-1}^{\ast}<1\). Then if \(\log(\zeta^{-1})/\log(n)\rightarrow 0\) as \(n\rightarrow\infty\) we have that \(\max_{u\in [n]}\vert \tilde{C}(u)\vert \log(\zeta^{-1})/\log(n)\) converges in probability to 1. However if instead there is \(\varepsilon>0\) such that \(\zeta\leq n^{-\varepsilon}\) for large enough \(n\), then \(\sup_{n}\mathbb{P}(\max_{u\in [m]}\vert \tilde{C}(u)\vert \geq M)\) tends to 0 as \(M\rightarrow \infty\). Proofs use detailed information on the component sizes in Erdős-Rényi random graphs, but there is also a non-trivial optimisation step involved.