Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.1. Issue 4 (16th July 2013)

• Record Type: Journal Article
• Authors: Turova, Tatyana S.
• Is Part Of: Random structures & algorithms. Volume 43:Issue 4(2013)
• Page Start: 486
• Page End: 539
• Publication Date: 2013-07-16
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20503
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>Consider the random graph on <italic>n</italic> vertices 1, …, <italic>n</italic>. Each vertex <italic>i</italic> is assigned a type <italic>x</italic><sub><italic>i</italic></sub> with <italic>x</italic><sub>1</sub>, …, <italic>x</italic><sub><italic>n</italic></sub> being independent identically distributed as a nonnegative random variable <italic>X</italic>. We assume that E<italic>X</italic><sup>3</sup>< <italic>∞</italic>. Given types of all vertices, an edge exists between vertices <italic>i</italic> and <italic>j</italic> independent of anything else and with probability <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\min \{1, \frac{x_ix_j}{n}\left(1+\frac{a}{n^{1/3}} \right) \}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg3qnzwn9r" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />. We study the critical phase, which is known to take place when E<italic>X</italic><sup>2</sup> = 1. We prove that normalized by <italic>n</italic><sup>‐2/3</sup>the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\sqrt{{\textbf{ E}}X{\textbf{ E}}X^3}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg3qnzwnw4" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />and drift <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}a-\frac{{\textbf{ E}}X^3}{{\textbf{ E}}X}s\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg3qnzwp09" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />. In particular, we conclude that the size of the largest connected component is of order <italic>n</italic><sup>2/3</sup>. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486–539, 2013</p> </abstract>