Locality of random digraphs on expanders (Q6116322)

The main results of this paper are about the limiting fraction of the largest and the second largest component of graphs that are the result of edge percolation of a sequence of graphs as well as directed graphs that come from these graphs. More specifically, the first theorem is about the order of the largest and the second largest connected component in the random graph that is the result of edge percolation on a sequence of graphs of bounded average degree that expand well in large sets. Suppose that we have such a sequence of graphs \((G_n)_{n\in \mathbb{N}}\), where \(G_n\) has \(n\) vertices, and \(G_n\) converges locally in probability, as \(n\to \infty\), to a rooted graph \((G,o)\). The latter is a graph that is sampled at random from the space of equivalence classes of locally finite rooted, under the equivalence relation induced by isomorphisms that map roots to roots. Local convergence in probability has to do with the convergence of bounded continuous (in metric defined using balls around the root as in the Benjamini-Schramm convergence) functionals on the graph \(G_n\) with a uniformly chosen root. (The case where \(G_n\) is a random graph is also considered with the appropriate modification.) For \(p\in [0,1]\), let \(G_n(p)\) denote the resulting random graph where each edge of \(G_n\) is retained independently with probability \(p\). If these graphs are expanders with a uniformly bounded average degree, then there is a critical value for \(p\) above which the largest component of \(G_n(p)\) contains a positive fraction of the vertices. A weak law of large numbers is proved. However, the fraction of vertices in the second largest connected component of \(G_n(p)\) is asymptotically (as \(n\to \infty\)) vanishing. This result is generalised to oriented percolation. In this case, each edge \(uv\) of \(G_n\) is replaced by to directed edges \((u,v)\) and \((v,u)\) and, thereafter, each directed edge is retained independently with probability \(p\). The authors show that if \(G_n\) satisfies the dichotomy described in the previous theorem for a range of probabilities, then the second smallest strongly connected component is sublinear with high probability, whereas they characterise when the largest strongly connected component is linear.