The diameter of inhomogeneous random graphs. Issue 2 (16th May 2018)

• Record Type: Journal Article
• Authors: Fraiman, Nicolas; Mitsche, Dieter
• Is Part Of: Random structures & algorithms. Volume 53:Issue 2(2018)
• Page Start: 308
• Page End: 326
• Publication Date: 2018-05-16
• Subjects: concentration inequalities -- diameter -- neighborhood expansion -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20781
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: In this paper, we study the diameter of inhomogeneous random graphs G ( n, κ, p ) that are induced by irreducible kernels κ . The kernels we consider act on separable metric spaces and are almost everywhere continuous. We generalize results known for the Erdős–Rényi model G ( n, p ) for several ranges of p . We find upper and lower bounds for the diameter of G ( n, κ, p ) in terms of the expansion factor and two explicit constants that depend on the behavior of the kernel over partitions of the metric space.