Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Optimal couplings between sparse block models

Author: James Hirst
Journal: Proc. Amer. Math. Soc. 149 (2021), 97-105
MSC (2010): Primary 05C80
Published electronically: October 9, 2020
MathSciNet review: 4172589
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the problem of coupling a stochastic block model with a planted bisection to a uniform random graph having the same average degree. Focusing on the regime where the average degree is a constant relative to the number of vertices $n$, we show that the distance to which the models can be coupled undergoes a phase transition from $O(\sqrt {n})$ to $\Omega (n)$ as the planted bisection in the block model varies. This settles half of a conjecture of Bollobás and Riordan and has some implications for sparse graph limit theory. In particular, for certain ranges of parameters, a block model and the corresponding uniform model produce samples which must converge to the same limit point. This implies that any notion of convergence for sequences of graphs with $\Theta (n)$ edges which allows for samples from a limit object to converge back to the limit itself must identify these models.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C80

Retrieve articles in all journals with MSC (2010): 05C80

Additional Information

James Hirst
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
MR Author ID: 1048445

Received by editor(s): October 14, 2019
Received by editor(s) in revised form: June 1, 2020
Published electronically: October 9, 2020
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2020 American Mathematical Society