Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon

Abstract:

We develop a general universality technique for establishing metric scaling limits of critical random discrete structures exhibiting mean-field behavior that requires four ingredients: (i) from the barely subcritical regime to the critical window, components merge approximately like the multiplicative coalescent, (ii) asymptotics of the susceptibility functions are the same as that of the Erdős-Rényi random graph, (iii) asymptotic negligibility of the maximal component size and the diameter in the barely subcritical regime, and (iv) macroscopic averaging of distances between vertices in the barely subcritical regime.

As an application of the general universality theorem, we establish, under some regularity conditions, the critical percolation scaling limit of graphs that converge, in a suitable topology, to an $L^3$ graphon. In particular, we define a notion of the critical window in this setting. The $L^3$ assumption ensures that the model is in the Erdős-Rényi universality class and that the scaling limit is Brownian. Our results do not assume any specific functional form for the graphon. As a consequence of our results on graphons, we obtain the metric scaling limit for Aldous-Pittel’s RGIV model inside the critical window (see D.J. Aldous and B. Pittel [Random Structures Algorithms 17 (2000), pp. 79–102]).

Our universality principle has applications in a number of other problems including in the study of noise sensitivity of critical random graphs (see E. Lubetzky and Y. Peled [Israel J. Math. 252 (2022), pp. 187–214]). In Bhamidi et al. [Scaling limits and universality II: geometry of maximal components in dynamic random graph models in the critical regime, In preparation], we use our universality theorem to establish the metric scaling limit of critical bounded size rules. Our method should yield the critical metric scaling limit of Ruciński and Wormald’s random graph process with degree restrictions provided an additional technical condition about the barely subcritical behavior of this model can be proved (see A. Ruciński and N. C. Wormald [Combin. Probab. Comput. 1 (1992), pp. 169–180]).