LOCALITY OF RANDOM DIGRAPHS ON EXPANDERS

• 成果类型: Article
• 署名作者: Alimohammadi, Yeganeh; Borgs, Christian; Saberi, Amin
• 署名单位: Stanford University; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/22-AOP1618
• 发表日期: 2023
• 页码: 1249-1297
• 关键词: giant component; Random graphs; percolation; threshold; size

摘要

We study random digraphs on sequences of expanders with a bounded average degree which converge locally in probability. We prove that the rel-ative size and the threshold for the existence of a giant strongly connected component as well as the asymptotic fraction of nodes with giant fan-in or nodes with giant fan-out are local, in the sense that they are the same for two sequences with the same local limit. The digraph has a bow-tie structure, with all but a vanishing fraction of nodes lying either in the unique strongly con-nected giant and its fan-in and fan-out or in sets with small fan-in and small fan-out. All local quantities are expressed in terms of percolation on the lim-iting rooted graph, without any structural assumptions on the limit, allowing, in particular, for nontree-like graphs. In the course of establishing these results, we generalize previous results on the locality of the size of the giant to expanders of bounded average degree with possibly nontree-like limits. We also show that, regardless of the local convergence of a sequence, the uniqueness of the giant and convergence of its relative size for unoriented percolation imply the bow-tie structure for di-rected percolation. An application of our methods shows that the critical threshold for bond percolation and random digraphs on preferential attachment graphs is pc = 0 with an infinite order phase transition at pc.