Stochastic processes in random graphs
By Anatolii A. Puhalskii. 2004
49 citations recorded by the source corpus.
We study the asymptotics of large, moderate and normal deviations for the connected components of the sparse random graph by the method of stochastic processes. We obtain the logarithmic asymptotics of large deviations of the joint distribution of the number of connected components, of the sizes of the giant components and of the numbers of the excess edges of the giant components. For the supercritical case, we obtain the asymptotics of normal deviations and the logarithmic asymptotics of large and moderate deviations of the joint distribution of the number of components, of the size of the largest component and of the number of the excess edges of the largest component. For the critical case, we obtain the logarithmic asymptotics of moderate deviations of the joint distribution of the sizes of connected components and of the numbers of the excess edges. Some related asymptotics are also established. The proofs of the large and moderate deviation asymptotics employ methods of idempotent probability theory. As a byproduct of the results, we provide some additional insight into the nature of phase transitions in sparse random graphs.
Subfields: Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/9362ba56245d9a86c29593cd6d4d8ba780032a26
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Mathematical Physics
Citations in the corpus
- Large deviations of empirical neighborhood distribution in sparse random graphs (2013, background): “O’Connell [28], Biskup, Chayes and Smith [6] and Puhalskii [29] have proven large deviation asymptotics for the connectivity and for the size of the connected components.”
- On large deviations of coupled diffusions with time scale separation (2013, unknown): “Puhalskii [39, 40, 42], Puhalskii and Vladimirov [43].”