Mihyun Kang, Zéphyr Salvy, Ronen Wdowinski
5 min
Abstract
We investigate random connected graphs from a block-stable class whose distribution is weighted based on the number of $2$-connected components, or blocks. This includes the class of planar graphs. For this, we develop a notion of a decorated block tree. Following similar ideas to Fleurat and the second author on block-weighted planar maps, we find a phase transition in the singular behaviour of the appropriate generating function and in the typical structure of the block tree. Moreover, for certain block-stable classes (including planar graphs), we obtain precise enumeration results and determine also the typical sizes of the largest blocks in subcritical, critical, and supercritical regimes. It strengthens previously known results on block sizes in uniform random planar graphs.
Alex: Logarithmic is small, like the height of a balanced tree in computer science. The Gibbs partition ties into why one block doesn't hog everything?
Sam: Yes. At each tree joint, a bouquet of blocks forms, and the biggest claims almost all the size there, minus a small random wiggle. In supercritical graphs, since bouquets stay small, no block grows huge. The paper pins this for planar graphs and classes with a square-root singularity in their block generating function.
Alex: Those block sizes mirror the tree degrees closely—giant linear subcritically, n to the 2/3 at critical, logarithmic supercritical?
Sam: Precisely. In each bouquet, the largest block takes nearly the full size assigned to that spot, minus a bounded random amount from a fixed distribution. The paper calls this a Gibbs partition: one piece hogs most of a fixed total, leaving scraps that stay small and steady. Block sizes follow the same scaling as tree degrees.
Alex: Practically, does this let us generate these graphs on demand, from tree-like to dense?
Sam: Yes—the Boltzmann samplers produce graphs under any u, shifting smoothly from giant-block heavy to tiny-block tree-like as u crosses u_C. This advances understanding in classes like planar or bounded-genus graphs, revealing tree versus graph regimes via block weighting.
Alex: Are there limits to where this analysis holds?
Sam: Yes. It requires the block generating function to have a square-root singularity near its limit for the sharp asymptotics. It applies precisely to planar-like classes, but not yet general minor-closed ones without that behavior. Future work targets those, plus higher genus and scaling limits.
Alex: Fair caveats. Overall, a solid unification of counting and typical structure through that decorated tree lens.
Sam: Exactly. The paper establishes phase transitions in the block tree law, counting asymptotics, and block sizes for block-stable classes, with planar as the showcase. That's the meaningful contribution.
Alex: Well put. Thanks for breaking it down, Sam. Thanks for listening to ResearchPod.