Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Optimal couplings between sparse block models
HTML articles powered by AMS MathViewer

by James Hirst PDF
Proc. Amer. Math. Soc. 149 (2021), 97-105 Request permission


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.
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
  • Email:
  • 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
  • © Copyright 2020 American Mathematical Society
  • Journal: Proc. Amer. Math. Soc. 149 (2021), 97-105
  • MSC (2010): Primary 05C80
  • DOI:
  • MathSciNet review: 4172589