Pendant appearances and components in random graphs from structured classes (Q6568862)

A class \(\mathcal{A}\) of graphs is a set of graphs closed under isomorphism. \(\mathcal{A}_{n}\) denotes the graphs in \(\mathcal{A}\) on vertex set \([n]=\{1,2,\ldots, n\}\) and \(R_{n}\) is a graph in \(\mathcal{A}_{n}\) sampled uniformly at random. We have a pendant appearance of a connected graph \(H\) in a larger graph \(G\) if, essentially, deleting a bridge from \(G\) leaves a component isomorphic to \(H\), though we also have to allow for a root which has to be mapped to the root in the copy of \(H\), which we denote \(H^\ast\). We let \(\mathrm{Pend}(R_{n},H^\ast)\) denote the set of pendant appearances of \(H^\ast\) in a random graph \(R_{n}\) and \(\mathrm{pend}(R_{n},H^\ast)\) be its size.\N\NFor a class of graphs \(\mathcal{A}\), if \(\lim_{n\rightarrow\infty}(\vert \mathcal{A}_{n}\vert/n!)^{1/n}\) exists and is in \((0,\infty)\), we say the limit is the growth constant \(\gamma_{\mathcal{A}}\). We then have the relationship \(\gamma_{\mathcal{A}}=1/\rho_{\mathcal{A}}\) where \(\rho_{\mathcal{A}}\) is the radius of convergence of the exponential generating function of the sequence \((\vert \mathcal{A}_{n}\vert)\). To state the results, we also need the notions of attachability and detachability. A graph \(H^\ast\) is attachable to a class \(\mathcal{A}\) if for every graph \(G\) it is true that if there is a pendant appearance of \(H^\ast\) in \(G\) on a vertex set \(W\) and the graph induced on \(V(G)\backslash W\) is in \(\mathcal{A}\), then \(G\in \mathcal{A}\) too. Similarly, a graph \(H^\ast\) is detachable from \(\mathcal{A}\) if for every graph \(G\in \mathcal{A}\), if there is a pendant appearance of \(H^\ast\) on vertex set \(W\) then the graph induced on \(V(G)\backslash W\) is also in \(\mathcal{A}\).\N\NA version of the original pendant appearances theorem was proved by the author [Lond. Math. Soc. Stud. Texts 84, 102--120 (2016; Zbl 1371.05270)]. We consider a class \(\mathcal{A}\) of graphs with \(0<\rho_{\mathcal{A}}<\infty\) (a weaker assumption than existence of a growth constant) and a graph \(H^\ast\) which is attachable to \(\mathcal{A}\), and now, for \(\beta>0\), we consider the class of graphs \(\mathcal{B}=\{G\in \mathcal{A}:\mathrm{pend}(G,H^\ast)\leq \beta \vert V(G)\vert \}\). The result is now that \(\rho_{B}>\rho_{A}\) for some \(\beta>0\). This implies earlier versions he proved in joint work with A. Steger and D. J. A. Welsh [the author et al., J. Comb. Theory, Ser. B 93, No. 2, 187--205 (2005; Zbl 1056.05128)] to the effect that given a class \(\mathcal{A}\) with a growth constant, there is \(\beta>0\) such that the probability that \(R_{n}\) has fewer than \(\beta n\) pendant copies of \(H^\ast\) is exponentially small in \(n\) -- very loosely speaking, some kind of large deviation estimate for the number of pendant appearances.\N\NThe main result in the paper under review is a generalisation of the author's theorem with weaker assumptions and more powerful conclusions. In essence, given a graph \(H^\ast\), it specifies the optimal value \(\alpha\) of the above parameter \(\beta\). It then says that if \(H^\ast\) is weakly attachable to \(\mathcal{A}\) (definition to follow) then few graphs in \(\mathcal{A}_{n}\) have many less than \(\alpha n\) pendant appearances of \(H^\ast\), but if \(H^\ast\) is weakly detachable (definition to follow) from \(\mathcal{A}\) then few graphs in \(\mathcal{A}_{n}\) have many more than \(\alpha n\) pendant appearances of \(H^\ast\). Here, for a graph class \(\mathcal{A}\) with \(0<\rho_{\mathcal{A}}<\infty\) we say \(H^\ast\) is weakly attachable to \(\mathcal{A}\) if there is \(\delta>0\) and a set \(\mathcal{B}\supseteq \mathcal{A}\) of graphs with \(\rho_{\mathcal{B}}=\rho_{\mathcal{A}}\) such that, for all large enough \(n\) and all graphs \(G\in \mathcal{A}_{n}\), if \(G^{\prime}\) is formed from \(G\) by simultaneously attaching at most \(\delta n\) pendant copies of \(H^\ast\) then \(G^{\prime}\in \mathcal{B}\). Similarly \(H^\ast\) is weakly detachable if there is \(\delta>0\) and a set \(\mathcal{B}\supseteq \mathcal{A}\) with \(\rho_{\mathcal{B}}=\rho_{\mathcal{A}}\) such that, for all large enough \(n\) and all graphs \(G\in \mathcal{A}_{n}\), if \(G^{\prime}\) is formed from \(G\) by simultaneously detaching at most \(\delta n\) pendant copies of \(H^\ast\) then \(G^{\prime}\in \mathcal{B}\). If a graph \(H^\ast\) is attachable (respectively detachable) for a class \(\mathcal{A}\) then it is weakly attachable (respectively weakly detachable), just take \(\mathcal{B}=\mathcal{A}\). However, examples are given to show that being attachable is strictly stronger than being weakly attachable and that being detachable is strictly stronger than being weakly detachable. There are also versions for unrooted graphs.\N\NThe results have implications for the structure of the fragment of \(R_{n}\), i.e. the part of the graph not in the giant component. They say, roughly, that under fairly wide conditions (not involving ``smoothness'') on the bridge-addable class \(\mathcal{A}\), the asymptotic joint distribution of certain components in the fragment is Boltzmann Poisson. This may allow us to obtain the limiting probability of \(R_{n}\) being connected under some further assumptions. The author notes that much remains unknown about unlabelled graphs.