## A sample-path large deviation principle for dynamic Erdős-Rényi random graphs.(English)Zbl 1521.05179

In this paper, a large deviation principle (LDP) is derived for a model of dynamic inhomogeneous random graphs. This random graph process starts with a random graph on $$n$$ vertices which comes from a given graphon. A random process is associated with each one of its edges where it becomes inactive with a certain rate $$\lambda>0$$ and it is activated again at rate $$\mu>0$$, where $$\lambda$$ and $$\mu$$ are real numbers. These random processes are independent. The dynamic gives rise to a graph-valued process $$G_{n,t}$$ and the authors consider this for a finite interval $$[0,T]$$. Equivalently, this may be viewed as a graphon-valued process, since each graph gives rise to a (step) graphon. Using the cut metric on the space of graphons, one can define the Skorohod topology on the set of paths of this process. The authors derive a number of LDPs for this process, under the assumption that the initial graphon converges as $$n\to \infty$$ to a given graphon. The first LDP is for the measure over graphons at time $$T$$. Then an LDP is derived for the joint measure on graphons that occur at times $$t_1 < \cdots < t_k\leq T$$. Finally, an LDP is derived for the measure of this process on the associated graphon-valued space of paths. Thereafter, two applications are discussed. The first is about the typical path that the process follows conditional that it ends up with an atypically large density of copies of a $$d$$-regular graph $$H$$ (with respect to the initial graphon, which is assumed to be constant). In the second application, the uniqueness of the typical path is discussed conditional on the initial and the final graphons being close to two given graphons.

### MSC:

 05C80 Random graphs (graph-theoretic aspects) 60C05 Combinatorial probability 60F10 Large deviations
Full Text:

### References:

 [1] ATHREYA, S., DEN HOLLANDER, F. and RÖLLIN, A. (2021). Graphon-valued stochastic processes from population genetics. Ann. Appl. Probab. 31 1724-1745. · Zbl 1475.92110 · doi:10.1214/20-aap1631 [2] BORGS, C., CHAYES, J., GAUDIO, J., PETTI, S. and SEN, S. (2020). A large deviation principle for block models. Available at arXiv:2007.1450. [3] Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T. and Vesztergombi, K. (2008). Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing. Adv. Math. 219 1801-1851. · Zbl 1213.05161 · doi:10.1016/j.aim.2008.07.008 [4] Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T. and Vesztergombi, K. (2012). Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Ann. of Math. (2) 176 151-219. · Zbl 1247.05124 · doi:10.4007/annals.2012.176.1.2 [5] ČERNÝ, J. and KLIMOVSKY, A. (2020). Markovian dynamics of exchangeable arrays. In Genealogies of Interacting Particle Systems. Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. 38 209-228. World Sci. Publ., Hackensack, NJ. · Zbl 1456.60076 [6] CHATTERJEE, S. (2017). Large Deviations for Random Graphs. Lecture Notes in Math. 2197. Springer, Cham. · Zbl 1375.60009 · doi:10.1007/978-3-319-65816-2 [7] Chatterjee, S. and Varadhan, S. R. S. (2011). The large deviation principle for the Erdős-Rényi random graph. European J. Combin. 32 1000-1017. · Zbl 1230.05259 · doi:10.1016/j.ejc.2011.03.014 [8] Crane, H. (2016). Dynamic random networks and their graph limits. Ann. Appl. Probab. 26 691-721. · Zbl 1342.60163 · doi:10.1214/15-AAP1098 [9] Crane, H. (2017). Exchangeable graph-valued Feller processes. Probab. Theory Related Fields 168 849-899. · Zbl 1367.05193 · doi:10.1007/s00440-016-0726-0 [10] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications, 2nd ed. Applications of Mathematics (New York) 38. Springer, New York. · Zbl 0896.60013 · doi:10.1007/978-1-4612-5320-4 [11] den Hollander, F. (2000). Large Deviations. Fields Institute Monographs 14. Amer. Math. Soc., Providence, RI. [12] DHARA, S. and SEN, S. (2022). Large deviation for uniform graphs with given degrees. Ann. Appl. Probab. 32 2327-2353. · Zbl 1525.05168 · doi:10.1214/21-aap1745 [13] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Wiley, New York. · Zbl 0592.60049 · doi:10.1002/9780470316658 [14] Feng, J. and Kurtz, T. G. (2006). Large Deviations for Stochastic Processes. Mathematical Surveys and Monographs 131. Amer. Math. Soc., Providence, RI. · doi:10.1090/surv/131 [15] FINNER, H. (1992). A generalization of Hölder’s inequality and some probability inequalities. Ann. Probab. 20 1893-1901. · Zbl 0761.60013 [16] GARBE, F., HANCOCK, R., HLADKÝ, J. and SHARIFZADEH, M. (2020). Limits of Latin squares. Available at arXiv:2010.07854. [17] JANSON, S. (2013). Graphons, Cut Norm and Distance, Couplings and Rearrangements. New York Journal of Mathematics. NYJM Monographs 4. State Univ. New York, Albany, NY. · Zbl 1268.05001 [18] Liggett, T. M. (1985). Interacting Particle Systems. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 276. Springer, New York. · Zbl 0559.60078 · doi:10.1007/978-1-4613-8542-4 [19] Lovász, L. (2012). Large Networks and Graph Limits. American Mathematical Society Colloquium Publications 60. Amer. Math. Soc., Providence, RI. · Zbl 1292.05001 · doi:10.1090/coll/060 [20] Lovász, L. and Szegedy, B. (2006). Limits of dense graph sequences. J. Combin. Theory Ser. B 96 933-957. · Zbl 1113.05092 · doi:10.1016/j.jctb.2006.05.002 [21] Lovász, L. and Szegedy, B. (2007). Szemerédi’s lemma for the analyst. Geom. Funct. Anal. 17 252-270. · Zbl 1123.46020 · doi:10.1007/s00039-007-0599-6 [22] Lubetzky, E. and Zhao, Y. (2015). On replica symmetry of large deviations in random graphs. Random Structures Algorithms 47 109-146. · Zbl 1348.05195 · doi:10.1002/rsa.20536 [23] MANDJES, M. (1999). Rare event analysis of the state frequencies of a large number of Markov chains. Commun. Stat., Stoch. Models 15 577-592. · Zbl 0933.60014 · doi:10.1080/15326349908807551 [24] MARKERING, M. (2020). The large deviation principle for inhomogeneous Erdős-Rényi random graphs. Bachelor thesis, Leiden Univ. · Zbl 1515.05161 [25] Ráth, B. (2012). Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics. Random Structures Algorithms 41 365-390. · Zbl 1252.05203 · doi:10.1002/rsa.20422 [26] SHWARTZ, A. and WEISS, A. (1995). Large Deviations for Performance Analysis. Stochastic Modeling Series. CRC Press, London · Zbl 0871.60021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.