Block-weighted random graphs: planar and beyond Mihyun Kang, Zéphyr Salvy, Ronen Wdowinski Abstract We investigate random connected graphs from a block-stable class whose distribution is weighted based on the number of 2 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. TU Graz, Institute of Discrete Mathematics, Steyrergasse 30, 8010 Graz, Austriakang@math.tugraz.at TU Wien, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstrasse 8-10, 1040 Vienna, Austriazephyr.salvy@tuwien.ac.at TU Graz, Institute of Discrete Mathematics, Steyrergasse 30, 8010 Graz, Austriawdowinski@math.tugraz.at ccs Mathematics of computing Combinatorics ccs Mathematics of computing Discrete mathematics ccs Mathematics of computing Enumeration ccs Mathematics of computing Generating functions ccs Mathematics of computing Probability and statistics ccs Mathematics of computing Stochastic processes keywords Bienaymé trees; Block sizes; Block-stable graphs; Boltzmann laws; Planar graphs † † runningauthor: M. Kang, Z. Salvy and R. Wdowinski † † copyright: Mihyun Kang, Zéphyr Salvy and Ronen Wdowinski † † funding: This research was supported by the Austrian Science Fund (FWF) [10.55776/F1002]. † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction 1.1 Motivation and background Planar maps and planar graphs have received much attention from enumerative and probabilistic points of view. The study of planar map enumeration started with the groundbreaking combinatorial work of Tutte, who gave a close formula for the number of rooted planar maps of size n in the 1960s [ 32 ] . Tutte’s work prompted many perspectives and extensions since [ 9 , 10 , 22 , 23 , 29 ] . Despite extensive studies, the asymptotic number of planar graphs were successfully determined only much more recently by Giménez and Noy [ 18 ] in 2009, building on work of Bender, Gao, and Wormald [ 5 ] . Many results on planar maps and planar graphs rely on applying decompositions that work in tree-like fashion, allowing combinatorial properties to be deduced. A prominent example of this theme is the block decomposition . For both planar maps and connected planar graphs, there is a unique way to decompose them into maximal 2 -connected submaps or subgraphs, called blocks (see, e.g., [ 11 , 19 , 32 ] ). In both cases, one can construct tree-like structures by viewing the blocks as vertices of a graph whose edges join overlapping blocks. In the case of planar maps, such a tree was described by Addario-Berry [ 2 ] , following Tutte’s description of the block decomposition [ 32 ] . Moreover, Addario-Berry [ 2 ] showed that this tree could be used to obtain information about random planar maps: Since the block tree of a uniform planar map of size n follows the law of a Bienaymé tree 1 1 1 Also called Galton–Watson tree or Bienaymé–Galton–Watson tree , we adopt the change of notation proposed by Addario-Berry, Brandenberger, Hamdan, and Kerriou [ 1 ] . , whose properties are well-known, properties on the sizes of the 2 -connected components of a random map follow. It was subsequently shown that this approach fruitfully allows one to consider block-weighted models : instead of sampling according to a uniform law, one considers a parameter u>0 , and samples a map of size n with probability proportional to u to the power of its number of blocks. (Note that u=1 corresponds to the usual uniform law.) Fleurat and the second author [ 15 ] showed that the block tree of such a random planar map still follows a Bienaymé law, and used this to obtain results on the sizes of blocks of such maps as well as scaling limits. More precisely, they discovered a phase transition between the universality classes of maps (converging to the Brownian sphere) and plane trees (converging to the Brownian tree), depending on the value of u , obtaining precise results on block sizes in each phase. Using an extensive list of decomposition of maps into subfamilies [ 4 ] , the second author [ 27 , 28 ] showed that this approach can be successfully adapted to deal with different decompositions of maps, giving a very similar phase transition between a “map phase” and a “tree phase”. Albenque, Fusy, and the second author [ 3 ] used this approach for a family of decorated maps, which are planar maps endowed with one of their spanning tree. They found a phase transition between a “tree-rooted map phase” and a “tree phase”. Since this technique of using block decompositions to obtain interesting results for planar maps is robust, it is intriguing to extend this approach to connected planar graphs . The planar graph case is slightly more intricate than the planar map case because one has to take into account the labelling and cannot rely on an embedding as in the map case. 1.2 Main results The main contributions of this paper are two-fold. First, we show that a random connected rooted labelled graph from a block-stable class (e.g., a random connected planar graph), which is sampled according to a block-weighted law, exhibits a phase transition (see \cref thm:phase-transition). To this end, we introduce a decorated block tree that encodes a block decomposition of such a connected graph (see \cref sec:decorated). This extends the lines of previous study based on a block tree decomposition from planar maps to connected planar graphs . Because block-stable classes are very general, our results are also very general, but not necessarily precise. Second, we show how the block tree methodology can be used to obtain more precise results. First, we use it to obtain enumeration results for the block-weighted generating function. Then we determine the distribution of block sizes of random block-weighted planar graphs and block-stable graphs of the same singular type (see \cref thm:block-sizes). As a result, we obtain more precise information on block size of a uniform random connected planar graph than what was previously known in the literature [ 17 , 25 ] . 1.2.1 Phase transition in block-weighted block-stable graphs A class \mathcal{C} of connected graphs is said to be block-stable if for each graph \mathfrak{g}\in\mathcal{C} each of its 2 -connected components (called blocks ) belongs to \mathcal{C} . Write \mathcal{B} for the class of 2 -connected elements of \mathcal{C} . Write B(y) and C(x) for the corresponding exponential generating functions (EGFs), and set C^{\bullet}(x)=xC(x) . It was shown, e.g., by Robinson [ 26 , Theorem 4] , that C^{\bullet}(x)=x\exp(B^{\prime}(C^{\bullet}(x))). (1) As we will see in \cref subsec:anal-comb-block-tree, this equation can be translated into a “decorated” block tree. More precisely, let C^{\bullet}(x,u) be the exponential generating function for connected rooted graphs of \mathcal{C} , where x marks vertices and u marks blocks. Write \rho(u) for the radius of convergence of C^{\bullet}(\cdot,u) . For u>0 , we consider the following block-weighted probability laws on \mathcal{C}^{\bullet} : for a graph \mathfrak{g}\in\mathcal{C} of size |\mathfrak{g}| with b(\mathfrak{g}) many 2 -connected components, we set \mathbb{P}_{u}\left(\mathfrak{g}\right):=\frac{\rho(u)^{|\mathfrak{g}|}u^{b(\mathfrak{g})}}{|\mathfrak{g}|!C^{\bullet}(\rho(u),u)},\qquad\text{and}\qquad\mathbb{P}_{n,u}\left(\mathfrak{g}\right):=\frac{u^{b(\mathfrak{g})}}{[x^{n}]C^{\bullet}(x,u)}\text{1}_{|\mathfrak{g}|=n}. We show that, when considering a block-weighted law on a connected rooted graphs from a block-stable classes (including connected rooted planar graphs), this block tree follows a Bienaymé tree distribution (see \cref prop:law-TG). Our first main theorem is about phase transitions in the criticality of this Bienaymé tree. Theorem 1 . Let \mathcal{C} be a block-stable class of connected graphs, let \mathcal{B} be its class of 2 -connected components whose EGF we denote by B(y) , and let \rho_{B} be the radius of convergence of B . Let u_{C}:=\frac{1}{\rho_{B}B^{\prime\prime}(\rho_{B})}. Then the following hold. • The singular behaviour of C^{\bullet}(x,u) depends on the relative positions of u and u_{C} ; • The block tree corresponding to a graph drawn according to \mathbb{P}_{n,u} follows a subcritical Bienaymé tree law if u1 , it is known that the graphs behave “tree-like”, which is consistent with u_{C}<1 and the uniform case being supercritical. On the contrary, when \rho_{B}B^{\prime\prime}(\rho_{B})<1 , the graphs behave as general planar graphs do, which is consistent with u_{C}>1 . We note that block-weighted block-stable graph classes were already considered by Stufler [ 30 , §5] in a general setting using the framework of Gibbs partitions, but our current work has a different focus. 1.2.2 Enumeration and block sizes in block-weighted planar graphs Our next results focus on the case where B^{\prime} has a singularity of type 3/2 (which encompasses planar graphs). Under this assumption, we also show how the phase transition described in \cref thm:phase-transition affects the behaviour of [x^{n}]C^{\bullet}(x,u) , as well as the typical sizes of blocks. The following is our main result on the former. Theorem 2 . For every u>0 , there exist c>0 , c_{1}(u)>0 , and c_{2}(u)>0 such that: • in the subcritical phase uu_{C} , [x^{n}]C^{\bullet}(x,u)\underset{n\to\infty}{\sim}c_{2}(u)n^{-3/2}\rho(u)^{-n}. For a more precise version of this theorem, see \cref th:dvp-sing-Cbxu. Thus, in the subcritical phase, the polynomial correction is that of rooted graphs: n^{-5/2} . Conversely, in the supercritical phase, the correction is that of plane trees: n^{-3/2} . This justifies why one can view the subcritical phase as a “general rooted graph phase” and the supercritical phase as a “tree phase”. It is worth noting that in the critical phase, i.e., when u=u_{C} , a novel asymptotic behaviour emerges, characterised by a polynomial correction of n^{-5/3} . The next theorem summarises our main results on the typical block sizes in the three different phases. Theorem 3 . There is a phase transition for block sizes depending on the value of u : • In the subcritical phase uu_{C} , there is a largest block of size \Theta_{\mathbb{P}}(\ln(n)) and likewise for the next largest block sizes. As we will see in \cref thm:phasetransition_block_sizes, we also determine precise limit laws for the block sizes when appropriately scaled, in the subcritical and critical cases, and provide a more precise description of what happens in the supercritical case. Our results extend some previous work in the literature [ 17 , 25 ] from uniform to block-weighted random planar graphs. In fact, the above two results hold for any block-stable class where B^{\prime} is singular with exponent 3/2 (for a definition, see e.g., [ 4 , Equation (46)] ). This includes the class of planar graphs as shown by Bender, Gao, and Wormald [ 5 ] (see \cref eq:asymp-exp-B’ for the singular expansion of B^{\prime} ). 1.3 Key proof techniques and related work The primary proof methods used in this paper build on those used for block-weighted planar maps in [ 15 ] , with some ideas originating from [ 2 ] . The Lagrangean form of \cref eq:Cbullet-block implicitly gives a tree-like structure and we make it combinatorially explicit in the form of a decorated block tree , detailed in \cref subsec:anal-comb-block-tree. Our decorated block tree looks similar to the usual notion of a block decomposition of a connected graph, but is different in that the vertices of our tree represent cut-vertices instead of blocks, and these cut-vertices are decorated by sets of blocks. We use tools from singularity analysis and results about Bienaymé trees to pinpoint and describe a phase transition, as in \cref thm:phase-transition,thm:enum. To prove our results about typical block sizes in random block-weighted planar graphs, as in \cref thm:block-sizes, we also incorporate some ideas on planar maps from [ 15 ] , but extra steps are needed due to the fact that our block tree decorations are not blocks, but sets of blocks , or more precisely, elements of the class \mathrm{Set}\circ\mathcal{B}^{\prime} . First we apply known results on degree distributions of Bienaymé trees (by, e.g., Janson [ 21 ] ) to our block tree. Then we combine this with results on Gibbs partitions by Stufler [ 31 ] to deduce typical block sizes. Similar ideas were used to study block-weighted simple triangulations in [ 28 , §4.2] , where the decorations were sequences of blocks. Finally, we mention some other related works. In the uniform case, Panagiotou and Steger [ 25 ] proved a dichotomy theorem on the behaviour of the size of a largest block in connected graph classes: For classes similar to planar graphs there is a unique largest block of linear size almost surely, whereas for classes similar to series-parallel graphs all components are at most logarithmic in size almost surely. Giménez, Noy, and Rué [ 17 , Theorem 5.4] subsequently refined the dichotomy theorem of Panagiotou and Steger [ 25 ] and also showed a limiting distribution on the sizes of the largest blocks, involving the Airy distribution. As mentioned earlier, our work considers in particular planar graphs with block weights and thus generalises some of the results in the works above. 1.4 Plan of the paper In \cref sec:preliminaries, we give notation and recall usual notions of block decompositions of graphs. In \cref sec:decorated, we detail the construction of the decorated block tree of a rooted graph. In \cref sec:block-weighted, we introduce the block-weighted model for block-stable graph classes and obtain results about it. In \cref sec:block-sizes, we focus on classes where B^{\prime} is singular with exponent 3/2 (which includes planar graphs), and obtain results on enumeration and block sizes. In \cref sec:conclusion, we discuss possible extensions and future work. 2 Preliminaries 2.1 Notation The set of natural numbers is written as \mathbb{N}_{0}=\{0,1,2,\dots\} . For n\in\mathbb{N}_{0} , p\in\mathbb{N}_{0} , k_{1},\dots,k_{p}\in\mathbb{N}_{0} such that \sum_{i=1}^{p}k_{i}=n , a multinomial coefficient is defined as \binom{n}{k_{1},\dots,k_{p}}\coloneqq\frac{n!}{k_{1}!\cdots k_{p}!}. By convention, 0!=1 . For a sequence (A_{n})_{n\in\mathbb{N}_{0}} of random variables and a positive sequence (a_{n}) , one writes: • A_{n}=O_{\mathbb{P}}(a_{n}) to mean that, for all sequences (u_{n}) of positive numbers that tend to +\infty , \mathbb{P}\left(|A_{n}|\leq a_{n}u_{n}\right)\xrightarrow[n\to\infty]{}1; • A_{n}=\Theta_{\mathbb{P}}(a_{n}) to mean that, for all sequences (u_{n}) of positive numbers that tend to +\infty , \mathbb{P}\left(\frac{a_{n}}{u_{n}}\leq|A_{n}|\leq a_{n}u_{n}\right)\xrightarrow[n\to\infty]{}1. We also use standard Landau notation (e.g., O(\cdot),\Theta(\cdot) ) in the non-probabilistic setting. 2.2 Labelled classes An object of size n is said to be well-labelled if its collection of labels is exactly the elements of the integer interval [1,n]\coloneqq\{1,2,\ldots,n\} . When relabelling one or several objects with labels, the relabelling is said to be consistent if it preserves the order relations among labels (for more information, see, e.g., [ 14 , II.2] ). The elements of a labelled combinatorial class are always well-labelled. The size of such an element is its number of labelled atoms. 2.3 Graphs and their generating functions All graphs considered in this paper are simple. For a graph \mathfrak{g} , let V(\mathfrak{g}) (resp. E(\mathfrak{g}) ) denote its set of vertices (resp. edges). Unless stated otherwise, the graphs are vertex-labelled with labels ranging from 1 to |V(\mathfrak{g})| . A rooted graph is a graph with a distinguished vertex. A derived graph \mathfrak{g} is a graph with one unlabelled vertex, where the other vertices are labelled with a number between 1 and |V(\mathfrak{g})|-1 . The size of a graph \mathfrak{g} is the number of labelled vertices in \mathfrak{g} and is denoted by |\mathfrak{g}| . Let \mathcal{C} be a block-stable class of connected graphs, and let \mathcal{B} be the subclass of 2 -connected elements. Let \mathcal{C}^{\bullet} be the class of rooted elements of \mathcal{C} and let \mathcal{B}^{\prime} the class of derived elements of \mathcal{B} . We write C(x) , B(y) , C^{\bullet}(x) , B^{\prime}(y) for the associated exponential generating functions. Let \rho_{C} (resp. \rho_{B} ) be the radius of convergence of C(x) (resp. B(y) ). It holds that C^{\bullet}(x)=xC^{\prime}(x) . For the case of the class of planar graphs, Bender, Gao, and Wormald [ 5 ] showed that B^{\prime} has a unique dominant singularity \rho_{B} and has the following singular expansion in a \Delta -domain around \rho_{B} : B^{\prime}(y)=B^{\prime}(\rho_{B})-B^{\prime\prime}(\rho_{B})(\rho_{B}-y)+c_{B}(\rho_{B}-y)^{3/2}+O\left((\rho_{B}-y)^{2}\right) (2) for some constant c_{B}\in\mathbb{R}^{*} . By a transfer theorem (see, e.g., [ 14 , Theorem VI.1] ), this implies that [y^{n}]B^{\prime}(y)\underset{n\to\infty}{\sim}\frac{c_{B}\rho_{B}^{3/2}}{\Gamma(-3/2)}\rho_{B}^{-n}n^{-5/2}. (3) 2.4 Block decomposition of a connected graph It is well-known that every connected graph can be uniquely decomposed into maximal 2 -connected subgraphs, called blocks , which can overlap in at most one vertex (see e.g., [ 11 , 19 ] ). We consider a single edge to be 2 -connected, but not a single vertex. A vertex where two or more blocks overlap is called a cut-vertex . The resulting block decomposition of a graph \mathfrak{g} is usually described in one of the following two ways: 1. Block graph B(\mathfrak{g}) (see e.g., [ 19 ] ): The vertices of B(\mathfrak{g}) are the blocks of \mathfrak{g} , and two blocks are joined by an edge in B(\mathfrak{g}) if they overlap at a vertex. The resulting graph B(\mathfrak{g}) is characterised by the property of being connected and that all of its blocks are cliques. 2. Block-cut graph T(\mathfrak{g}) (see e.g., [ 11 ] ): The vertices of T(\mathfrak{g}) are the blocks and the cut-vertices of \mathfrak{g} , and a cut-vertex is joined to a block by an edge in T(\mathfrak{g}) if that vertex is contained in that block. The resulting graph T(\mathfrak{g}) is a tree. In the present work, we use an alternative block decomposition that naturally arises from the Lagrangean form of ( 1 ) of the generating series C^{\bullet}(x) . It originates from work of Addario-Berry [ 2 ] on planar maps (see also [ 28 ] ), and we give a precise algorithmic description in \cref subsec:anal-comb-block-tree. We note that this construction works specifically for rooted labelled connected graphs, and we call its output a decorated block tree . In a decorated block tree, the vertices represent all the vertices of the original graph \mathfrak{g} but each vertex is decorated by a set of blocks that contain that vertex. In [ 2 ] , the decorations were simply blocks, but in our construction the decorations are more general sets of blocks . 3 Decorated block trees of connected block-stable graphs In this section, we describe decorated block trees , which are a central tool in our analysis. 3.1 Construction of decorated block tree Recalling the Lagrangean form of \cref eq:Cbullet-block, we define \Phi(y)=\sum_{k=0}^{\infty}\frac{\phi_{k}}{k!}y^{k}\coloneqq\exp(B^{\prime}(y))\in\mathbb{C}[[y]], (4) which is precisely the exponential generating function for the class \mathrm{Set}\circ\mathcal{B}^{\prime} . For convenience we also use \Phi to denote the class \mathrm{Set}\circ\mathcal{B}^{\prime} . It follows from \cref eq:Cbullet-block that C^{\bullet}(x)=x\Phi(C^{\bullet}(x)). As explained in [ 28 , §2.2.1] , there is a systematic way to define a (plane) block tree from a Lagrangean decomposition scheme. Namely, each vertex of the tree is decorated with an object \varphi from the class \Phi , and the subtrees attached to a vertex of the tree (corresponding to some \varphi ) are the trees of the rooted graphs substituted into \varphi . The situation in the case of graphs is a little more involved than in the case of maps because of the labelling possibilities. Thus, we use the following notion. Remember that elements of the class \Phi are well-labelled. Therefore, for each \mathfrak{g}\in\mathcal{C} , when we consider sets of derived blocks of \mathfrak{g} , it is always implied that the set has been relabelled with a well-labelling which is consistent with the order of the labels in \mathfrak{g} . Figure 1: The image on the left is a connected labelled rooted planar graph \mathfrak{g} , with root highlighted in grey. The image on the right is the associated decorated block tree {T}_{\mathfrak{g}} . Now, we give an algorithmic definition of decorated block trees. An example is provided in \cref fig:block-tree-2. Definition 4 . For \mathfrak{g}\in\mathcal{C}^{\bullet} (which for ease of presentation \mathfrak{g} is also allowed to be a rooted derived graph, with a root and one unlabelled non-root vertex), we define the decorated block tree {T}_{\mathfrak{g}} as the result of the following construction: 1. Let r be the root of \mathfrak{g} , and let \varphi=\{\mathfrak{b}^{\prime}_{1},\ldots,\mathfrak{b}^{\prime}_{\ell}\} be the set of derived blocks containing r and no unlabelled vertex in \mathfrak{g} , where the label of the vertex corresponding to r is removed. Start with a root vertex r_{{T}} in {T}_{\mathfrak{g}} and decorate it with \varphi . 2. For i\in\{1,\ldots,\ell\} , we construct a derived graph \mathfrak{g}^{\prime}_{\mathfrak{b}_{i}} by deleting r from \mathfrak{g} , keeping the connected component of \mathfrak{g} that intersects \mathfrak{b}^{\prime}_{i} , and then adding r back to this subgraph. We consistently relabel the vertices of \mathfrak{g}^{\prime}_{\mathfrak{b}_{i}} except r which remains unlabelled. For every labelled vertex v of \mathfrak{b}^{\prime}_{i} , we construct the rooted derived graph \mathfrak{g}_{(v)} by rooting \mathfrak{g}_{\mathfrak{b}_{i}}^{\prime} at v (and keeping the unlabelled vertex). 3. For v a vertex in \varphi , in increasing order of label in \varphi , let \mathfrak{t}_{v}:={T}_{\mathfrak{g}_{(v)}} be the decorated block tree on this rooted subgraph with an unlabelled vertex. Add \mathfrak{t}_{v} as the rightmost child of r_{{T}} . This finishes the construction the decorated block tree. In addition, we define the block tree of \mathfrak{g} to be the result of forgetting the decorations of {T}_{\mathfrak{g}} , giving a plane tree. Notice that, contrary to the more traditional block-cut tree described in \cref subsec:block-decomp-tradi, one cannot use the undecorated block tree to directly read off the number of blocks in the original graph. On the other hand, the number of vertices of the block tree is the same as the number of vertices of the original graph. In addition, the outdegree of a vertex in the block tree is equal to the size of the set that decorates it. In particular, leaves are decorated by the empty set. 3.2 Reverse construction In \cref subsec:anal-comb-block-tree we described how to construct both a decorated and undecorated rooted plane tree from a given graph in \mathcal{C}^{\bullet} , with the decorations given by sets of derived blocks. One can reverse this construction to obtain a graph of \mathcal{C}^{\bullet} from a decorated block tree. This comes from gluing together the blocks that decorate a given vertex of the block tree, where the gluing happens along the unlabelled vertex at each of those blocks. Then we identify vertices across different gluings based on their ordering in the (plane) block tree. Now, there may be multiple labelled graphs with the same decorated block tree because our vertex decorations are well-labellings , and there are multiple labellings of the original graph that result in the same well-labelling in a decoration. However, once we fix both a decorated block tree and an allocation of the appropriate number of labels to the root of the graph and to the decorated vertices of the block tree, one can associate a unique graph. This leads to the following proposition, quantifying the number labelled connected rooted graphs with the same decorated block tree. Recall that \Phi is the class \mathrm{Set}\circ\mathcal{B}^{\prime} , with EGF defined in \cref eq:def-Phi. Proposition 5 . Let \mathfrak{t} be a rooted plane tree with n vertices. Let d_{1},\ldots,d_{n} be the outdegrees of its vertices. There are {\mathrm{dec}}(\mathfrak{t})\coloneqq\prod_{i=1}^{n}\phi_{d_{i}} ways to decorate the vertices of \mathfrak{t} with an element of the class \Phi of size equal to the outdegree of the vertex. Moreover, it holds that \left|\left\{\mathfrak{g}\in\mathcal{C}^{\bullet}\mid{T}_{g}=\mathfrak{t}\right\}\right|={\mathrm{dec}}(\mathfrak{t})\cdot n\binom{n-1}{d_{1},\dots,d_{n}}. 4 Block-weighted laws for block-stable classes In this section, we study the main objects of this paper, namely block-weighted connected graphs. We recall that these are graphs sampled according to a block-weighted law. As explained in the introduction, let C^{\bullet}(x,u) be the exponential generating function for connected rooted graphs of \mathcal{C} , where x marks vertices and u marks blocks. Let \rho(u) denote the radius of convergence of C^{\bullet}(\cdot,u) . From now on, we always assume u>0 . We consider the following block-weighted probability laws on \mathcal{C}^{\bullet} : For a graph \mathfrak{g}\in\mathcal{C}^{\bullet} with b(\mathfrak{g}) many 2 -connected components, we set \mathbb{P}_{u}\left(\mathfrak{g}\right):=\frac{\rho(u)^{|\mathfrak{g}|}u^{b(\mathfrak{g})}}{|\mathfrak{g}|!C^{\bullet}(\rho(u),u)}\qquad\text{and}\qquad\mathbb{P}_{n,u}\left(\mathfrak{g}\right):=\frac{u^{b(\mathfrak{g})}}{[x^{n}]C^{\bullet}(x,u)}\text{1}_{|\mathfrak{g}|=n}. 4.1 Law of (decorated) block trees Letting \Phi(y,u):=\exp\left(uB^{\prime}(y)\right) , we have the following version of \cref eq:Cbullet-block: C^{\bullet}(x,u)=x\exp\left(uB^{\prime}(C^{\bullet}(x,u))\right)=x\Phi(C^{\bullet}(x,u),u). (5) \cref eq:Cbullet-u can readily be translated into Boltzmann samplers (see [ 13 , 16 ] ), which we write explicitly in \cref algoCbul,algoPhi below. Algorithm 1 \Gamma C^{\bullet}(x,u) for x\leq\rho(u) y=C^{\bullet}(x,u) \varphi=\Gamma\Phi(y,u) // see \cref algoPhi n=|\varphi| for i=1 to n do \mathfrak{c}_{i}=\Gamma C^{\bullet}(x,u) Attach \mathfrak{c}_{i} to the i -th atom of \varphi end for Attach all the elements of \varphi by merging all the unlabelled vertices Root in its unlabelled root vertex and add a label to it Reshuffle the labels of \varphi return \varphi Algorithm 2 \Gamma\Phi(y,u) for y\leq\rho_{B} k=\operatorname{Poisson}\left(uB^{\prime}(y)\right) \mathfrak{b}_{1},\dots,\mathfrak{b}_{k}=(\Gamma(uB^{\prime})(y))_{1\leq i\leq k} // k independent calls \varphi=\{\mathfrak{b}_{1},\dots,\mathfrak{b}_{k}\} Reshuffle the labels of \varphi return \varphi As explained in [ 28 , §2.2.3] , a Boltzmann sampler for a class corresponding to a Lagrangean equation produces an object whose internal structure is a Bienaymé tree. For \cref algoCbul, the root of the tree corresponds to \varphi and has n children, where n is the size of a random object obtained by \cref algoPhi, and for each child the same process applies. The reproduction law of this Bienaymé tree is given by the size distribution of the output of \cref algoPhi, which is a Boltzmann sampler. For y(u)=C^{\bullet}(\rho(u),u) , we define the probability law {\mu}^{u}(j)\coloneqq\frac{[y^{j}]\Phi(y,u)\,y(u)^{j}}{\Phi(y(u),u)}\quad\text{for }j\in\mathbb{N}_{0}. (6) For notation in the proposition below, given a decorated block tree \mathfrak{t} and vertex v of \mathfrak{t} , we let d_{\mathfrak{t}}(v) denote the outdegree of v . We write \mathrm{Bienaym\acute{e}}\left(\mu\right) for the distribution of a Bienaymé tree with reproduction law \mu , and \mathrm{Bienaym\acute{e}}\left(\mu,n\right) when the output is additionally conditioned to have n vertices. Proposition 6 . Fix u>0 , let \mathbf{G} be distributed according to \mathbb{P}_{u} , and denote by ({\mathbf{T}},(\boldsymbol{\varphi}_{v},v\in{\mathbf{T}})) the decorated block tree {T}_{\mathbf{G}} , where {\mathbf{T}} is the undecorated block tree and (\boldsymbol{\varphi}_{v},v\in{\mathbf{T}}) is its family of vertex decorations. Then the law of {T}_{\mathbf{G}} can be described as follows: • {\mathbf{T}} follows the law \mathrm{Bienaym\acute{e}}\left({\mu}^{u}\right) ; • Conditionally given {\mathbf{T}}=\mathfrak{t} , the decorations (\boldsymbol{\varphi}_{v},v\in\mathfrak{t}) are independent random variables, and, for v\in\mathfrak{t} , \boldsymbol{\varphi}_{v} is distributed according to \Gamma\Phi(C^{\bullet}(\rho(u),u),u) conditioned to have size d_{\mathfrak{t}}(v) . For every n\in\mathbb{N}_{>0} , the same statements hold under \mathbb{P}_{n,u} , only replacing \mathrm{Bienaym\acute{e}}\left({\mu}^{u}\right) with \mathrm{Bienaym\acute{e}}\left({\mu}^{u},n\right) . Remark 7 . In the special case u=1 , the last item can be rewritten as follows: Conditionally given {\mathbf{T}}=\mathfrak{t} , the blocks (\boldsymbol{\varphi}_{v},v\in\mathfrak{t}) are independent random variables, and, for v\in\mathfrak{t} , \boldsymbol{\varphi}_{v} follows a uniform distribution on the set of elements of \mathrm{Set}\circ\mathcal{B}^{\prime} of size d_{\mathfrak{t}}(v) . Indeed, in the case u=1 , \Gamma\Phi(C^{\bullet}(\rho(u),u),u) is uniform on elements of the same size, which is not the case when u\neq 1 . Remark 8 . Conditionally given {\mathbf{T}}=\mathfrak{t} , it is not true a priori that the number of derived blocks in the decoration of v\in V(\mathfrak{t}) follows a \operatorname{Poisson}\left(uB^{\prime}(y)\right) law. This only holds when there is no conditioning. 4.2 Phase transition of block-weighted graphs Bienaymé trees exhibit a phase transition depending on the mean of their reproduction law (see, e.g., [ 24 ] ). It is easy to compute that \mathbb{E}\left[{\mu}^{u}\right]=\frac{y(u)\Phi^{\prime}(y(u),u)}{\Phi(y(u),u)}=uy(u)B^{\prime\prime}(y(u)), (7) where the derivation of the function \Phi is done with respect to the first variable. Therefore, \mathbb{E}\left[{\mu}^{u}\right]=1\iff y(u)=\frac{1}{uB^{\prime\prime}(y(u))}. To understand the behaviour of y(u) and, more generally, to exhibit a phase transition for block-weighted graphs from block-stable classes, one looks into the singularity \rho(u) of C^{\bullet}(\cdot,u) . From \cref eq:Cbullet-u, there are two possible sources of singularity: 1. The first case when y(u)=\rho_{B} . In this case, we have \rho_{B}=\rho(u)\exp(uB^{\prime}(\rho_{B})) , i.e., \rho(u)=\rho_{B}\exp(-uB^{\prime}(\rho_{B})). 2. The second case when \frac{\partial F}{\partial c}(\rho(u),y(u))=0 where F:(x,c)\mapsto c-x\exp(uB^{\prime}(c)) . In this case, we have \rho(u)=\frac{1}{uB^{\prime\prime}(y(u))\exp(uB^{\prime}(y(u)))}. Since by definition we have \rho(u)=y(u)\exp\left(-uB^{\prime}(y(u))\right) , it holds that y(u)=\frac{1}{uB^{\prime\prime}(y(u))}. Consider the equation y=\frac{1}{uB^{\prime\prime}(y)} , or equivalently u=\frac{1}{yB^{\prime\prime}(y)} . The function y\mapsto yB^{\prime\prime}(y) is increasing for y\in[0,\rho_{B}] , with range in [0,\rho_{B}B^{\prime\prime}(\rho_{B})] , so this equation has a solution (which is unique) if and only if u\geq 1/(\rho_{B}B^{\prime\prime}(\rho_{B})) . These considerations imply the following theorem. Theorem 9 . Let \mathcal{C} be a block-stable class of connected graphs, let \mathcal{B} be its class of 2 -connected components with EGF B(y) , and let \rho_{B} denote the radius of convergence of B . Let u_{C}:=\frac{1}{\rho_{B}B^{\prime\prime}(\rho_{B})}. Then the radius of convergence \rho(u) of the series C^{\bullet}(\cdot,u) (on block-weighted rooted elements of \mathcal{C} ) and y(u)=C^{\bullet}(\rho(u),u) satisfy the following: • If u\leq u_{C} , then \rho(u)=\frac{\rho_{B}}{\exp(uB^{\prime}(\rho_{B}))}\qquad\text{and}\qquad y(u)=\rho_{B}; • If u\geq u_{C} , then \rho(u)=\frac{1}{uB^{\prime\prime}(y(u))\exp(uB^{\prime}(y(u)))}\qquad\text{and}\qquad y(u)=\frac{1}{uB^{\prime\prime}(y(u))}. Remark 10 . When considering the block-stable class of connected planar graphs , it holds that \rho_{B}B^{\prime\prime}(\rho_{B})<1 [ 18 , Claim 1] , so in fact u_{C}>1 and uniform planar graphs fall into the subcritical case. It holds that u_{C}\approx 24.837\dots Together with \cref eq:Exp-muT-u,prop:law-TG, \cref th:phase-trans-singular implies the following. Theorem 11 . Let \mathbf{G}_{n,u} be a graph of size n from a block stable class distributed according to \mathbb{P}_{n,u} . Then its block tree \mathbf{T}_{n,u} follows the law \mathrm{Bienaym\acute{e}}\left({\mu}^{u},n\right) where {\mu}^{u} satisfies the following. • If u0 . Moreover, using the notation of \cref eq:asymp-exp-B’, it holds for y in a \Delta -domain around \rho_{B} that \displaystyle\Phi(y,u) \displaystyle=\exp\left(uB^{\prime}(\rho_{B})-uB^{\prime\prime}(\rho_{B})(\rho_{B}-y)+uc_{B}(\rho_{B}-y)^{3/2}+O\left((\rho_{B}-y)^{2}\right)\right) \displaystyle=\exp\left(uB^{\prime}(\rho_{B})\right)\left(1-uB^{\prime\prime}(\rho_{B})(\rho_{B}-y)+uc_{B}(\rho_{B}-y)^{3/2}+O\left((\rho_{B}-y)^{2}\right)\right). This will be the cornerstone of our analysis in this section. In particular, by the transfer theorem (see, e.g., [ 14 , Theorem VI.1] ), it holds that [y^{n}]\Phi(y,u)\underset{n\to\infty}{\sim}\gamma(u)\rho_{B}^{-n}n^{-5/2},\qquad\text{where}\quad\gamma(u):=\frac{3\rho_{B}^{3/2}c_{B}}{4\sqrt{\pi}}u\exp\left(uB^{\prime}(\rho_{B})\right). (9) 5.1 Enumerative results The proof of [ 28 , Theorem 3.2 and Proposition 3.5] together with the discussion above imply the following result, which is a more precise version of \cref thm:enum. Theorem 12 . The series C^{\bullet}(x,u) displays the following asymptotic behaviours when x is in a \Delta -domain neighbourhood of \rho(u) , where we set X:=1-\frac{x}{\rho(u)} . Subcritical regime. If uu_{C} , then C^{\bullet}(x,u)=y(u)-s(u)X^{1/2}+\Theta\left(X\right), where s(u):=\sqrt{\frac{2}{uB^{\prime\prime}(y(u))+u^{2}B^{\prime}(y(u))^{2}}}=\sqrt{\frac{2y(u)}{1+y(u)\ln\left(\frac{y(u)}{\rho(u)}\right)^{2}}}. Thus, [x^{n}]C^{\bullet}(x,u)\sim\frac{s(u)}{2\sqrt{\pi}}n^{-3/2}\rho(u)^{-n}. 5.2 Degree distribution in the block tree To study the block sizes of \mathbf{G}_{n,u} sampled according to \mathbb{P}_{n,u} , we start by determining the degrees in \mathbf{T}_{n,u} . In the remainder of the paper, we write {\mathbf{d}}_{n,u}^{(1)},{\mathbf{d}}_{n,u}^{(2)},\dots for the degrees of \mathbf{T}_{n,u} in decreasing order, and let \mathbf{v}_{n,u}^{(j)} be the vertex of degree {\mathbf{d}}_{n,u}^{(j)} (in case of equality, choose any deterministic ordering). The following is a consequence of \cref eq:def-mu,eq:transfer-Phi-y-u. Proposition 13 . Let c(u):=\frac{\gamma(u)}{\Phi(y(u))}=\frac{3\rho_{B}^{3/2}c_{B}}{4\sqrt{\pi}}u\exp\left(u\left(B^{\prime}(\rho_{B})-B^{\prime}(y(u))\right)\right). If u\leq u_{C} , then y(u)=\rho_{B} , so as k\to\infty , {\mu}^{u}(k)\sim c(u)k^{-5/2}. If u\geq u_{C} , then as k\to\infty , {\mu}^{u}(k)\sim c(u)k^{-5/2}\left(\frac{y(u)}{\rho_{B}}\right)^{k}. In particular, if u>u_{C} , then {\mu}^{u} has a finite variance. Using \cref thm:phasetransition_block_weighted,prop:equiv-muu and results of Janson [ 21 , Theorem 19.16, Example 19.27, Remark 19.28, Theorem 19.34] on the degree distribution of Bienaymé trees, we obtain the following results on the degree distribution of a block tree. (In the subcritical case, results from [ 20 ] are also used.) A similar method was used for the block tree of planar maps [ 15 ] . Proposition 14 . 1. If u0 , \nu(dx)=c(u_{C})x^{-5/2}\frac{g(-x)}{g(0)}dx, and, for all j\geq 1 , almost surely E_{(j)}>0 . 3. If u>u_{C} , then for all fixed j\in\mathbb{N}_{0} , it holds as n\rightarrow\infty that {\mathbf{d}}_{n,u}^{(j)}=\frac{\ln(n)}{\ln\left(\frac{\rho_{B}}{y(u)}\right)}-\frac{5}{2}\frac{\ln(\ln(n))}{\ln\left(\frac{\rho_{B}}{y(u)}\right)}+O_{\mathbb{P}}(1). (12) Remark 15 . The distribution of L_{1} is known in the map literature as the Airy distribution of the map type . 5.3 Block sizes In this subsection, we study the distribution of block sizes of random block-weighted planar graphs. Unfortunately, the degrees of the associated block tree do not correspond immediately to sizes of blocks, but to sizes of sets of blocks in the decorations. In the following, we deduce block sizes using our results on the degree distribution of block tree (see \cref prop:degrees-Tnu) together with results on Gibbs partitions. This approach was previously used for block-weighted simple triangulations in [ 28 , §4.2] . We want to understand the behaviour of an element of the class \Phi with a fixed size. We use the fact that the function \Phi_{u}:=\Phi(\cdot,u) can be written as \Phi_{u}(y)=V(W(y)), for V(\cdot):=\exp(\cdot) and W(\cdot):=uB^{\prime}(\cdot) . The Gibbs partition framework allows one to study the size of the elements of the class \mathcal{W} (whose EGF is given by W(\cdot) ) in a random element \varphi drawn from a Boltzmann law on \Phi_{u} . In particular, [ 31 , Theorem 3.11] allows us to prove the following proposition. Proposition 16 . Let \mathbf{m}_{n,u}^{(j)} denote the size of a largest element in the set decorating \mathbf{v}_{n,u}^{(j)} in \mathbf{T}_{n,u} . Let R be a random variable with probability generating function P_{R}(z):=\mathbb{E}\left[z^{R}\right]=\frac{\exp(uB^{\prime}(\rho_{B}z))}{\exp(uB^{\prime}(\rho_{B}))}. Then for any j\in\mathbb{N}_{0} , it holds that {\mathbf{d}}_{n,u}^{(j)}-\mathbf{m}_{n,u}^{(j)}\xrightarrow[n\to\infty]{(d)}R, so, in particular, {\mathbf{d}}_{n,u}^{(j)}-\mathbf{m}_{n,u}^{(j)}=O_{\mathbb{P}}(1)\qquad\text{as}\quad n\to\infty. Proof. The collection of block sizes in a random decoration of a vertex of outdegree k in \mathbf{T}_{n,u} can be interpreted as a Gibbs partition. As described in [ 31 , Theorem 3.11] , under certain conditions a Gibbs partition of size k has a unique giant component whose size \mathbf{m}_{k} satisfies k-\mathbf{m}_{k}\xrightarrow[k\to\infty]{(d)}S\coloneqq\sum_{i=1}^{\hat{N}-1}X_{i}. (13) Here, the X_{i} ’s are independent copies of a random variable X whose probability generating function is P_{X}(z)\coloneqq\mathbb{E}[z^{X}]=\frac{W(\rho_{W}z)}{W(\rho_{W})}, and \hat{N} is a random variable whose probability generation function is P_{\hat{N}}(z)\coloneqq\mathbb{E}[z^{\hat{N}}]=\frac{V^{\prime}(W(\rho_{W})z)z}{V^{\prime}(W(\rho_{W}))}. One can check that the probability generating function of the random variable S is P_{S}(z)\coloneqq\mathbb{E}[z^{S}]=\frac{P_{\hat{N}}(P_{X}(z))}{P_{X}(z)}=\frac{\exp(uB^{\prime}(\rho_{B}z))}{\exp(uB^{\prime}(\rho_{B}))}, so S and R have the same distribution. \Cref prop:gibbs-partition is a then consequence of: • Stufler [ 31 , Theorem 3.11] ; • For all j\in\mathbb{N}_{>0} , {\mathbf{d}}_{n,u}^{(j)} converges in probability to +\infty ; • The fact that one can sample \mathbf{G}_{n,u} according to \mathbb{P}_{n,u} by first sampling \mathbf{T}_{n,u} , then its decorations (see \cref prop:law-TG). Finally, we show that [ 31 , Theorem 3.11] does indeed apply to our setting. Specifically, we show that condition (iv) of the theorem holds. In our case, the radii of convergence of V and W are respectively \rho_{V}=\infty and \rho_{W}=\rho_{B} , and it holds that 00 . The block-weighted graph \mathbf{G}_{n,u} exhibits the following behaviours when n\to\infty . Subcritical case. If uu_{C} , then \cref eq:grandbloc holds for the block sizes (fixing j\in\mathbb{N}_{0} ): \mathrm{LB}^{(j)}\left(\mathbf{G}_{n,u}\right)=\frac{\ln(n)}{\ln\left(\frac{\rho_{B}}{y(u)}\right)}-\frac{5}{2}\frac{\ln(\ln(n))}{\ln\left(\frac{\rho_{B}}{y(u)}\right)}+O_{\mathbb{P}}(1). Proof. Let i\in\mathbb{N}_{>0} . The quantity \mathbf{m}_{n,u}^{(i)} from \cref prop:gibbs-partition represents the size of a block. By \cref prop:gibbs-partition,prop:degrees-Tnu, we already know the asymptotic behaviour of \mathbf{m}_{n,u}^{(i)} (and it corresponds to the statement). It therefore remains to show that this asymptotic behaviour coincides with that of the size of the i -th largest block. In the supercritical case, this follows immediately because all block sizes that we identified have the same asymptotic behaviour. In the remaining cases, observe that the limits of the rescaled quantities \mathbf{m}_{n,u}^{(i)} are strictly decreasing in i . Consequently, for every fixed j and for all sufficiently large n , the ordering of the first j blocks coincides with that of the sequence (\mathbf{m}_{n,u}^{(i)}) with high probability. ∎ 6 Conclusion This paper studied the typical structure of block-weighted random graphs from block-stable classes using tools from analytic combinatorics. We developed a notion of a decorated block tree, and depending on the block weight u>0 , we found phase transitions in the law of the block tree ( \cref thm:phasetransition_block_weighted) and, when the series B^{\prime} is singular with exponent 3/2 , in the behaviour of [x^{n}]C^{\bullet}(x,u) ( \cref th:dvp-sing-Cbxu) and in the typical sizes of the blocks themselves ( \cref thm:phasetransition_block_sizes). For future work, we aim to more closely investigate block-stable graph classes beyond those that behave like planar graphs, including perhaps higher genus graph classes (see [ 6 , 8 ] ) and minor-closed classes (see [ 7 ] ). In particular, we aim to find dichotomy behaviours similar to those observed by Panagiotou, Steger [ 25 ] and Giménez, Noy, Rué [ 17 ] . In addition, we look to find scaling limits of our block-weighted graph classes. Finally, a more challenging future direction would be to investigate block-weighted graph classes in unlabelled graph settings (see [ 12 ] ).