Locality of Random Digraphs on Expanders

We consider random digraphs on a sequence of expanders with bounded average degree. Under the assumption that the original sequence has a weak local limit, we show that the threshold for the existence of a giant strongly connected component, as well as the asymptotic fraction of nodes with a giant fan-in or a giant fan-out are local, in the sense that they are the same for two sequences with the same weak local limit. We prove uniqueness of this strongly connected giant, as well as a bow-tie structure for the nodes with giant fan-in and fan-out and the strongly connected giant.

In the course of proving this, we also prove that for unoriented percolation, there is a unique giant above criticality, whose size and critical threshold are again local. We give explicit formulae for all these quantities in terms of random variables defined on the rooted graph expressing the weak local limits. We make no assumptions on the limit, in particular, we don’t assume that it is tree-like.

As an application of our methods, we show that the critical threshold for bond percolation and random digraphs on preferential attachment graphs is $0$.