Author | Conference | Journal | Organization | Year | DOI
Look for results that meet for the following criteria:
Academic
Publications
Asymptotic equivalence and contiguity of some random graphs
Edit
Asymptotic equivalence and contiguity of some random graphs   (Citations: 13)
BibTex | RIS | RefWorks Download
We show that asymptotic equivalence, in a strong form, holds between two random graph models with slightly diering edge probabilities under substantially weaker conditions than what might naively be expected. One application is a simple proof of a recent result by van den Esker, van der Hofstad and Hooghiemstra on the equivalence between graph distances for some random graph models. (i) The sequence (Pn)n is asymptotically equivalent to (Qn)n, denoted by (Pn)n = (Qn)n, if for every sequence of measurable sets An (i.e., An2An), we have Pn(An) Qn(An)! 0. (ii) The sequence (Pn)n is contiguous with respect to (Qn)n, denoted by (Pn)nC (Qn)n, if for every sequence of measurable sets An such that Qn(An)! 0, we also have Pn(An)! 0. We use the same terminology and notations for sequences of random vari- ables Xn and Yn with values in the same space Xn, meaning that these properties hold for their distributions L(Xn) and L(Yn). For example, (Xn)n = (Yn)n means that P(Xn2 An) P(Yn2 An)! 0 for every sequence (An)n. We will also use the simpler notations Xn = Yn and XnC Yn, etc. Note that asymptotic equivalence is a symmetric relation while contiguity is not; we say that (Pn)n and (Qn)n are (mutually) contiguous, (Pn)nCB (Qn)n, if both (Pn)nC (Qn)n and (Qn)nC (Pn)n, i.e., if Pn(An)! 0 ()
Journal: Random Structures and Algorithms - RSA , vol. 36, no. 1, pp. 26-45, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
More »
    • ...We now show that our results apply to NRn(w); GRGn(w); and CLn(w) all at once: Theorem 2.1 (Asymptotic equivalence [28])...
    • ...Proof. By the results in [28], the random graphs NRn(w); GRGn(w); and CLn(w) are asymptotically equivalent, meaning that all sequences of events have asymptotically equal probabilities, when...
    • ...Proof. First, by the asymptotic equivalence of NRn(w), GRGn(w) and CLn(w) which is established in the proof of Theorem 2.1 using the results in [28], it suces to prove the result for GRG Now, it is well-known that GRGn(w) conditioned on its degrees is uniform from all graphs with those degrees...
    • ...As a result, any limit in probability proved for the CM with this degree sequence also holds for GRGn(w) (see [28])...

    Remco van der Hofstad. Critical behavior in inhomogeneous random graphs

    • ...(Alternatively, and almost equivalently, see [4] and [20], we may use the probability 1 exp( (xi;xj)=n).) We interpret xi as the type of vertex i, and call (S; ) the type space...

    Svante Janson, et al. Susceptibility in inhomogeneous random graphs

    • ...See [12, Section 2], which in turn is based on [14], for more details on the asymptotic equivalence of such inhomogeneous random graphs...

    Shankar Bhamidi, et al. Scaling limits for critical inhomogeneous random graphs with finite th...

    • ...governed by (2.1) holds for > 2 as a consequence of (5.2), a strong general form of asymptotic equivalence is proved in Janson [12]; in the case = 2, when P iW 3 i = op(n 3/2) by (4.2), a somewhat weaker form of equivalence...
    • ...(known as contiguity) holds provided also, say, maxij ij 0.9, see again [12]...

    Svante Janson, et al. Large cliques in a power-law random graph

    • ...See [17, Section 2], which in turn is based on [20], for more details on the asymptotic equivalence of such inhomogeneous random graphs...

    Shankar Bhamidi, et al. Novel scaling limits for critical inhomogeneous random graphs

Order by:

Citations (13)

Share this on | Contribute to Academic