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
DOI: https://doi.org/10.1090/proc/15218
Published electronically: October 9, 2020
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
Email: jhirst137@gmail.com

DOI: https://doi.org/10.1090/proc/15218
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