%updated 30-05-2013 %submitted to E-JC 2012-10-09? ack 2012-10-10 %rwg-2012-10-09 home sent to arXiv 2012-10-09 submit/0568730 %for hard-core model see \m{more refs Molloy-Reed, Durrett, Montanari,..?} %see rwg-2012-09-01 for $\lambda_0, \lambda_1$ throughout. %See lem.wellb. Some day, add case .. at most k disjoint cycles of length at least l - need to show there is a gc %suppressed Lemma {lem.growth-subclass} 30-05-2013 \title{\bf Random graphs from a weighted\\ minor-closed class} \date{30 May 2013} \documentclass[11pt]{article} \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb} % \usepackage{amsmath} % \usepackage{amssymb} \usepackage{latexsym} \usepackage{graphicx} %\usepackage{showkeys} %\usepackage[notref,notcite]{showkeys} %\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} %\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % \newenvironment{proof}{\noindent{\bf Proof} \hspace{.1in}}{\hspace*{\fill}$\Box$} \newenvironment{proofof}[1]{% \noindent {\bf Proof of #1}}% {\hspace*{\fill}$\Box$} \def\noproof{\hspace*{\fill}$\Box$} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma} [theorem] {Lemma}%[section] \newtheorem{corollary} [theorem] {Corollary}%[section] \newtheorem{prop} [theorem] {Proposition}%[section] \newtheorem{definition} [theorem] {Definition}%[section] \newtheorem{remark} [theorem] {Remark}%[section] \newtheorem{conjecture} [theorem] {Conjecture}%[section] \def\Prob#1{\mbox{{\rm Prob}}\,[#1]} \def\Exp{{\mathbb E}\,} \def\Pr{\mbox{{\rm Pr}}\,} \let\eps=\epsilon \def\enddiscard{} \long\def\discard#1\enddiscard{} \newcommand{\?}{?\marginpar[\hfill ?]{?}} \newcommand{\vn}{\mbox{\rm v}} %number of vertices - not used \newcommand{\en}{\mbox{\rm e}} %number of edges - not used \def\Po{\mbox{\rm Po}} \newcommand{\bc}{{\rm BC}} \newcommand{\CP}{\rm CP} %\newcommand{\eps}{\varepsilon} \newcommand{\E}{{\mathbb E}} \newcommand{\pr}{{\mathbb P}} \newcommand{\giant}{{\rm giant}} \newcommand{\Bigc}{{\rm Big}} \newcommand{\bigc}{{\rm big}} %\newcommand{\Miss}{\rm Miss} %\newcommand{\miss}{\rm miss} \newcommand{\eg}{{\rm eg}} \newcommand{\inu}{\in_{u}} \newcommand{\inl}{\in_{\lambda}} \newcommand{\whp}{whp } \newcommand{\m}[1]{\marginpar{\tiny{#1}}} \newcommand{\gc}{\gamma_{\ell}} \newcommand{\gu}{\gamma_{u}} \newcommand{\gs}{{\mathcal G}^{S}} \newcommand{\as}{{\mathcal A}^{S}} \newcommand{\bs}{{\mathcal B}^{S}} \newcommand{\cs}{{\mathcal C}^{S}} \newcommand{\mgs}{|{\mathcal G}^{S}_n|} \newcommand{\cp}{{\mathcal P}} \newcommand{\ca}{{\mathcal A}} \newcommand{\cb}{{\mathcal B}} \newcommand{\cc}{{\mathcal C}} \newcommand{\cd}{{\mathcal D}} \newcommand{\ce}{{\mathcal E}} \newcommand{\cf}{{\mathcal F}} \newcommand{\cg}{{\mathcal G}} \newcommand{\ct}{{\mathcal T}} \newcommand{\cu}{{\mathcal U}} \newcommand{\cv}{{\mathcal V}} \newcommand{\rU}{\rm U} \newcommand{\cat}{({\mathcal A}, \tau)} \newcommand{\ugs}{{\mathcal U}{\mathcal G}^{S}} \newcommand{\umgs}{|{\mathcal U}{\mathcal G}^{S}_n|} \newcommand{\up}{{\mathcal U}{\mathcal P}} \newcommand{\rhoP}{\rho_{\cal P}} \newcommand{\UP}{U_{\cal P}} \newcommand{\add}{\mbox{add}} \newcommand{\aut}{\mbox{\small aut}} \newcommand{\nono}{\Nats} \newcommand{\core}{2{\rm -core}} \newcommand{\ex}{{\rm Ex}} \newcommand{\Frag}{{\rm Frag}} \newcommand{\frag}{{\rm frag}} \newcommand{\Bridge}{{\rm Bridge}} \newcommand{\bridge}{{\rm bridge}} \newcommand{\Cross}{{\rm Cross}} \newcommand{\cross}{{\rm cross}} \newcommand{\apex}{{\rm Apex}} %\newcommand{\favl}{favl-dichotomous} \newcommand{\favl}{freely-addable-or-limited} \newcommand{\Favl}{Freely-addable-or-limited} \date{\dateline{October 11, 2012}{April 24, 2013}\\ \small Mathematics Subject Classifications: 05C80, 05C30} \begin{document} \author{Colin McDiarmid \\ \small Department of Statistics \\ \small Oxford University, UK\\ \small \tt cmcd@stats.ox.ac.uk} \maketitle \begin{abstract} There has been much recent interest in random graphs sampled uniformly from the $n$-vertex graphs in a suitable minor-closed class, such as the class of all planar graphs. Here we use combinatorial and probabilistic methods to investigate a more general model. We consider random graphs from a `well-behaved' class of graphs: examples of such classes include all minor-closed classes of graphs with 2-connected excluded minors (such as forests, series-parallel graphs and planar graphs), the class of graphs embeddable on any given surface, and the class of graphs with at most $k$ vertex-disjoint cycles. Also, we give weights to edges and components to specify %which yield probabilities, so that our random graphs correspond to the random cluster model, appropriately conditioned. %The introduction of weights can throw extra light on the role of bridges. We find that earlier results extend naturally in both directions, to general well-behaved classes of graphs, and to the weighted framework, for example results concerning the probability of a random graph being connected; and we also give results on the 2-core which are new even for the uniform (unweighted) case. \bigskip\noindent \textbf{Keywords:} random graph; minor-closed class; random cluster model; connectivity; core \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\newpage %\tableofcontents \section{Introduction} \label{sec.intro} Given a class $\ca$ of graphs (always assumed to be closed under isomorphism), let $\ca_n$ denote the set of graphs in $\ca$ on the vertex set $[n]:= \{1,\ldots,n\}$. %\m{deleted $[n]$} There has been much recent interest in properties of the random graph $R_n$ sampled uniformly from $\ca_n$, when $\ca$ is a suitable `structured' class of graphs such as the class of all planar graphs. %\m{give more refs?} %see for example~\cite{msw05}. Analytic methods, based on generating functions and singularity analysis, have over recent years been extended dramatically to handle more and more complicated classes of graphs: the work on planar graphs by Gim\'enez and Noy~\cite{gn09a} (see also~\cite{bgw02,gn09b}) was a breakthrough, and very recently graphs embeddable on any given surface have been handled~\cite{bg09,cfgmn11}. See also~\cite{ggnw07} for graphs with no minor isomorphic to the complete bipartite graph $K_{3,3}$. %In both cases the Analytic work in papers such as those just mentioned much extends earlier combinatorial and probabilistic investigations, as for example in~\cite{gm04,gmsw05,gmsw07,cmcd08,cmcd09,cb08,msw05,msw06}. For further recent related work (appearing in 2010 or later) see for example \cite{bnw09,bfkv11,cfgn10,dowden10,dowden11,dgn2011,dgn10,dgn11a,dgn11b,dgnps12,fp11,kl10,kmcd11,km08b,km11,cmcd11,ps10,ps11}. %\m{check 2010, more refs?} There is natural interest also in the case when $\ca$ is {\em any} minor-closed class of graphs, or for example any such class with 2-connected excluded minors; and for such investigations we still need combinatorial and probabilistic methods. Here we use such methods, building in particular on~\cite{cmcd09}, and consider a more general model: we investigate random graphs from a suitable weighted class of graphs, where `suitable' includes all the usual suspects and more, and `weighted' is described below, corresponding to the random clusster model. %is defined quite generally. %We are particularly interested in minor-closed graph classes which are `addable', %that is, which have 2-connected excluded minors, %or have some similar property such as being embeddable on a given surface. %Given a class $\ca$ of graphs (closed under isomorphism) we let $\ca_n$ %denote the set of graphs in $\ca$ on the vertex set $[n]=\{1,\ldots,n\}$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{The model} \label{subsec.model} To introduce the model, recall that in the classical binomial random graph $G_{n,p}$ on the vertex set $[n]$, the %${n \choose 2}$ $\binom{n}{2}$ possible edges are included independently with probability $p$, where $00$; %(we use $\nu$ rather than $q$), and the random graph $R_n$ takes as values the graphs $H$ on $[n]$, with %on $\{1,\ldots,n\}$, with \[ \pr(R_n=H) \propto p^{e(H)}(1-p)^{\binom{n}{2}-e(H)} \nu^{\kappa(H)}. \] Here $\kappa(H)$ denotes the number of components of $H$. %Assuming as before that $\ca_n$ is non-empty, For each $H \in \ca_n$ we have \[ \pr(R_n=H \, | \, R_n \in \ca ) %= \frac{p^{e(H)}(1-p)^{{n \choose 2}-e(H)} q^{\kappa(H)} } %{\sum_{G \in \ca_n}p^{e(G)}(1-p)^{{n \choose 2}-e(G)} q^{\kappa(G)}} = \frac{\lambda^{e(H)}\nu^{\kappa(H)}} {\sum_{G \in \ca_n}\lambda^{e(G)} \nu^{\kappa(G)}}. \] %where $\lambda=p/(1-p)$. %This is the model in which we are most interested, but %sometimes it may be helpful to generalise one step further (see also Section~\ref{sec.concl}. %Bridges play a special role in this work. % A {\em bridge} in a graph $G$ is an edge $e$ such that $G-e$ has one more component than $G$. % For a graph $G$ we let $e_0(G)$ be the number of bridges in $G$ (the 0 is since a bridge is in 0 cycles) % and let $e_1(G)=e(G)-e_0(G)$. % We replace %$\lambda>0$ by $\lambda_0>0$ and $\lambda_1>0$; and replace % $\lambda^{e(G)}$ by $\lambda_0^{e_0(G)} \lambda_1^{e_1(G)}$. % and we use $\nu$ rather than $q$. % We call $\lambda_0$ and $\lambda_1$ the {\em edge-parameters} and $\nu$ the {\em component-parameter}. This is the distribution on which we shall focus. Thus the distribution of our random graphs in $\ca$ is as follows. Given {\em edge-parameter} $\lambda>0$ and {\em component-parameter} $\nu>0$, we let the \emph{weighting} $\tau$ be the pair $(\lambda,\nu)$. For each graph~$G$ we let %$\lambda^{e(G)}$ denote $\lambda_0^{e_0(G)} \lambda_1^{e_1(G)}$, $\tau(G) = \lambda^{e(G)} \nu^{\kappa(G)}$; %\m{Let $\tau(G)= \lambda^{e(G)} \nu^{\kappa(G)}$?} and for each finite set $\cb$ of graphs we denote $\sum_{G \in \cb} \tau(G)$ by $\tau(\cb)$. We write $R \in_{\tau} \cb$ to indicate that $R$ is a random graph which takes values in $\cb$ with %$\pr(R_n=H) \propto \lambda^{e(H)}$ for each $H \in \ca_n$, that is %$\pr(R=H) = \tau(H)/\tau(\cb)$; \[ \pr(R=H) = \frac{\tau(H)}{\tau(\cb)} \] and we call $R$ a $\tau$-\emph{weighted random graph from} $\cb$. Given a fixed {\em weighted graph class} $(\ca, \tau)$, we write $R_n \in_{\tau} \ca$ to indicate that $R_n$ has the distribution of $R \in_{\tau} \ca_n$ (when $\ca_n$ is non-empty). %(and we say that $R_n$ is $\tau$-\emph{random from} $\ca$). Our aim is to investigate the behaviour of the $\tau$-weighted random graph $R_n$ for a suitable weighted graph class $\cat$, with a fixed $\tau$, for large $n$. %The most interesting case is when $\lambda_0=\lambda_1$ but we learn more by allowing the %edge-parameters to differ. When $\lambda=\nu=1$ of course we are back to random graphs sampled uniformly. %we write $\tau={\bf 1}$ in this case. Let us write $R_n \in_u \ca$ %instead of $R_n \in_{\bf 1} \ca$, to indicate that $R_n$ is uniformly distributed over $\ca_n$, as introduced in~\cite{msw06} (and perhaps earlier). %\m{physics models, Boltzmann, $\mu n$ edges,..} Analytic methods for graph problems often involve generating functions with a variable $x$ for vertices and a variable $y$ for edges (and sometimes a variable $z$ for components), as for example in~\cite{gn09a}; and we may think of $y$ as giving a weight for edges. Also for example, for a fixed $1<\mu<3$, we may learn about the random planar graph with $n$ vertices and with $\sim \mu n$ edges %is investigated in~\cite{}. \m{also gn, gerke,mcd,steger,weissel} %We can learn about such graphs by choosing a suitable value for the edge-weight, see~\cite{gn09a}. %setting $\lambda_0=\lambda_1=\lambda$ and $\nu=1$, and considering %$R_n \in_{\tau} \ca$ for a suitable value of $\lambda$, see for example~\cite{gn09a}. Further, models in physics involving lattices or more general graphs may attach weights to vertices or edges; for example the hard-core model, which is a model for a gas with particles of non-negligible size, and which also appears in models for communications networks, see for example~\cite{bs94}. % \m{more refs Molloy-Reed, Durrett, Montanari,..?} We find that many results extend naturally from the uniform case $\tau=(1,1)$ to general $\tau$-weighted random graphs. As well as generalising previous work on the uniform case in this way, we give new results on the 2-core of $R_n$, arising from a more combinatorial proof of a key `smoothness' result, see~\cite{bcr08,cmcd09}. The 2-\!{\em core} of a graph $G$ (sometimes called just the \emph{core}), denoted here by $\core(G)$, is the unique maximal subgraph with minimum degree is at least $2$. Thus $\core(G)$ is empty if and only if $G$ is a forest; and the 2-core may be obtained by repeatedly trimming off leaves. To investigate the %$\tau$-weighted random graph $R_n \in_{\tau} \ca$ we need to consider how $\tau(\ca_n)$ grows with $n$. %Let us also write $\tau_n(\ca)$ for $\tau(\ca_n)$. \m{$\tau_n(\ca)$ wanted?} As in the uniform case, we say that the weighted graph class $\cat$ has {\em growth constant} %\m{$0< \gamma$?} $\gamma = \gamma(\ca,\tau)$ if $0 \leq \gamma<\infty$ and $\tau(\ca_n) = (\gamma +o(1))^n n!$ as $n \to \infty$. (Sometimes we insist that $\gamma>0$.) Also we say that $\cat$ is {\em smooth} (or {\em smoothly growing}) if $\tau(\ca_{n})/n \tau(\ca_{n-1})$ tends to a limit $\gamma'$ with $0<\gamma'<\infty$ as $n \to \infty$. (This is also referred to as the `ratio test' property RT1, see for example~\cite{bb03,{burris2001}}.) %\m{Burris, Bell ok?} It is easy to see that in this case the limit $\gamma'$ must be the growth constant $\gamma$. %For example, it is well known that the class $\cf$ of forests is smooth with growth constant $e$; %and we shall see that, for any $\tau$, %$=(\lambda,\nu)>0$, %the weighted class $\cf,\tau$ is smooth with growth constant $e\lambda_0$. We need some definitions concerning a graph class $\ca$. We say that $\ca$ is {\em proper} when it is not the class of all graphs %\m{non-trivial - later?} and it contains a graph with at least one edge; %\m{contains all components - put back `all' move this defn later?} %that $\ca$ {\em contains all components} if each component of each graph in $\ca$ is also in $\ca$; that $\ca$ is {\em decomposable} when a graph is in $\ca$ if and only if each component is; that $\ca$ is {\em bridge-addable} when, for each graph in $\ca$ and each pair $u$ and $v$ of vertices in different components, the graph obtained by adding an edge joining $u$ and $v$ must also be in $\ca$; and $\ca$ is {\em addable} when it is both decomposable and bridge-addable. Also, we say that $\ca$ is {\em minor-closed} if whenever $G \in \ca$ and $H$ is a minor of $G$ then $H \in\ca$. %\m{notation in Diestel?} %\m{(denoted by $H \preceq_m G$)} Let $\ca$ be a proper minor-closed class of graphs. The minor-minimal graphs not in $\ca$ are the \emph{excluded minors}. From the Robertson and Seymour theory of graph minors~\cite{rs04}, see for example Diestel~\cite{diestel05}, the set of excluded minors must be finite. The properties of being decomposable and being addable correspond to simple properties of the excluded minors: indeed, $\ca$ is decomposable if and only if each excluded minor is connected, and $\ca$ is addable if and only if each excluded minor is 2-connected. % and $\ca$ is bridge-addable if and only if for each excluded minor $H$ satisfies %(a) $H$ has no bridges, and (b) some minor of the `exploded graph' $H'$ %is also an excluded minor, %where $H'$ is the disjoint union of the blocks of $H$. (We shall prove this later.) It was conjectured in~\cite{bnw09} that, in the uniform case, every proper minor-closed class of graphs has a growth constant. % $\geq 0$. It is natural to conjecture that this in fact holds for each weighting $\tau$. %or at least in the case $\lambda_0=\lambda_1$. Indeed it is natural to conjecture that we even have smoothness, whenever the growth constant is $>0$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Overview of main results} \label{subsec.overview} Our results involve a `well-behaved' weighted class of graphs. We shall say later precisely what this means, %for a weighted class $\ca, \tau$ of graphs to be{\em well-behaved}, after we have introduced various preliminary definitions. We require that such a class is proper, minor-closed and bridge-addable, and satisfies certain further conditions: the full definition is given in section~\ref{subsec.wellbdef} below. The important thing to note here is that the following classes of graphs are all well-behaved, with any weighting $\tau$: any proper, minor-closed, addable class (for example the class of forests, or series-parallel graphs or planar graphs); the class $\gs$ of graphs embeddable on any given surface $S$; and the class of all graphs which contain at most $k$ vertex-disjoint cycles, for some fixed $k$. %\m{need to prove there is a gc with $\lambda$} We shall prove various results about any well-behaved weighted class of graphs $\cat$ %with weights $\tau=(\lambda,\nu)$ %(where $\lambda =(\lambda_0,\lambda_1)$), and about the corresponding %a $\tau$-weighted random graph $R_n \in_{\tau} \ca$, %(Recall that $\tau=(\lambda,\nu)$.) where $\lambda>0$, $\nu>0$ and $\tau=(\lambda,\nu)$. % where %$\lambda_0>0$, $\lambda_1>0$, $\nu>0$ and $\tau=(\lambda_0,\lambda_1,\nu)$. We sketch some of these results now, in the order in which the proofs run: full details appear in Section~\ref{sec.results}. First we show the key counting result that $\cat$ is smooth, with some growth constant $\gamma >0$ %which is independent of $\nu$. % (depending on $\ca$ and $\lambda$ but not on $\nu$). In the process of doing this we learn about the 2-core of $R_n$: %$\core(R_n)$: in particular we find that, as $n \to \infty$ \begin{equation} \label{eqn.2core} %v(\core(R_n))/ n \to (1- \lambda/\beta) \mbox{ in probability} v(\core(R_n))/ n \to (1- t) \mbox{ in probability} \end{equation} %\m{$\lambda_0$?} where $t$ is the unique root with $00$) then from~\cite{gn09a,cmcd08} we have $\gamma \approx 27.22687$, and so %$\beta \approx 26.2076$, \m{26.20755} and $1-1/\beta \approx 0.96184$. \m{0.961843} $v(\core(R_n)) \approx 0.96184 n$ \whp. (We say that a sequence $(A_n)$ of events holds \emph{with high probability} (\whp ) if $\Pr(A_n) \to 1$ as $n \to \infty$.) After that, using smoothness, we learn about the `fragments' of $R_n$ not in the giant component, %the probability of connectedness, and so on. and in particular we find that \begin{equation} \label{eqn.conna} \pr(R_n \mbox{ is connected}) \; \to \; e^{-D(\rho,\tau)}= e^{- \nu D(\rho,\tau_1)} \mbox{ as } n \to \infty \end{equation} where %$\tau_1=(\lambda_0,\lambda_1,1)$ $\tau_1=(\lambda,1)$ and $D(\rho,\tau)$ is as described in the next paragraph. When $\ca$ is the class of forests, the growth constant $\gamma$ is $e \lambda$ and the limiting probability of connectedness is $e^{-\frac{\nu}{2\lambda}}$. When $\ca$ is the class $\gs$ of graphs embeddable on a given surface $S$ and $\lambda=1$ %of planar graphs and $\lambda_0=\lambda_1=1$ then from~\cite{gn09a} Corollary 1 %and~\cite{bg09,cfgmn11}, %we have $e^{-D(\rho,{\bf 1})} \approx 0.96325$, and %\m{read off for general $\lambda$'s?} the limiting probability of connectedness is $e^{-\nu D(\rho,{\bf 1})} \approx 0.96325^{\nu}$ (see Section~\ref{subsec.2core}). We say that a graph $H$ is {\em freely addable} to a graph class $\ca$ if the disjoint union $G \cup H$ of $G$ and $H$ is in $\ca$ for each graph $G \in \ca$. Let $\cd$ denote the class of connected graphs which are freely addable to $\ca$. % Observe that if $\ca$ is decomposable then each graph in $\ca$ is freely addable to $\ca$, so that $\cd$ is the class of connected graphs in $\ca$; and if $\ca=\gs$ then $\cd$ is the class of connected planar graphs. % Now $D(\rho,\tau)$ is the evaluation of the exponential generating function $D(x,\tau)$ for $\cd$ (see Subsection~\ref{subsec.boltzmann}), at the radius of convergence $\rho$ for $\cat$. % \m{was: its radius of convergence $\rho$.} % Now we define $D(x,y_0,y_1,z)$ as the generating function %\[ \sum_{n \geq 1} \sum_{G \in \cd_n} \frac{x^n}{n!} y_0^{e_0(G)} y_1^{e_1(G)} z^{\kappa(G)},\] % and let $\rho= \rho(\tau)$ be the radius of convergence of the power series $D(x,\tau)$ % (that is, $D(x,\lambda_0,\lambda_1,\nu)$) as a function of $x$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Statement of main results} \label{sec.results} %In the first subsection we say precisely what it means for a %graph class to be `well-behaved': the reader might wish to skip this subsection on a first reading. The first subsection describes the Boltzmann Poisson random graph corresponding to a decomposable class. Then we consider a well-behaved weighted class $\cat$ of graphs and $R_n \in_{\tau} \ca$. We describe how the `fragments' not in the giant component of $R_n$ converge in distribution to $R$, for the corresponding Boltzmann Poisson random graph $R$, which gives as a corollary the result~(\ref{eqn.conna}) on the limiting probability of $R_n$ being connected. The next subsection concerns smoothness and the $\core$, and in particular includes the result~(\ref{eqn.2core}); and then we discuss appearances of subgraphs. In the final subsections we say precisely what it means for a graph class to be `well-behaved', and then give a sketch plan of the rest of the paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Boltzmann Poisson random graph} \label{subsec.boltzmann} %\subsection{Exponential formula and growth constants} %\label{subsec.expf} We introduce a general distribution on the unlabelled graphs corresponding to a weighted class of labelled graphs. %we return to minor-closed classes in Section~\ref{} below. %Theorem~\ref{thm.miss} below. Let $\ca$ be a class of graphs, and let $\cc$ be the class of connected graphs in $\ca$. (By convention the empty graph $\emptyset$ is in $\ca$ and not in $\cc$.) %Much as earlier, we write $y$ for $y_0,y_1$ and $y^{e(G)}$ for $y_0^{e_0(G)} y_1^{e_1(G)}$. We define the generating function $A(x,y,z)$ by \[ A(x,y,z) = \sum_{n \geq 0} \sum_{G \in \ca_n} \frac{x^n}{n!} y^{e(G)} z^{\kappa(G)} \] and similarly \[ C(x,y,z) = z \ \sum_{n \geq 1} \sum_{G \in \cc_n} \frac{x^n}{n!} y^{e(G)}. \] The standard `exponential formula' in a general form (see for example~\cite{fs09,stanley99}) is that when $\ca$ is decomposable we have \begin{equation} \label{eqn.exp} A(x,y,z) = e^{C(x,y,z)}. \end{equation} Let us say that $\ca$ {\em contains components} (or is {\em down-decomposable}) if each component of each graph in $\ca$ is also in $\ca$. % (which is much weaker than insisting that $\ca$ be decomposable). Suppose that $\ca$ contains components, and consider any fixed positive $y$ and $z$. Then as in~(\ref{eqn.exp}), $C(x,y,z) \leq A(x,y,z) \leq e^{C(x,y,z)}$ for each $x \geq 0$, and so %for any fixed positive $y$ and $z$ the generating functions $A(x,y,z)$ and $C(x,y,z)$ (as functions of $x$) have the same radius of convergence. Thus in particular the radius of convergence of $A$ does not depend on~$z$. (The radius of convergence clearly depends on~$y$ since $e(G)$ is at least linear for a connected graph $G$.) %\m{deleted: We Also we may see that $\cat$ has growth constant $\gamma$ if and only if $(\cc, \tau)$ does. %\m{recast?} %\m{deleted: (See Section~\ref{subsec.contogen} for further discussion.)} %\m{check in Section~\ref{subsec.contogen}} \smallskip %\subsection{Boltzmann Poisson random graph} %\label{subsec.boltzmann} For any graph class $\ca$, we let $\cu \ca$ denote the corresponding unlabelled graph class, with members the equivalence classes of graphs in $\ca$ under isomorphism. %and we let $A(x,y,z)$ denote the (exponential) generating function of $\ca$. Now let $\ca$ be any decomposable class of (labelled) graphs. %which is closed under isomorphism, %and let $A(x,y,z)$ be its generating function. %\m{deleted: [This will be our general rule, so that a class $\cb$ of graphs %will have generating function $B(x,y,z)$ etc.]} %If $\cc$ denotes the class of connected graphs in $\ca$ then the %`exponential formula' is that $A(x)=e^{C(x)}$. %(By convention the empty graph $\emptyset$ is in $\ca$ and not in $\cc$.) % As we shall observe later, % at the beginning of Section~\ref{sec.proofU}, we may write its generating function $A(x,y,z)$ in terms of $\cu \ca$ %of unlabelled graphs in $\ca$ as \begin{equation} \label{eqn.Agen} A(x,y,z) = \sum_{H \in \cu \ca} \frac{x^{v(H)}y^{e(H)} z^{\kappa(H)}}{\aut(H)}. \end{equation} % Here $\aut(G)$ denotes the number of automorphisms of $G$. Suppose that we are given %$\lambda>0$, $\nu>0$ and $\tau=(\lambda,\nu)$. We shall set $y=\lambda$ %(that is, $y_0=\lambda_0$ and $y_1=\lambda_1$) and $z=\nu$, and write either $A(x,\lambda,\nu)$ or $A(x,\tau)$. If we choose $\rho>0$ such that $A(\rho,\tau)$ is finite, then we may obtain a natural `Boltzmann Poisson distribution' on $\cu \ca$ -- see equation~(\ref{eqn.bp-def}) below. The uniform case $\tau=(1,1)$ was considered in~\cite{cmcd09}. We denote the radius of convergence of $A(x, \tau)$ %$A(x,\lambda,\nu)$ (viewed as a power series in $x$) by $\rho(\ca,\tau)$. We need more notation (following~\cite{cmcd09}) to record some of the properties of this distribution. %Let $\kappa(G)$ denote the number of components of a graph~$G$; For a connected graph $H$ let $\kappa(G,H)$ denote the number of components of $G$ isomorphic to $H$; and for a class $\cal D$ of %unlabelled connected graphs let $\kappa(G,{\cal D})$ denote $\sum_{H \in {\cal U \cal D}} \kappa(G,H)$, the number of components of $G$ isomorphic to some graph in $\cal D$. The notation $X \sim \Po(\mu)$ means that the random variable $X$ has %(precisely) the Poisson distribution with mean $\mu$. Recall that a sum of independent Poisson random variables $\Po(\mu_i)$ has distribution $\Po(\sum_i \mu_i)$, as long as $\sum_i \mu_i < \infty$. % \begin{theorem} \label{thm.U} Consider the weighted graph class $\cat$ where $\ca$ is decomposable. %(which is closed under isomorphism); %let $\lambda>0$, $\nu>0$ and $\tau=(\lambda,\nu)$; Let $\rho >0$ be such that $A(\rho,\tau)$ is finite, and let \begin{equation} \label{eqn.mudef} \mu(H) = \frac{\rho^{v(H)} \lambda^{e(H)} \nu^{\kappa(H)}}{\aut(H)} \; \mbox{ for each } H \in \cu\ca \end{equation} (so that $A(\rho,\tau)= \sum_{H \in \cu\ca} \mu(H)$ by equation~(\ref{eqn.Agen})). Let the `Boltzmann Poisson random graph' $R=R(\ca,\rho,\tau)$ take values in $\cu \ca$, with \begin{equation} \label{eqn.bp-def} \pr[R=H] = \frac{\mu(H)}{A(\rho,\tau)} \;\; \mbox{ for each } H \in \cu \ca. \end{equation} Also, let $\cc$ denote the class of connected graphs in $\ca$. Then the random variables $\kappa(R,H)$ for $H \in {\cal U}{\cal C}$ are independent, with $\kappa(R,H) \sim \Po(\mu(H))$. \end{theorem} % In particular, since $C(\rho,\tau) = \sum_{H \in \cu\cc} \mu(H)$ (by equation~(\ref{eqn.Agen}) applied to $\cc$) we have $\kappa(R) \sim \Po(C(\rho,\tau))$. %Let us record this as a corollary: % %\begin{corollary} \label{cor.thmU} %The random number $\kappa(R)$ of components of $R$ satisfies % $\kappa(R) \sim \Po(C(\rho,\tau))$. %(that is, $\kappa(U)$ has distribution $\Po(C(\rho))$). % parts (b) and (c) deleted 22/11/08 % \begin{equation} \label{eqn.missdef} % \pr[|R|=n] = \frac{1}{A(\rho)} \frac{|\ca_n| \rho^{n}}{n!} % \;\;\mbox{ for each } n \geq 0. % \end{equation} % % (c) Given an unlabelled graph $G$ let $f(G)$ be the random labelled graph % obtained by picking a graph isomorphic to $G$ on vertices $1,\ldots,|G|$ % uniformly at random. %(or equivalently by picking any graph on vertices $1,\ldots,|G|$ isomorphic to $G$ %and permuting its vertices uniformly at random). %Then for each (labelled) graph $G \in \ca_n$ %\[ %\pr[f(F)= G] = \frac{\rho^n}{A(\rho) n!}, %\] %\m{ref to~\cite{abt97} or book} % Then for each $n$, conditional on $|R|=n$ the random graph $f(R)$ is uniformly %distributed on $\ca_n$. % and the probability generating function $G(x)= \E[x^{|U|}]$ equals %$A(\rho x)/A(\rho) = e^{C(\rho x)-C(\rho)} $. %\end{corollary} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Fragments and connectivity} \label{subsec.connresults} The {\em big component} $\Bigc(G)$ of a graph $G$ is the (lexicographically first) component with the most vertices, and $\Frag(G)$ is the {\em fragments} subgraph induced on the vertices not in the big component (thus $\Frag(G)$ may be empty). %[We have changed from the name $\Miss(G)$ used in McDiarmid~\cite{cmcd06}.] Denote the numbers of vertices in $\Bigc(G)$ and $\Frag(G)$ by $\bigc(G)$ and $\frag(G)$ respectively, so $\bigc(G)+\frag(G)= v(G)$. % equals the number of vertices of $G$. % %Observe from the last theorem that %$\pr[\bigc(R) \leq n] = \exp \left( - \sum_{j >n} |\cc_j| \rho^j /j!\right)$. %[It is clear what $\bigc(H)$ means for an unlabelled graph $H$, %though it is less obvious how to define $\Bigc(H)$.] % We consider $R_n \in_{\tau} \ca$, and focus on the limiting distribution of the random graph $\Frag(R_n)$. It is convenient to deal with the random unlabelled graph $F_n$ % = \rU \Frag(R_n)$ corresponding to $\Frag(R_n)$. We use $\to_{TV}$ to denote convergence in total variation (or in distribution). % %The following theorem and corollary, which are proved in Section~\ref{sec.completingproofs} below, %should be compared with the labelled part of Theorem 2 %of Bell, Bender, Cameron and Richmond~\cite{bbcr00}, and see also %Compton~\cite{compton87}. \begin{theorem} \label{thm.Frag} Let the weighted graph class $\cat$ be well-behaved, %let $\cf(\ca)$ be the class of graphs freely addable to $\ca$ %Let $\lambda>0$, $\nu>0$ and $\tau=(\lambda,\nu)$; %let the class $\ca$ of graphs be such that $\ca,\tau$ is well-behaved; and let $\rho = \rho(\ca,\tau)$. Let $\cf_{\ca}$ be the class of graphs freely addable to $\ca$, with exponential generating function $F_{\ca}$. % Then $0<\rho<\infty$ and $F_{\ca}(\rho,\tau)$ %and $A'(\rho)$ are is finite; and for the %$\tau$-weighted random graph $R_n \in_{\tau} \ca$, the random unlabelled graph $F_n$ corresponding to $\Frag(R_n)$ satisfies $F_n \to_{TV} R$, where $R$ is the Boltzmann Poisson random graph for $\cf_{\ca},\rho,\tau$ defined in~(\ref{eqn.bp-def}). Further, $\E[v(R)] = \rho \, D'(\rho,\tau) < \infty$, where $\cd$ is the class of connected graphs in $\cf_{\ca}$. % is finite. \end{theorem} \begin{corollary} \label{cor.comps} (a) For any given distinct graphs $H_1,\ldots,H_k$ in $\cu \cd$ the $k$ random variables $\kappa(F_n,H_i)$ are asymptotically independent with distribution $\Po(\mu(H_i))$. (b) For any class $\tilde{\cd} \subseteq \cd$ %of connected graphs in $\cf(\ca)$ we have $\kappa(F_n,\tilde{\cd}) \to_{TV} \Po(\tilde{D}(\rho,\tau))$, and each moment of $\kappa(F_n,\tilde{\cd})$ tends to that of $\Po(\tilde{D}(\rho,\tau))$. %\m{delete (b)?} (c) As a special case of part (b), $\kappa(F_n) \to_{TV} 1+ \Po(D(\rho,\tau))$, and as $n \to \infty$ we have $\pr[F_n \mbox{ is connected }] \to e^{-D(\rho,\tau)} = F_{\ca}(\rho,\tau)^{-1}$, $\E[\kappa(F_n)] \to 1 + D(\rho,\tau)$, and the variance of $\kappa(F_n)$ tends to $D(\rho,\tau)$. (d) For the random number of vertices $v(F_n)=\frag(R_n)$, we have\\ $v(F_n) \to_{TV} v(R)$; that is, for each non-negative integer $k$ \[ \pr[v(F_n) = k] \to \frac{1}{F_{\ca}(\rho,\tau)} \frac{ \rho^{k}}{k!} \tau((\cf_{\ca})_k) \; \mbox{ as } n \to \infty, \] and similarly $e(F_n) \to_{TV} e(R)$. \end{corollary} % \m{I do not know if $\E[v(F_n)] \to \E[v(R)]$} \noindent In the uniform case $\tau=(1,1)$ of the above result, part (c) on $\kappa(R_n)$ and part (d) on $v(F_n)$ extend for example Theorems 5.2 and 5.3 of~\cite{cfgmn11}. %Note that Theorem~\ref{thm.sumup} below, together with the result from part (c) above that \m{delete?} %$\pr[R_n \mbox{ is connected}]$ tends to a non-zero limit as $n \to \infty$, shows that $\cc,\tau$ is smooth. \medskip \noindent \emph{Trees and forests} %\m{all $\lambda_0$} Let us illustrate the above results for the classes $\ct$ of trees and $\cf$ of forests. Denote $\cf$ by $\ca$ temporarily (just the next three times). % (to avoid referring to $\cf_{\cf}$). The class $\ca$ is minor-closed and addable, and so it is well-behaved; and the class $\cf_{\ca}$ of graphs freely addable to $\ca$ is just $\cf$ again. By Cayley's formula $\tau(\ct_n)= n^{n-2} \lambda^{n-1} \nu$, and by Stirling's formula $(n!)^{1/n} \sim n/e$. Thus $(\tau(\ct_n)/n!)^{1/n} \to e \lambda$ as $n \to \infty$, %Recall that $\ct$ and $\cf$ denote the classes of trees and forests, respectively. so that $(\ct,\tau)$ has growth constant $e \lambda$. By Lemma~\ref{lem.tauconn} below \[ \tau(\cf,\tau) \geq \tau(\ct,\tau) \geq e^{-\nu/\lambda} \tau(\cf,\tau)\] and it follows that $(\cf,\tau)$ also has growth constant $e \lambda$ (see also Section~\ref{subsec.tau-vary} below). %for example since by Lemma~\ref{lem.tauconn} below %\[ \tau(\cf,\tau) \geq \tau(\ct,\tau) \geq e^{-\nu/\lambda_0} \tau(\cf,\tau).\] Thus $\rho=\rho(\cf,\tau)= %\rho(\ct,\tau)= (e \lambda)^{-1}$. % since $\tau(\ct_n)= n^{n-2} \lambda_0^{n-1} \nu$. %Thus $\cf,\tau$ also has growth constant $e \lambda_0$, since $\cf$ contains components %(see the discussion following~(\ref{eqn.exp})). %Further $\tau(\ct_n) \leq \tau(\cf_n) \leq \tau(\ct_n) e^{\nu/\lambda_0}$ by Lemma~\ref{lem.tauconn}. %and so also $\cf,\tau$ has growth constant $e \lambda_0$. Recall that \begin{equation} \label{eqn.treeformulae} \sum_{n \geq 1} \frac{n^{n-2}}{e^n n!} = \frac12 \;\; \mbox{ and } \;\; \sum_{n \geq 1} \frac{n^{n-1}}{e^n n!} = 1. \end{equation} (One way to see these results is to consider the exponential generating functions $U(z)$ for (Cayley) trees and $T(z)$ for rooted trees respectively, where $U(z) = \sum_{n \geq 1} n^{n-2} z^n/n!$ and $T(z) = \sum_{n \geq 1} n^{n-1} z^n/n!$. Since $T(z)=ze^{T(z)}$ we find $T(1/e)=1$, and since $U(z)=T(z)-T^2(z)/2$ we find $U(1/e)=1/2$, see for example Stanley~\cite{stanley99} chapter 5, or Flajolet and Sedgewick~\cite{fs09} section II.5.). Thus the exponential generating function $T$ (for the weighted case) satisfies \[ T(\rho, \tau)= \nu \sum_{n \geq 1} n^{n-2} \lambda^{n-1}(e \lambda)^{-n}/n! = \frac{\nu}{\lambda} \sum_{n \geq 1} \frac{n^{n-2}}{e^n n!} = \frac{\nu}{2 \lambda}. \] and \[ T'(\rho, \tau) = \nu \sum_{n \geq 1} n^{n-1}\lambda^{n-1}(e \lambda)^{-(n-1)}/n! = e \nu \sum_{n \geq 1} \frac{n^{n-2}}{e^n n!} = e \nu. \] Now consider $R_n \in_{\tau} \cf$. It follows from Corollary~\ref{cor.comps} part (c) that, as $n \to \infty$, $\kappa(R_n)$ converges in distribution to $1+\Po(\nu/2\lambda)$, and so in particular \begin{equation} \label{eqn.for1} \pr(R_n \mbox{ is connected }) = \frac{\tau(\ct_n)}{\tau(\cf_n)} \to e^{-\frac{\nu}{2 \lambda}} %\;\;\; \mbox{ as } \; n \to \infty. \end{equation} and so \begin{equation} \label{eqn.for2} \tau(\cf_n) \sim \nu e^{\frac{\nu}{2 \lambda}} \ n^{n-2} \lambda^{n-1} . \end{equation} %In fact these results are already known, see Theorem 2.3 of~\cite{cmcd12}. % Also, by part (d), as $n \to \infty$, $\Frag(R_n)$ converges in distribution to $R$, so $\frag(R_n)$ converges in distribution to $v(R)$, and indeed in this case we may see %\m{we may see .. not done yet?} that also $\E[\frag(R_n)] \to \E[v(R)]$ as $n \to \infty$ (this follows using the formulae above for $\tau(\ct_n)$ and $\tau(\cf_n)$, and arguing as in the proof of Proposition 5.2 of~\cite{cmcd08}), where by Theorem~\ref{thm.Frag} $\E[v(R)] = \rho T'(\rho,\tau) = \frac{\nu}{\lambda}$. %(Indeed, in this case we may show that that also $\E[\frag(R_n)] \to \E[v(R)]$ as $n \to \infty$.) %\m{see Thm 2.3 of \cite{cmcd12}} \medskip Now consider (vertex-) rooted trees, which also have growth constant $e \lambda$. The exponential generating function $T^o$ satisfies \[ T^o((e \lambda)^{-1}, \tau) = \nu \sum_{n \geq 1} n^{n-1} \lambda^{n-1}(e \lambda)^{-n}/n! = \frac{\nu}{\lambda} \sum_{n \geq 1} \frac{n^{n-1}}{e^n n!} = \frac{\nu}{\lambda}, \] where we have used~(\ref{eqn.treeformulae}). This result is used in the introduction to Section~\ref{subsec.conn-smooth}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Smoothness and $\core(R_n)$} \label{subsec.2core} Our next theorem says that a well-behaved weighted graph class $\cat$ is smooth, and gives results on $\core(R_n)$ for the %$\tau$-weighted random graph $R_n \in_{\tau} \ca$. % %for $R_n \in_{\tau} \ca$ the size of the 2-core is concentrated around a certain %value; and the probability of $\core(R_n)$ being connected tends to a certain limit. %There are also related results for the class $\cc$ of connected graphs in $\ca$. Recall that $(\cf,\tau)$ has growth constant $\lambda e$, where $\cf$ is the class of forests. %and then it gives results on the core of a random graph from either $\ca$ or $\cc$. %In particular, the conditions hold for any non-trivial minor-closed addable class of graphs, and for the class of all %graphs embeddable on any fixed surface. \begin{theorem} \label{thm.sumup} %Let $\ca$ be a monotone bridge-addable \m{or minor-closed?} class of graphs, and let $\lambda>0$ etc. Let the weighted graph class $\cat$ be well-behaved, with growth constant $\gamma$; %\m{dropped assumption $\gamma > \lambda_0 e$} %with growth constant $\gamma > \lambda_0 e$; let $\cc$ denote the class of connected graphs in $\ca$; %[delete: let $\cb$ denote the class of graphs in $\cc$ with minimum degree at least 2;] and let $R_n \in_{\tau} \ca$. %Assume that $\ca$ is not just the class $\cf$ of forests. %and the corresponding class $\cc$ of connected graphs in $\ca$. %For $n=1,2,\ldots$ let $R^{\ca}_n \inu \ca_n$ and $R^{\cc}_n \inu \cc_n$. %Suppose that $\ca, \tau$ has a growth constant $\gamma$ and $\gamma > \lambda e$; %that the class $\cb$ of connected graphs in $\ca$ with minimum degree at least 2 %maintains at least factorial growth; and \whp each component of $\Frag(R^{\ca}_n)$ is %in the class $\cd$ of connected graphs which are freely addable to $\ca$. %For $n=1,2,\ldots$ let $R_n \inu \ca$. %\m{do for minor-closed} Then \begin{description} \item{(a)} Both $\cat$ and $(\cc,\tau)$ %the class $\cc$ of connected graphs in $\ca$ are smooth with growth constant $\gamma$, and $\gamma \geq \lambda e$. %where $\gamma$ is the growth constant of $\ca, \tau$ \item{(b)} Let $\cb$ denote the class $\cc^{\delta\geq 2}$ of graphs in $\cc$ with minimum degree at least~2. %\m{could drop conn, see .. ?} If $\gamma > \lambda e$ then %\m{suppress chat on $\cb$?} $(\cb,\tau)$ has growth constant $\beta$ where $\beta$ is the unique root $> \lambda$ to $\beta e^{\lambda/\beta} = \gamma$; and if $\gamma \leq \lambda e$ then $\rho(\cb,\tau) \geq \lambda^{-1}$. % \m{we do not know if there is gc?} %$t$ where $t$ is the unique root with $00$, %$\pr[|\core(R^{\cc}_n)- (1-1/\beta) n| > \eps n] = e^{-\Omega(n)}; $ % \item{(c)} If $\gamma > \lambda e$ let $\alpha= 1-x$ where $x$ is the unique root $<1$ to $xe^{-x}= \lambda/\gamma$; and otherwise let $\alpha=0$. %[Or let $\alpha= 1-x$ where $x$ is the unique root in $(0,1]$ to $xe^{-x}= \lambda_0/\gamma$, %so $\alpha>0$ if and only if $\gamma > \lambda_0 e$.] %\m{deleted: Let $\alpha= 1- \lambda_0/\beta$ if $\gamma > \lambda_0 e$ and let $\alpha= 0$ otherwise.} Then %[delete: $v(\core(R_n))/ n \to \alpha$ in probability and indeed??,] for each $\eps>0$ \begin{equation} \label{eqn.expcorebd} \pr(|v(\core(R_n))-\alpha n| > \eps n) = e^{-\Omega(n)}. \end{equation} %\item %\m{separate off last 2 parts?} %For any $\eps>0$ there exists $c$ such that $\pr(\frag( \core(R^{\ca}_n))>c)<\eps$ for each $n$. % %$\E[\frag( \core(R^{\ca}_n))] \leq \E[\frag(R^{\ca}_n))] = O(1)$, %so \whp $\core(R^{\ca}_n)$ has a giant component; %\m{weaken if not mc, to $\pr(\frag > c) < \eps$} %(and $\E(\Frag(\core(R^{\ca}_n))) \leq const$ if mc); \item{(d)} Let $\cal T$ denote the class of trees and let $\cd$ denote the class of connected graphs which are freely addable to $\ca$, with generating functions $T$ and $D$ %$T(x,y,z)$ and $D(x,y,z)$ respectively; and let $\rho=1/\gamma$. Suppose that $\gamma > \lambda e$ (so the probability that $\core(R_n)$ is empty is $e^{-\Omega(n)}$ by part (c)). Then %both $T(\rho,\tau)$ and $D(\rho,\tau)$ are finite $T(\rho,\tau) < D(\rho,\tau) < \infty$, and %\m{$T(\rho,\tau) < D(\rho,\tau)$?} %$\pr(R_n \mbox{ is connected}) \; \to \; e^{-D(\rho,\lambda)}\mbox{ as } n \to \infty,$ and the probability that $\core(R_n)$ is non-empty and connected tends to $e^{T(\rho,\tau)-D(\rho,\tau)}$ as $n \to \infty$. %\mbox{ as } n \to \infty, %$\kappa(\Frag(\core(R^{\ca}_n)))$ is asymptotically $\Po(D(\rho)-T(\rho))$ distributed, %and so the probability that $\core(R^{\ca}_n)$ is connected %$\to e^{T(\rho)-D(\rho)}$ as $ n \to \infty$. %where $D(x)$ and $T(x)$ are the egfs of $\cd$ and the class $\cal T$ of trees respectively %and $\rho=1/\gamma$ %(and $T(\rho)$ and $D(\rho)$ are finite). \end{description} \end{theorem} \smallskip \noindent \emph{Graphs on surfaces} Let us illustrate the theorem above for the class $\cg^S$ of graphs embeddable on a given surface $S$. It was shown in~\cite{cmcd08} that for any fixed surface $S$, the class $\cg^S$ of graphs embeddable on $S$ has growth constant~$\gamma$, where $\gamma$ is the {\em planar graph growth constant} (the same $\gamma$ for each surface), and recently this was very much improved to give an asymptotic formula for $|\gs_n|$, see~\cite{cfgmn11,bg09}. %\m{gao and bender?} From Gim\'enez and Noy~\cite{gn09a} we have $\gamma \approx 27.226878$. %\m{$27.2268777685$, thm 1 in gn orig} %\m{not here, to end of subsection?} %Of course, $\cg^S$ is bridge-addable, and the class $\cb$ %%$(\gs)^{\delta \geq 2}$ of connected graphs in $\gs$ with minimum degree at least 2 %is closed under subdividing edges: % it maintains at least factorial growth (by Lemma~\ref{lem.subdiv}). %or by Lemma~\ref{lem.subdiv2}). For any weighting $\tau$, %\m{was: with $\lambda_0=\lambda_1$} the weighted class $(\cg^S,\tau)$ is well-behaved (this is part of lemma~\ref{lem.wellb} below), and so by Theorem~\ref{thm.sumup} we see that $(\cg^S, \tau)$ is smooth; and when we specialise to the uniform case %$\tau={\bf 1}$ we obtain the result of~\cite{bcr08} that the (uniform) class $\cg^S$ is smooth (this also follows directly from the recent asymptotic formula for $|\cg^S_n|$ mentioned above). Further we obtain new information on the core of a uniform random graph $R_n \inu \gs$, as follows. Solving $\beta e^{1/\beta}= \gamma$ (using the more accurate figure for $\gamma$ %$\gamma \approx 27.2268777685$ in Theorem 1 in~\cite{gn09a}) gives $\beta = \beta_0 \approx 26.207554$, %\m{26.20755, 0.961843} and solving $\alpha = 1-1/\beta$ gives $\alpha = \alpha_0 \approx 0.961843$. %\m{0.961843} Thus the class $\cb$ of (connected) %\m{could omit conn, see .. ?} graphs in $\gs$ with minimum degree at least 2 %$(\gs)^{\delta \geq 2}$ has growth constant $\beta_0$ and %for $R_n \inu \cg^S_n$ $v(\core(R_n)) \approx \alpha_0 n$ \mbox{\whp.} % The growth constant $\beta_0$ for (connected) graphs in $\cg^S$ with each degree at least 2 is only slightly larger than the growth constant $\approx 26.18412$ for 2-connected graphs in $\gs$, from~\cite{bgw02,gn09a}. Also, the asymptotic number $\alpha_0 n$ of vertices in the core of $R_n$ is only slightly larger than the number of vertices in the largest block, which is about $0.95982 n$ by Theorem 5.4 of~\cite{gnr07}. Finally, let us consider the connectivity of the 2-core. The class $\cd$ of connected freely addable graphs is the class of all connected planar graphs, and from Corollary 1 in~\cite{gn09a} we have $e^{-D(\rho)} \approx 0.963253$, %\m{was $0.9632528217$} where $\rho=1/\gamma$. Further %, by considering trees of order up to 5, we see that %\m{$T(\rho) \approx 0.03742896$} $e^{T(\rho)} \approx 1.038138$, %\m{$T(x) = x+x^2/2 +x^3/2 + 2/3 x^4 + 25/24 x^5 + ..$} %\m{sum from $j$ is $\leq j^{-2} (ex)^j /(1-ex)$} so by Theorem~\ref{thm.sumup} part (d) the probability that $\core(R_n)$ is connected $\approx 0.999990$ %\m{was $0.9999896$} (for large $n$). Thus the probability that $\core(R_n)$ is not connected $\approx 10^{-5}$. For comparison note that $\pr(\Frag(R_n) = C_3) \sim e^{-D(\rho)} \rho^3/6 \approx 8 \cdot 10^{-6}$. %\m{prob not conn $> 1-e^{-\rho^5/5!}$, prob of $C_3$?} % \m{last para - not here} % Let the class $\ca$ of graphs be minor-closed and addable and have growth constant $\gamma>e$. % Then of course $\ca$ is % %\m{ was `trimmable and'} % bridge-addable; % the class $\cb$ of connected graphs in $\ca$ with minimum degree at least 2 is addable, % so it has a growth constant, and thus maintains at least factorial growth; % and every graph in $\ca$ is freely addable to $\ca$. % Thus the above result applies directly to any addable % class of graphs with growth constant $>e$ (and we already know all about $\cf$, the only addable monotonic % class of graphs with growth constant $\leq e$). %\m{work out constant for core for series-parallel, $ex(C_4)$ etc} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Appearances theorem} \label{subsec.apps} It is often useful to know that for $R_n \in_{\tau} \ca$, \whp $R_n$ contains many disjoint copies of a given connected graph $H$. % Suppose that $H$ has a specified root vertex $r$. We say that $H$ is {\em freely attachable} %\m{keep `freely'?} to $\ca$ if, given any graph $G \in \ca$ %disjoint from $H$ and vertex $v \in G$, the graph formed from the disjoint union $G \cup H$ %of $G$ and $H$ by adding the edge $vr$ is in $\ca$. Let $H$ be a graph on the vertex set $[h]=\{1,\ldots,h\}$, and let $G$ be a graph on the vertex set $[n]$ where $n>h$. Let $W \subset V(G)$ with $|W|=h$, and let the \emph{root} $r_W$ be the least element in $W$. We say that $H$ has a {\em pendant appearance} at $W$ in $G$ if (a) the increasing bijection from $[h]$ to $W$ gives an isomorphism between $H$ and the induced subgraph $G[W]$ of $G$; and (b) there is exactly one edge in $G$ between $W$ and the rest of $G$, and this edge is incident with the root $r_W$. We let $f_H(G)$ be the number of pendant appearances of $H$ in $G$, that is the number of sets $W \subseteq V(G)$ such that $H$ has a pendant appearance at $W$ in $G$. The next theorem extends results in~\cite{msw05,msw06,cmcd08,cmcd09}. %\m{refs ok?} \begin{theorem} \label{thm.appearances1} Let the weighted graph class $\cat$ %Let $\lambda>0$, $\nu>0$ and $\tau=(\lambda,\nu)$; let %the class $\ca$ of graphs be such that $\ca,\tau$ have growth constant~$\gamma$, %\m{deleted - let $\rho=\rho(\ca,\tau)$} and let $R_n \in_{\tau} \ca$. Let the connected graph $H$ %on the vertex set $\{1,\ldots,h\}$ be freely attachable to $\ca$. %Let $\ca$ be a class of graphs, and let the connected graph $H$ %on the vertex set $\{1,\ldots,h\}$ be freely attachable to $\ca$. %% which is addable and small, with growth constant~$\gamma$. %Let $\lambda>0$ and $\nu>0$, let $\tau=(\lambda,\nu)$, let $R_n \in_{\tau} \ca$, %and assume that $\ca,\tau$ has growth constant~$\gamma$. Then there exists $\alpha>0$ such that \[ \Pr[f_H(R_n) \leq \alpha n] = e^{-\Omega(n)}. \] \end{theorem} This result shows for example that, if the $k$-leaf star rooted at its centre is freely attachable to $\ca$, then $R_n$ has linearly many vertices of degree $k+1$, with exponentially small failure probability. It is possible to extend the theorem to consider graphs $H$ with (slowly) growing size, see for example Theorem 3.1 in~\cite{cb08}, but we do not pursue that here. If $\cat$ is well-behaved then we can be more precise about $f_H(R_n)$, extending Proposition 1.9 of~\cite{cmcd09}. \begin{prop} \label{thm.apps2} Let the weighted graph class $\cat$ be well-behaved with growth constant $\gamma$, %Let $\lambda>0$, $\nu>0$ and $\tau=(\lambda,\nu)$; let %the class $\ca$ of graphs be such that $\ca,\tau$ is well-behaved; %let $\rho=\rho(\ca,\tau)$, and let $R_n \in_{\tau} \ca$. Let the connected graph $H$ %on the vertex set $\{1,\ldots,h\}$ be freely attachable to $\ca$. %and let $X_n(H)$ be the number of pendant appearances of $H$ in $R_n$. Then %$f_H(R_n)/n \to \frac{\lambda_0 \lambda^{e(H)}}{\gamma^{v(H)} v(H)!}$ %in probability as $n \to \infty$. %\m{$\lambda_0 \lambda^{e(H)}$} \[ \frac{f_H(R_n)}{n} \to \; \lambda \cdot \frac{\lambda^{e(H)}}{\gamma^{v(H)} v(H)!} \;\;\mbox{ in probability as } n \to \infty.\] \end{prop} % The same result holds if we count disjoint pendant appearances. %\m{move this para later?} Indeed, if $\tilde{f}_H(R_n)$ %$\tilde{X}_n(H)$ denotes the number of pendant appearances of $H$ in $R_n$ that share a vertex or the root edge with some other pendant appearance of $H$, then $\E[\tilde{f}_H(R_n)] = O(1)$. %for series parallel, and(?) outerplanar, and ?? %compare $\beta$ to gc for 2-conn. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Definition of a `well-behaved' graph class} \label{subsec.wellb-def} Now at last in this section we can say precisely what we mean by a well-behaved class. We need first to introduce the notions of a graph class with a `\favl' dichotomy, and of a graph class `maintaining at least factorial growth'. Along the way we introduce `very well-behaved' graph classes. \subsubsection{Freely-addable-or-limited classes of graphs} \label{subsec.dichotomous} Recall that, given a class $\ca$ of graphs, the graph $H \in \ca$ is freely addable to $\ca$ if the disjoint union $G \cup H \in \ca$ whenever $G \in \ca$. We denote the class of graphs which are freely addable to $\ca$ by $\cf_{\ca}$. %\m{droppped $\cf$} For example, if $\ca$ is the class $\gs$ of graphs embeddable on a fixed surface $S$ then $\cf_{\ca}$ is the class $\cp$ of planar graphs. %Also, if $\ca$ is addable then $\cf(\ca)=\ca$. % Observe that %if $\ca$ contains components then $\cf(\ca)$ is decomposable; and if $\ca$ is minor-closed and bridge-addable then $\cf_{\ca}$ is minor-closed and addable. We say that a graph $H \in \ca$ is {\em limited} in $\ca$ if $kH$ is not in $\ca$ for some positive integer $k$. Here $k H$ denotes the disjoint union of $k$ copies of $H$. %For a minor-closed class, this is equivalent to some excluded minor for $\ca$ having each %component a minor of $H$. For example, if $\ca$ is $\gs$ as above then the graphs in $\ca$ which are limited in $\ca$ are the non-planar graphs, which are exactly the non-freely addable graphs. If $\ca$ is decomposable then no graph in $\ca$ is limited in $\ca$. Indeed if $H$ is freely addable to a class $\ca$ then $H$ is not limited in $\ca$ (recall that each graph in a decomposable class is freely addable to the class). We are interested in classes $\ca$ of graphs such that each graph $G \in \ca$ is either freely addable or limited (as we have noted it cannot be both): let us call such a graph class {\em \favl.} %freely-addable-versus-limited} {\em dichotomous}, or % {\em favl-dichotomous} for short. %\m{was tidy} %\m{satisfies a 0-1 law if $\pr(R_n \cup H \in \ca)$ tends to 0 or 1? for $\tau$ iff for $\bf 1$?} From what we have just seen, for any surface $S$ the class $\gs$ is \favl. If $\ca$ is decomposable then $\cf_{\ca}=\ca$ so $\ca$ is \favl. %moved to last section If $\ca$ is the class $\ex(k C_3)$ of graphs with at most $k$ vertex-disjoint cycles, then $\cf_{\ca}$ is the class of forests and each graph with a cycle is limited, so $\ca$ is \favl. % %For a minor-closed class, %with set $\cb$ of excluded minors, %being dichotomous is equivalent to each component $H$ of each excluded minor being limited, %that is $H$ being such that some excluded minor has each component a minor of $H$. An example of a class which is not \favl\ is the class $\ex(C_3 \cup C_4)$ of graphs with no minor $C_3 \cup C_4$, where $C_3$ is neither freely-addable nor limited. %We call a class $\ca$ of graphs {\em limited} if for each graph $H$ not freely-addable to $\ca$ %there is an integer $k$ such that $(k+1)H$ is not in $\ca$. %Let $\ca$ be a minor-closed class of graphs. %We say that {\em each component counts} if for each component $H$ of each %excluded minor for $\ca$ there is a positive integer $k$ such that $k H$ %is not in $\ca$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsubsection{Very well-behaved classes of graphs} \label{subsubsec.vwellbdef} It is conjectured~\cite{bnw09} that any proper minor-closed class $\ca$ of graphs has a growth constant, and it is natural to conjecture similarly that $\cat$ always has a growth constant. Part of the definition of $\cat$ being well-behaved %or very well-behaved will require that there is a growth constant. We (temporarily) call the weighted class $\cat$ of graphs {\em very well-behaved} if it is minor-closed, bridge-addable and \favl ; and if it either is decomposable, or it is closed under subdividing edges and has a growth constant. From what we have already seen, %\m{From what we have already seen - check} to show that $\cat$ must be very well-behaved when $\ca$ is a proper minor-closed addable class, or a class $\gs$, it suffices to show that the growth constant must exist. This is done in Sections~\ref{subsec.addable-gc} and~\ref{subsec.gs-gc}. Now let $\ca$ be the class of graphs with at most $k$ vertex-disjoint cycles. Then $\ca$ is minor-closed, bridge-addable, \favl\ and closed under subdividing edges. In the uniform case this class has growth constant $2^ke$~\cite{km08b}, and so it is %It may also be shown \m{done? ref?} that the class of graphs with at most $k$ vertex-disjoint cycles is very well-behaved. Furthermore, straightforward adaptations of the proof in~\cite{km08b} shows that the weighted class $\cat$ has a growth constant, %as long as $\lambda_0=\lambda_1$. and so it is very well-behaved. %\m{ok I trust!} However, %this is not true consider for example the class of graphs with no two vertex-disjoint cycles of length at least 4: this class is not decomposable nor closed under subdividing edges, and so it is not very well behaved. % (in the uniform case). To cover such further graph classes, we weaken the condition and define %\m{do we cover `such' classes?} a larger class of `well-behaved' graph classes. Unfortunately the definition is %less attractive. more involved. % but it will be easy to see that any very well-behaved graph class is well-behaved. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsubsection{Maintaining at least factorial growth} \label{subsec.maint} We shall want to consider classes of graphs which we can show do not have any sudden dips in their growth rate. Let us say that a weighted graph class $\cat$ of graphs {\em maintains at least factorial growth} if there exist an $\eta>0$ and a function $g(n)=(1+o(1))^n$ such that for each $n$ and each $j$ with $1 \leq j < n$ we have \begin{equation} \label{eqn.mafg} \tau(\ca_n) \geq \tau(\ca_{n-j}) \ (n)_j \ \eta^j \ g(n). \end{equation} An equivalent condition avoiding the function $g$ is that there exist an $\eta>0$ such that for each $\eps>0$, for each sufficiently large $n$, for each $1 \leq j 0$ such that~(\ref{eqn.mafg}) or~(\ref{eqn.mafg2}) holds for each $j$ with $1 \leq j \leq \delta n$. % then $\ca$ maintains at least factorial growth. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsubsection{Well-behaved classes of graphs} \label{subsec.wellbdef} %\m{deleted `The class $\ca$ is {\em monotone} if whenever $G'$ is a subgraph of $G$ %and $G \in \ca$ then $G' \in= \ca$.'} We may at last say exactly what `well-behaved' means. We start with the definition of a very well-behaved graph class $\ca$, and we simply replace the condition that $\ca$ be either decomposable or closed under subdividing edges by the condition that the subclass $\ca^{\delta \geq 2}$ is either `as small as the paths' or it is `consistently large'. (Recall that $\ca^{\delta \geq 2}$ is the class of graphs in $\ca$ with minimum degree at least~2.) %maintains at least factorial growth. It will be easy to check that any very well-behaved graph class is well-behaved. \smallskip \noindent {\bf Definition} The weighted class $\cat$ of graphs is {\em well-behaved} if it is %\m{was `monotone'} minor-closed, bridge-addable, \favl, and %; if the weighted class $\ca,\tau$ has a growth constant; and if the weighted class %$\cb,\tau$ of connected %\m{want connected?} %graphs in $\ca$ with minimum degree at least 2 $(\ca^{\delta \geq 2},\tau)$ either (a) is empty or has radius of convergence at least $\lambda^{-1}$ %\m{was $\lambda_0^{-1}$} or (b) maintains at least factorial growth. \smallskip \noindent From our observations in Section~\ref{subsec.boltzmann}, we obtain an equivalent condition if we replace the assumption that $\cat$ has a growth constant by the assumption that $(\cc,\tau)$ has a growth constant, where $\cc$ is the class of connected graphs in~$\ca$. Similarly, we could replace $\ca^{\delta \geq 2}$ by the class of connected graphs in $\ca$ with minimum degree at least 2. %To see that any very well-behaved graph class is well-behaved, we need only check that any addable proper minor-closed %class and any class closed under subdividing edges maintains at least factorial growth -- see .. not quite right \begin{lemma} \label{lem.wellb} Every very well-behaved weighted graph class is well-behaved, and in particular the weighted class $\cat$ is well-behaved in the following cases, with any $\tau$: \begin{description} \item{(a)} $\ca$ is minor-closed and addable, % with any $\tau$; \item{(b)} $\ca$ is the class $\gs$ of graphs embeddable on any given surface~$S$, % when $\lambda_0=\lambda_1$; \item{(c)} $\ca$ is the class of graphs which contain at most $k$ vertex-disjoint cycles, for any given positive integer $k$. % when $\lambda_0=\lambda_1$. \end{description} \end{lemma} %We need further definitions, though we still postpone the definition of a class being well-behaved. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Plan of the rest of the paper} \label{subsec.plan} The next section collects and proves various preliminary general results, and contains a proof of Lemma~\ref{lem.wellb} above which shows that certain graph classes %$\gs$ and any proper minor-closed addable graph class are well-behaved. After that, in Section~\ref{sec.proofU}, we prove the results stated in Section~\ref{subsec.boltzmann} %Theorem~\ref{thm.U} on the Boltzmann Poisson random graph. The next section proves most of the results %Theorem~\ref{thm.sumup} parts (a) and (b) presented in Section~\ref{subsec.2core} on smoothness and the $\core$; and the smoothness results allow us, after a brief section on Poisson convergence, to prove the results on $\Frag(R_n)$ and connectedness %Theorem~\ref{thm.Frag} in the preceding section, in Section~\ref{subsec.connresults}. %(from which part (c) Theorem~\ref{thm.sumup} follows). After that we prove the results on appearances given in Section~\ref{subsec.apps}, and finally we make some concluding remarks. %and the `appearances theorem' Theorem~\ref{thm.appearances1}, \m{prop?} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminary general results} \label{sec.prelims} This section presents various preliminary general results, %some of which may be of independent interest (for example Lemmas~\ref{lem.tauconn} and~\ref{lem.fragbound}), and gives a proof of Lemma~\ref{lem.wellb}, which shows that certain interesting graph classes are well-behaved. % %Given a graph $G$, let %\m{deleted $\Bridge(G)$, $\Cross(G)$ etc} %be the set of bridges, so that $|\Bridge(G)|=e_0(G)$; \m{wanted?} %and let $\Cross(G)$ be the set of non-edges between components, and let $\cross(G)=|\Cross(G)|$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Connectivity bounds for a bridge-addable class} %\subsection{Bounding connectedness probability and $\E[\frag(R)]$ for a bridge-addable class} %\subsection{Bounding the probability of being connected for a bridge-addable class} % and numbers of components} \label{sec.comps} We start with a lemma taken from~\cite{cmcd12}, which will be used several times in this paper. Part (a) is a special case of Theorem~2.1 in~\cite{cmcd12}, and extends Theorem 2.2 of~\cite{msw05}: % which though elementary has proved to be a key result; and Lemma~\ref{lem.tauconn} part (b) is a special case of Theorem~2.2 in~\cite{cmcd12}, and extends Lemmas 2.5 and 2.6 of~\cite{cmcd09}. (The paper~\cite{cmcd12} also gives asymptotic versions of these results, in the case when the class is closed also under deleting bridges, which match the results for forests described in~\ref{subsec.connresults}.) \begin{lemma} \label{lem.tauconn} Let the finite non-empty weighted set $\cat$ of graphs be\\ bridge-addable, %Let $\lambda>0$, $\nu>0$ and $\tau=(\lambda,\nu)$. and let $R \in_{\tau} \ca$. %that is, let the random graph $R$ take values in $\ca$, %with $\pr(R=H)= \lambda^{e(H)} \nu^{\kappa(H)}/\tau(\ca)$ for each $H \in \ca$. %\m{use $\leq_s$?} Then\\ (a) $\kappa(R)$ is stochastically at most $1+ \Po(\nu/\lambda)$, and so in particular\\ $\pr(R \mbox{ is connected}) \geq e^{-\nu/\lambda}$; %and $\pr(\kappa(R) >j) \leq (\nu/\lambda)^{j} / j!$ for each positive integer $j$; and\\ (b) $\E[\frag(R)] < 2 \nu /\lambda$. \end{lemma} %\m{shorten statement?} %\noindent % The second result is a special case of Theorem~2.2 in~\cite{cmcd12}, and % extends Lemmas 2.5 and 2.6 of~\cite{cmcd09}. % and improves on these results even in the case $\tau={\bf 1}$. %\begin{lemma} \label{lem.fragbound} % Let the finite non-empty weighted set $\ca,\tau$ of graphs be bridge-addable, %Let $\lambda>0$, $\nu>0$ and $\tau=(\lambda,\nu)$. % and let $R \in_{\tau} \ca$. %Let the weighted graph class $\ca,\tau$ be bridge-addable; %Let $\lambda>0$, $\nu>0$ and $\tau=(\lambda,\nu)$; %let $n$ be a positive integer such that $\ca_n$ is non-empty; %and let $R_n \in_{\tau} \ca$. % Then $\E[\frag(R)] < 2 \nu /\lambda_0$. %\end{lemma} %\subsection{Bounding $\E[\frag(R)]$ for a bridge-addable class} %\label{subsec.fragbound} %The next two lemmas show that $\frag(R_n)$ is typically small. %Both lemmas concern a bridge-addable class of graphs: %in the second lemma we assume also that the class is minor-closed and we learn more. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Growth constant for an addable class} \label{subsec.addable-gc} The following result is an extension of %Theorem 3.2 in~\cite{msw06} and Proposition 1.1 in~\cite{cmcd09}, and its proof follows similar lines. %We call a weighted graph $\ca,\tau$ {\em small} if for some %constant $c$ we have $\tau(\ca_n) \leq c^n n!$ for all $n$. \begin{lemma} \label{lem.addable-gc} Let $\ca$ be a non-empty addable subclass of a proper minor-closed class of graphs, and consider any weighting $\tau$. Then there is a constant $\gamma$ with $0<\gamma<\infty$, which does not depend of $\nu$, such that \[ (\tau(\ca_n)/n!)^{1/n} \to \gamma \;\;\mbox{as } n \to \infty.\] \end{lemma} \begin{proof} %Let $\tau^{(c)}(\ca_n)$ denote the total weight Let $\cc$ be the class of connected graphs in $\ca$. Then $\tau(\cc_n) \geq \tau(\ca_n) e^{-\nu/\lambda}$ by Lemma~\ref{lem.tauconn} (a), and so for all positive integers $a$ and $b$ \begin{eqnarray*} \tau(\ca_{a+b}) & \geq & \frac12 \binom{a+b}{a} \ \tau(\cc_a)\ \tau(\cc_b)\\ & \geq & 2 (a+b)! \ \frac{\tau(\ca_a) e^{-\nu/\lambda} }{2\ a!} \ \frac{\tau(\ca_b) e^{-\nu/\lambda}}{2\ b!}. \end{eqnarray*} Thus, if we set $f(n)= \frac{\tau(\ca_n)\, e^{-2 \nu/\lambda} }{ 2\, n!}$ then $f(a+b) \geq f(a) f(b)$, that is $f$ is supermultiplicative. Since $\ca$ is a subclass of a proper minor-closed class of graphs, there is a constant $c_1$ such that $|\ca_n| \leq n! c_1^n$, see~\cite{nstw06} (or~\cite{dn10} for a different proof). Also there is a constant $c_2$ such that each graph in $\ca$ has average degree at most $c_2$, by a result of %Kostochka~\cite{k82} and Thomason~\cite{t84}, Mader~\cite{mader68} (see also for example Diestel~\cite{diestel05}). %\m{(as we noted in the proof of Lemma~\ref{lem.mc1})- not now, give ref} Hence \[ \tau(\ca_n) \leq |\ca_n| \max\{1, \lambda^{n-1}\} \max\{ 1, \lambda_1^{c_2 n/2}\} \max \{\nu, \nu^n \}. \] % \leq n! \left( c_1 \max\{1, \lambda \}^{c_2/2} \max \{1, \nu \}\right)^n. Thus %$f(n) \leq c_3^n$ for a constant $c_3$, so that $\gamma = \sup_n f(n)^{1/n}$ satisfies $0<\gamma<\infty$; and since $f$ is supermultiplicative it follows by Fekete's lemma (see for example~\cite{lint-wilson} Lemma 11.6) that %there is a constant $\gamma$ with $0<\gamma< \infty$ such that as $n \to \infty$ we have $f(n)^{1/n} \to \gamma$ and so also $(\tau(\ca_n)/n!)^{1/n} \to \gamma$. % Finally note that $\gamma$ cannot depend on $\nu$ since $\ca$ contains all components (see the discussion following~(\ref{eqn.exp})). % $\cc$ has the same growth constant $\gamma$ as $\ca$ by the exponential formula \end{proof} %\begin{corollary} \label{cor.addable-gc} % Let $\ca$ be an addable minor-closed proper class of graphs. % Then there is a constant $\gamma$ with $0<\gamma<\infty$ such that % $(\tau(\ca_n)/n!)^{1/n} \to \gamma$ as $n \to \infty$. %\end{corollary} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Growth constant for $(\gs,\tau)$} \label{subsec.gs-gc} %In this subsection we show %present the perhaps unsurprising result %that each weighted graph class $\gs,\tau$ has a growth constant, %which does not depend on the surface $S$ or on the components parameter $\nu$. Since the class $\cp$ of planar graphs is minor-closed and addable, we know from the last subsection that, with any weighting $\tau$, the weighted graph class $(\cp,\tau)$ has a growth constant $\gamma(\cp,\tau)$, which does not depend on $\nu$. %As long as $\lambda_0=\lambda_1$, We may show that $(\gs,\tau)$ has the same growth constant $\gamma(\cp,\tau)$, by induction on the Euler genus of $S$, following the treatment of the uniform case in~\cite{cmcd08}. %It seems likely that the extra condition $\lambda_0=\lambda_1$ is not necessary here, but that is not immediate from %the proofs in~\cite{cmcd08}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{\Favl\ graph classes} %\section{Each component counts} \label{subsec.limited} It was shown in~\cite{cmcd08} that, for $R_n \inu \gs$ (the uniform case), the probability that $\Frag(R_n)$ is non-planar is $O(\ln n / n)$: here we improve and extend this result. Let us write $G \succeq_m H$ to mean that $G$ has a minor (isomorphic to) $H$. First we give a lemma concerning a single unwanted minor. %\m{need minor-closed? if so, we need that for well-behaved?} %For the proof we use one preliminary lemma. %\begin{lemma} \label{lem.m2conn} %\m{put this lemma inside the proof of the previous lemma?} % Let $\ca$ be minor-closed and bridge-addable. % Let $K$ be a component of an excluded minor $H$ for $\ca$, % and be minor-minimal with this property. Then $K$ is 2-connected. %\end{lemma} % %\begin{proof} % Suppose that $K$ is not 2-connected, and let $v$ be a cut-vertex. % Then there are disjoint graphs $K'$ and $K''$ with vertices $v' \in K'$ % and $v'' \in K''$ such that identifying $v'$ and $v''$ yields $K$. % Let $H'$ be the graph obtained from $H$ by replacing $K$ by $K' \cup K''$. % Then $H'$ is not in $\ca$, since otherwise $H'$ plus the edge $v'v''$ would be in $\ca$ % and hence $H$ would be in $\ca$. % Let $M$ be an excluded minor for $\ca$ which is a minor of $H'$. % Then some component of $M$ is a minor of $K'$, which contradicts the minimality of $K$. %\end{proof} % \m{Assume throughout that we can always add isolated vertices?} %Let $\ca$ be bridge-addable. If $H$ is limited in $\ca$ then so is $\core(H)$. \begin{lemma} \label{lem.Frag2} Let $\ca$ be bridge-addable, let $R_n \in_{\tau} \ca$, let $H$ be a connected graph, and let $k$ be a non-negative integer. Then \begin{equation} \label{eqn.bound0} \pr( \Frag(R_n) \succeq_m H) \leq \frac{3 \nu k}{2 \lambda} \frac{\ln n}{n} + \frac{6 \nu}{\lambda n} + \pr(R_n \succeq_m (k+1)H). \end{equation} Further if $H$ is 2-connected then we may improve the first term in the bound to $\frac{3 \nu k}{2 \lambda v(H)} \frac1{n}$. %\m{$H$ is not an edge} \end{lemma} %\noindent %\m{$\pr( \Frag(R_n) = H) \leq .. + \pr(R_n \mbox{ has } \geq (k+1) \mbox{ disjoint pendant subgraphs } H)$} \medskip \begin{proof} %{Lemma~\ref{lem.Frag}} Let $\omega=\omega(n)= \lfloor n/3 \rfloor$. Let $\cb^{j}_n$ be the class of graphs $G \in \ca_n$ such that $G \in \ex(k+1)H$, $\frag(G) \leq \omega$, $\Frag(G) \succeq_m H$, and there are exactly $j$ vertices in the lex-first component $C$ of $\Frag(G)$ with minor $H$. Given a graph $G \in \cb^{j}_n$, add any edge between this component $C$ and a vertex in $\Bigc(G)$, to form $G'$. This gives $j \cdot \bigc(G) \geq j \cdot 2n/3$ constructions of graphs $G' \in \ca$. Each graph $G'$ constructed can have at most $k$ (oriented) bridges $uv$ such that the component of $G'-uv$ containing $u$ has order at least $2n/3$, and the component containing $v$ has order $j$ and has a minor $H$ (since otherwise the original graph $G$ is not in $\ex(k+1)H$). %containing one end of $e$ has at least $2n/3$ vertices, and orienting $e$ away from this large side, %the head of $e$ is in a component of order $j$ with a minor $H$. Thus $G'$ can be constructed at most $k$ times. Hence \[ j \frac{2n}{3} \ \frac{\lambda}{\nu} \tau(\cb^j_n) \leq k \tau(\ca_n) \] so \[ \tau(\cb^j_n) \leq \frac{1}{j} \frac{3 \nu k}{2 \lambda n} \tau(\ca_n). \] Let $\cb_n= \cup_{j \leq \omega} \cb^j_n$. Since $\sum_{v(H) \leq j \leq \omega} 1/j \leq \ln \omega$ we have \[ \tau(\cb_n) \leq \frac{3 \nu k}{2 \lambda} \frac{\ln n}{n} \tau(\ca_n). \] Thus $\tau(\{G \in \ca_n: \Frag(G) \succeq_m H\})$ is at most %\begin{eqnarray} \begin{equation} \nonumber %\label{eqn.bound1} \frac{3 \nu k}{2 \lambda} \frac{\ln n}{n} \tau(\ca_n) + \tau(\{G\!\in\!\ca_n\!: \frag(G)\!>\!\omega\}) + \tau(\{G\!\in\!\ca_n\!: G \succeq_m (k\!+\!1)H \}). \end{equation} %\end{eqnarray} But recall from Lemma~\ref{lem.tauconn} (b) that $\E[\frag(R_n)] < 2 \nu/\lambda$, and so \[ \pr(\frag(R_n) > n/3) < \frac{6 \nu}{\lambda n}.\] Hence we may divide by $\tau(\ca_n)$ in the last displayed inequality %~(\ref{eqn.bound1}) to obtain~(\ref{eqn.bound0}). \smallskip Now suppose that $H$ is 2-connected. %Let $\tilde{\cb}_n$ be the class of graphs $G \in \ca_n$ such that $G \in \ex(k+1)H$, %$\frag(G) \leq \omega$ and $\Frag(G) \succeq_m H$. %Let $G \in \tilde{\cb}_n$. Let $G \in {\cb}_n$, where $\cb$ is as above. Then some block of some component of $\Frag(G)$ has a minor $H$. %Pick a vertex in such a block $B$ as the root. Add any edge between a vertex in such a block and a vertex in $\Bigc(G)$, to form $G'$. This gives at least $v(H) \cdot {\bigc(G)} \geq 2 v(H) n/3$ constructions of graphs $G' \in \ca$. Each graph $G'$ constructed can have at most $k$ (oriented) bridges $uv$ such that the component of $G'-uv$ containing $u$ has order at least $2n/3$, and the component containing $v$ is in a block with a minor $H$. %(since otherwise the original graph $G$ is not in $\ex(k+1)H$). %Each graph $G'$ can have at most $k$ bridges $e$ such that the component of $G'-e$ containing one %end of $e$ has at least $2n/3$ vertices, and orienting $e$ away from this large side, %the head of $e$ is in a block with a minor $H$. Thus $G'$ can be constructed at most $k$ times. Hence \[ v(H) \frac{2n}{3} \ \frac{\lambda}{\nu} \tau(\tilde{\cb}_n) \leq k \tau(\ca_n) \] and we may proceed as before. %This completes the proof. \end{proof} \medskip \noindent Recall that $\cf_{\ca}$ denotes the class of graphs which are freely addable to~$\ca$. The last lemma yields: \begin{lemma} \label{lem.Frag} Let $\ca$ be minor-closed, bridge-addable and \favl; and let $R_n \in_{\tau} \ca$ for $n=1,2,\ldots$. %let $\cf$ denote the class of graphs freely addable to $\ca$, and suppose that each component counts. Then there is a constant $c$ such that %$\pr(\Frag(R_n) \not\in \cf(\ca)) \leq \frac{c \nu}{n \lambda}$ for each~$n$. \[ \pr(\Frag(R_n) \not\in \cf_{\ca}) \leq \frac{c \nu}{n \lambda} \;\;\; \mbox{ for each } \;n. \] \end{lemma} \begin{proof} %{Lemma~\ref{lem.Frag}} As we noted in Section~\ref{subsec.dichotomous}, $\cf_{\ca}$ is minor-closed and addable, with a finite set of excluded minors each of which is 2-connected. %Thus if $H \not\in \cf(\ca)$ then $H$ has a 2-connected minor $K$ which %is a component of an excluded minor for $\ca$. %Let $\cal K$ be the class of graphs $G$ with a minor $K$. %\m{(The Robertson and Seymour~\cite{rs04} theory of graph minors, see for example Diestel~\cite{diestel05}, %shows that a set of excluded minors must be finite.)} %It follows that there are only finitely many choices for $K$, Thus it suffices to prove that for each excluded minor $K$ for $\cf_{\ca}$ there is a constant $c_K$ such that $\pr(\Frag(R_n) \succeq_m K) \leq \frac{c_K \nu}{n \lambda}$ for each $n$. But if $K \in \ca$ then $K$ must be limited in $\ca$ since $\ca$ is \favl, so there is a $k$ such that $(k+1) K \not\in \ca$; and now we may use Lemma~\ref{lem.Frag2} for the 2-connected graph~$K$. \end{proof} %\m{mention 0,1 law?} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Maintaining at least factorial growth} \label{subsec.growth} We shall want to consider weighted graph classes $\cat$ (with each vertex degree at least 2) which %we can show do not have any sudden dips in their growth rate, and indeed which %Let $\ca$ be a class of graphs; and let $\lambda>0$ and $\nu>0$, and $\tau=(\lambda,\nu)$. %Let us say that $\ca, \tau$ {\em maintains at least factorial growth} %if there exist $\delta>0$, $\eta>0$ and a function $g(n)=(1+o(1))^n$ such that %for each $n$ and each $j$ with $1 \leq j \leq \delta n$ we have %\[ \tau(\ca_n) \geq \tau(\ca_{n-j}) \ (n)_j \ \eta^j \ g(n). \] maintain at least factorial growth, as defined in Section~\ref{subsec.maint}. It is easy to see that if $\cat$ has growth constant $\gamma >0$ then $\cat$ maintains at least factorial growth. For let $0<\eps<1$ (for example take $\eps=\frac12$) and let $n_0$ be such that $(1-\eps)^n n! \gamma^n \leq \tau(\ca_n) \leq (1-\eps)^{-n} n! \gamma^n$ for each $n \geq n_0$. Then for each $n > n_0$ and $1 \leq j \leq n-n_0$, \[ \tau(\ca_n) \geq (1-\eps)^n n! \gamma^n = (1-\eps)^n (n-j)! \gamma^{n-j} (n)_j \gamma^j \geq (1-\eps)^{2n} \tau(\ca_{n-j}) (n)_j \gamma^j, \] and~(\ref{eqn.mafg}) follows for each $1 \leq j 0$ and the function $g_1(n)=(1+o(1))^n$ be such that for each $n$ and % each $j$ with $1 \leq j < n$ we have %\begin{equation} \label{eqn.cacb1} % \tau(\cb_n) \geq \tau(\cb_{n-j}) \ (n)_j \ \eta^j \ g_1(n). %\end{equation} % Let $g_2(n) = \tau(\cb_n)/\tau(\ca_n)$, so that $g_2(n)=(1+o(1))^n$. % Next let $g_3(n) = \min_{1 \leq j < n} g_2(n-j)$. Then it is easy to check that % $g_3(n)=(1+o(1))^n$. But for each $j$ with $1 \leq j < n$, %\begin{equation} \label{eqn.cacb2} % \tau(\cb_{n-j})=g_2(n-j) \tau(\ca_{n-j}) \geq g_3(n) \tau(\ca_{n-j}). %\end{equation} % Now $\tau(\ca_n) \geq \tau(\cb_n)$, and so by~(\ref{eqn.cacb1}) and~(\ref{eqn.cacb2}) %\[ % \tau(\ca_n) \geq \tau(\ca_{n-j}) \ (n)_j \ \eta^j \ g_4(n) %\] % where $g_4(n) = g_1(n) g_3(n) =(1+o(1))^n$. %\end{proof} % \medskip Finally here let us check that a seemingly more `local' and weaker condition implies that $\ca$ maintains at least factorial growth (as defined at~(\ref{eqn.mafg2})). \begin{lemma} \label{lem.malfgnod} Assume that $\ca_n \neq \emptyset$ for infinitely many $n$. Let $0<\delta \leq 1$, $0<\eta\leq 1$ and $g(n)=(1+o(1))^n$; and suppose that %we have %~(\ref{eqn.mafg}), that is \[ \tau(\ca_n) \geq \tau(\ca_{n-j}) \ (n)_j \ \eta^j \ g(n) \] % Let $\delta >0$ and $\eta>0$; and %$g(n)=(1+o(1))^n$; and % suppose that for each $\eps>0$, we have %~(\ref{eqn.mafg}), that is %\[ \tau(\ca_n) \geq \tau(\ca_{n-j}) \ (n)_j \ \eta^j \ e^{-\eps n} \] for each sufficiently large $n$ and each $1 \leq j \leq \delta n$. Then $\ca$ maintains at least factorial growth (with the same $\eta$). % though perhaps with a different function~$g$). \end{lemma} \begin{proof} %We may assume that $\delta \leq 1$ and $\eta \leq 1$. Let $0<\eps \leq 1$. %\frac12$. Let $N_0$ be sufficiently large that $g(n) \geq (1-\delta \eps/2)^n$ for all $n \geq N_0$. Let $N \geq N_0$ be such that $\ca_{N} \neq \emptyset$. Let us first show that \begin{equation} \label{eqn.maint1} \tau(\ca_n) \geq (n)_j \ \eta^j e^{-\eps n} \cdot \tau(\ca_{n-j}) \end{equation} for each $n >N$ and $j=1,\ldots,n-N$. %for $n$ sufficiently large. %For simplicity we shall ignore rounding. %Let $j \sim \delta^{-1} \log\log n$. % %Now let us prove~(\ref{eqn.maint1}). Let $n>N$ and $1 \leq j \leq n-N$. Let $n_i= \lfloor (1-\delta)^i n \rfloor$ for $i=0,1,2,\ldots$. Let $i_0$ be the least $i$ such that $n_i \leq n-j$, and redefine $n_{i_0}$ as $n-j$. Observe that $\sum_{i=0}^{i_0-1} n_i \leq n \sum_{i \geq 0} (1-\delta)^i = n/\delta$. Note also that %$\ln(1-\delta \eps/2) \geq - \delta \eps$ since $\delta \eps/2 \leq 1/2$, %$\ln(1-x/2) \geq - x$ for $0N$, and further we may assume that $\eta \leq 1$. Let $\alpha = \max_{1 \leq i \leq N} \{ \tau(\ca_i)/\tau(\ca_{N}) \}$. Let $c = (\alpha N!)^{-1}$, and note that $0N$, \begin{equation} \label{eqn.maint2} \tau(\ca_n) \geq \tau(\ca_{n-j})\, (n)_j \ \eta^j e^{-\eps n} \cdot c \end{equation} for each $n >N$ and $j=1,\ldots,n-1$. Since $c \leq 1$ this is immediate from~(\ref{eqn.maint1}) for $j \leq n-N$. So assume that $n-N0$. We will show that $\tau(\ca_n) \geq n! \ \eta^n e^{-2\eps n}$ for $n$ sufficiently large. % For simplicity we shall ignore rounding. % Let $j \sim \delta^{-1} \log\log n$. % Let $N$ be sufficiently large that $g(n) \geq (1-\delta \eps)^n$ for all $n \geq N$. % Let $n_i=(1-\delta)^i n$ for $i=0,1,\ldots,j$. Observe that $n_j = n/(\log n)^{\Theta(1)}$ % and $\sum_in_i \leq n \sum_{i \geq 0} (1-\delta)^i = n/\delta$. % Consider $n$ sufficiently large that $n_j \geq N$. % Thus % \[ \prod_{i=0}^{j-1} g(n_i) \geq (1-\delta \eps)^{\sum_i n_i} \geq (1-\delta \eps)^{n/\delta} % \geq e^{-\eps n}. \] %\begin{eqnarray*} % \tau(\ca_n) % & \geq & % \prod_{i=0}^{j-1} (n_i)_{(\delta n_i)} \eta^{\delta n_i} g(n_i) \cdot \tau(\ca_{n_j})\\ % & \geq & % (n)_{n-n_j} \eta^{n} \prod_{i=0}^{j-1} g(n_i) \cdot 1 % \;\; \geq \;\; % \frac{n!}{n_j!} \eta^n e^{-\eps n}. %\end{eqnarray*} % Now let us upper bound $n_j!$. Recall that $\ln(1-\delta) < - \delta$. Thus % $(1-\delta)^j = e^{j \ln(1-\delta)} = o(e^{- \delta j}) = o(1/\ln n)$. Hence for $n$ sufficiently large, % $n_j \leq \eps n/\ln n$ and then $n_j! \leq n^{n_j} =e^{n_j \ln n} \leq e^{\eps n}$. % Thus $\tau(\ca_n) \geq n! \ \eta^n e^{-2\eps n}$ for $n$ sufficiently large, as required. %\end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Being well-behaved: proof of Lemma~\ref{lem.wellb}} \label{subsec.l2.1} If $\ca$ is an addable proper minor-closed class of graphs then $\ca$ is decomposable, and $\cat$ has a growth constant by lemma~\ref{lem.addable-gc}; and if $\ca$ is $\gs$, or $\ca$ is the class of graphs which contain at most $k$ vertex-disjoint cycles, then $\ca$ is closed under subdividing edges, and %if also $\lambda_0=\lambda_1$ then %by Lemma~\ref{lem.tau-gs2} $\cat$ has a growth constant. %(see Section~\ref{subsec.gs-gc} for $\cg^S$). Also in each case $\ca$ is \favl, as we saw in Section~\ref{subsec.dichotomous}, and so $\cat$ is very well-behaved. It remains to show that each very well-behaved weighted graph class $\cat$ is well-behaved. If $\ca^{\delta \geq 2}$ is empty then $\cat$ is well-behaved, so we may assume that $\ca^{\delta \geq 2}$ is non-empty. %and to do this we need only show that it maintains at least factorial growth. %\m{deleted: (We postpone discussion of $\ex(k C_t)$.)} Suppose first that $\ca$ is closed under subdividing edges. Then also $\ca^{\delta \geq 2}$ is closed under subdividing edges, so by Lemma~\ref{lem.subdiv} $(\ca^{\delta \geq 2}, \tau)$ maintains at least factorial growth; and so $\cat$ is well-behaved. So suppose now that $\ca$ is decomposable. Then $\ca$ is addable, and so also $\ca^{\delta \geq 2}$ %of graphs in $\ca$ with minimum degree at least 2 is addable. By Lemma~\ref{lem.addable-gc}, $(\ca^{\delta \geq 2},\tau)$ has a growth constant, and so %by Lemma~\ref{lem.tauconn} a fortiori it maintains at least factorial growth, as noted in Section~\ref{subsec.maint}. This completes the proof. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{$\rho(\ca,\tau)$ as $\tau$ varies} \label{subsec.tau-vary} %\m{not for paper?} Consider a proper minor-closed class $\ca$ of graphs, with $\rho(\ca,(1,1))$ finite. For example if $\ca$ contains the class $\cf$ of forests then $\rho(\ca,(1,1)) \leq \rho(\cf,(1,1)) = e^{-1} < \infty$. We saw that the radius of convergence $\rho(\ca,\tau)$ does not depend on the component parameter $\nu$. %Let us consider the case when $\lambda_0=\lambda_1= \lambda$ %(with a slight abuse of notation, as $\lambda$ is now a real number), %, so that $\tau$ is $((\lambda,\lambda),1)$. Let us write $\rho(\lambda)$ for $\rho(\ca,\tau)$. Let $c=c(\ca)$ be the maximum average degree of a graph in $\ca$, and recall that $c$ is finite (see the proof of Lemma~\ref{lem.addable-gc}). Note that $c \geq 2$: for if $c<2$ and $\cb$ is a class of all graphs with average degree at most $c$, %such that each graph $G$ in $\cb_n$ has $e(G) \leq (1-\eps)n$. then \[ |\cb_n| = \sum_{0 \leq m \leq cn/2} \binom{\binom{n}{2}}{m} \leq n\left( \frac{en}{c} \right)^{cn/2} = e^{(c/2) n \log n},\] so $(|\cb_n| / n!)^{1/n} = o(1)$, that is $\rho(\cb,\lambda)=0$. (See~\cite{gmsw05} for related details.) \begin{prop} \label{prop.mc-tauvary} %Let $\tau=(\lambda,1)$. The function $\rho(\ca,\lambda)$ is continuous and strictly decreasing on $(0,\infty)$. If $\; 0<\lambda \leq 1$ then \[\rho(\ca,1)\, \lambda^{-1} \leq \rho(\ca,\lambda) \leq \rho(\ca,{1}) \lambda^{-c/2}, \] and if $\: \lambda \geq 1$ then \[\rho(\ca,{1}) \lambda^{-c/2} \leq \rho(\ca,\lambda) \leq \rho(\ca,{1}) \lambda^{-1}.\] \end{prop} For the class $\cf$ of forests we have $c=2$, and \[ \rho(\cf,\lambda) = \rho(\cf,{\bf 1}) \lambda^{-1} = (e \lambda)^{-1}\] as we already noted; and we see that the inequalites above for $\rho(\ca,\lambda)$ are tight. \smallskip \begin{proof} To show $\rho(\ca,1)\, \lambda^{-1} \leq \rho(\ca,\lambda)$ for $0<\lambda \leq 1$. Let $0<\eps<1$. Let $\ca' = \{ G \in \ca: e(G) \leq (1-\eps) v(G)\}$, and let $\ca'' = \ca \setminus \ca'$. Then %for each $\lambda >0$ we have $\rho(\ca',\lambda)= \infty$ as we saw above, and $\rho(\ca'',\lambda) = \rho(\ca,\lambda)$. Then for $\lambda \leq 1$ \[ \tau(\ca_n'') \leq | \ca_n''| \, {\lambda}^{(1-\eps)n} \leq | \ca_n| \, {\lambda}^{(1-\eps)n},\] and so $\rho(\ca, \lambda) = \rho(\ca'', \lambda) \geq \rho(\ca,{\bf 1}) \, {\lambda}^{-(1-\eps)}$. But this holds for each $0<\eps<1$ so $\rho(\ca, \lambda) \geq \rho(\ca,{\bf 1}) \hat{\lambda}^{-1}$. (We needed no assumptions on $\ca$ here.) \smallskip To show $\rho(\ca,\lambda) \leq \rho(\ca,{1}) \lambda^{-1}$ for $\lambda \geq 1$. As we saw following~(\ref{eqn.exp}), $\rho(\cc,\lambda)= \rho(\ca,\lambda)$, where $\cc$ is the class of connected graphs in $\ca$. Thus for $\lambda \geq 1$, $\tau(\cc_n) \geq |\cc_n| {\lambda}^{n-1}$, so $\rho(\cc,\lambda) \leq \rho(\cc,{\bf 1})/{\lambda}$ and hence $\rho(\ca,\lambda) \leq \rho(\ca,{\bf 1})/{\lambda}$. For the remaining inequalities, observe that $\tau(\ca_n) = \sum_{G \in \ca_n} \lambda^{e(G)}$. Thus if ${\lambda} \leq 1$, $\tau(\ca_n) \geq |\ca_n| {\lambda}^{cn/2}$, and so $\rho(\ca,\lambda) \leq \rho(\ca,{\bf 1}) {\lambda}^{-c/2}$; and if ${\lambda} \geq 1$, $\tau(\ca_n) \leq |\ca_n| {\lambda}^{cn/2}$, and so $\rho(\ca,\lambda) \geq \rho(\ca,{\bf 1}) {\lambda}^{-c/2}$. \smallskip To show that $\rho(\ca,\lambda)$ is strictly decreasing on $(0,\infty)$, consider $\ca''$ from the first part of the proof, with say $\eps=\frac12$. Let $\eta>0$. Then \[ \sum_{G \in \ca_n''} ((1+\eta) \lambda)^{e(G)} \geq (1+\eta)^{ n/2} \cdot \sum_{G \in \ca_n''} \lambda^{e(G)}\] and so \[ \rho(\ca,(1+\eta)\lambda) = \rho(\ca'',(1+\eta)\lambda) \leq (1+\eta)^{-\frac12} \rho(\ca,\lambda).\] Now to show that $\rho(\ca,\lambda)$ is continuous on $(0,\infty)$, observe that \[ \sum_{G \in \ca_n} ((1+\eta) \lambda)^{e(G)} \leq (1+\eta)^{cn/2} \cdot \sum_{G \in \ca_n} \lambda^{e(G)} \] and so \[ \rho(\ca,(1+\eta)\lambda) \geq (1+\eta)^{-c/2} \rho(\ca,\lambda).\] \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Distribution of the Boltzmann random graph} \label{sec.proofU} Let us first check equation~(\ref{eqn.Agen}). Recall that the class $\ca$ of graphs is closed under isomorphism. We identify an unlabelled graph on $n$ vertices with an equivalence class under graph isomorphism of graphs on vertex set $[n]$. Since each graph $H \in \cu \ca_n$ consists of $\frac{n!}{\aut(H)}$ graphs $G \in \ca_n$, we have \[ \frac{x^{v(H)} y^{e(H)} z^{\kappa(H)}}{\aut(H)} = \sum_{G \in H} \frac{\aut(H)}{v(H)!} \frac{x^{v(H)} y^{e(H)} z^{\kappa(H)} }{\aut(H)} = \sum_{G \in H} \frac{x^{v(G)} y^{e(G)} z^{\kappa(G)} }{v(G)!}. \] Thus \[ A(x,y,z) %= \sum_{G \in \ca} \frac{z^{v(G)}}{v(G)!} = \sum_{H \in \cu \ca} \sum_{G \in H} \frac{x^{v(G)} y^{e(G)} z^{\kappa(G)} }{v(G)!} = \sum_{H \in \cu \ca} \frac{x^{v(H)}y^{e(H)} z^{\kappa(H)}}{\aut(H)}, \] proving~(\ref{eqn.Agen}). \bigskip \begin{proofof} {Theorem~\ref{thm.U}} Each sum and product below is over all $H$ in $\cu\cc$. Let the unlabelled graph $G$ consist of $n_H$ components isomorphic to $H$ for each $H \in \cu \cc$, where $0 \leq \sum_{H} n_H < \infty$. Then \[ \rho^{v(G)} = \prod_{H} \rho^{v(H) n_H}, \;\; \lambda^{e(G)} = \prod_{H} \lambda^{e(H) n_H}, \;\; \nu^{\kappa(G)} = \prod_{H} \nu^{n_H} \] and \[ \aut(G) = \prod_{H} \aut(H)^{n_H} {n_H}! .\] Hence \[ \frac{ \rho^{v(G)} \lambda^{e(G)} \nu^{ \kappa(G)} }{\aut(G)} = \prod_{H} \frac{\mu(H)^{n_H}}{n_H!}.\] % and %\[ \lambda^{e(G)} = \prod_{H} \lambda^{e(H) n_H}. \] Also since $\sum_{H} \mu(H) = C(\rho, \tau)$ by~(\ref{eqn.Agen}) applied to $\cc$, \[ \frac{1}{A(\rho,\tau)} = e^{-C(\rho,\tau)} = \prod_{H} e^{-\mu(H)}. \] Hence \begin{eqnarray*} \pr[R =G] &=& e^{-C(\rho,\tau)} \frac{ \rho^{v(G)} \lambda^{e(G)} \nu^{ \kappa(G)} }{\aut(G)}\\ &=& \prod_{H} e^{-\mu(H)} \frac{\mu(H)^{n_H}}{n_H!}\\ &=& \prod_{H} \pr[\Po(\mu(H))=n_H]. \end{eqnarray*} Thus the probability factors appropriately, and the family of random variables $\kappa(R,H)$ for $H \in \cu\cc$ satisfies \[ \pr[\kappa(R,H)=n_H \;\; \forall H \in \cu\cc] = \prod_H \pr[\kappa(R,H)=n_H]. \] This holds for every choice of non-negative integers $n_H$ with $\sum_{H \in \cu\cc} n_H < \infty$, and thus also without this last restriction (since both sides are zero if the sum is infinite). This completes the proof of the theorem. \end{proofof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Smoothness and 2-core: proof of Theorem~\ref{thm.sumup}} \label{sec.proofs} In this section we deduce Theorem~\ref{thm.sumup}, after two preliminary subsections: one on deducing smoothness for a class $\ca$ from smoothness for the class of connected graphs in $\ca$, and one on smoothness for classes of connected graphs. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Smoothness: from connected to general} \label{subsec.contogen} %Observe that $\ca$ is decomposable if and only if each graph in $\ca$ it is freely addable to $\ca$. %Recall that $\gs$ denotes the class of graphs embeddable on a given surface~$S$; %and note that $\gs$ is %\m{move to previous section?} %minor-closed \m{delete minor-closed?} and %bridge-addable, %and the graphs freely addable to $\gs$ are precisely the planar graphs. %Note also from McDiarmid~\cite{cmcd06} that, for $R_n \inu \gs_n$, \whp $\Frag(R_n)$ is planar. %\m{?Let $\cf$ denote the class of graphs $F$ such that $\pr(R_n \cup F \in \ca) \to 1$ as $n \to \infty$, or use $R_n^{\cc}$?} \begin{lemma} \label{lem.smoothconv} Let the class $\ca$ of graphs be bridge-addable, %\m{?replace by - each component counts?} %let $\lambda>0$, $\nu>0$ and $\tau=(\lambda, \nu)$; and let $R_n \in_{\tau} \ca$. %let $\cb$ be freely addable to $\ca$, %let $\cd$ be the class of connected graphs in $\cb$, Let $\cf$ denote the class $\cf_{\ca}$ of graphs freely addable to~$\ca$, and suppose that \whp $\Frag(R_n) \in \cf$. % is freely addable to $\ca$. Let $\cc$ be the class of connected graphs in $\ca$, let $\rho = \rho({\cal C},\tau)$ satisfy $0<\rho<\infty$, and suppose further that $(\cc,\tau)$ is smooth. Then $F(\rho,\tau)$ is finite, where $F$ is the exponential generating function for $\cf$; and the weighted class $\cat$ is smooth. \end{lemma} %\m{could have $\cf$ as the asymptotically freely addable graphs?} \begin{proofof}{Lemma \ref{lem.smoothconv}} %Let $\cb$ denote the class of all graphs freely addable to~$\ca$. %Let $a_n=|\ca_n|$, $b_n=|\cb_n|$ and $c_n=|\cc_n|$. Recall that $F(x,\tau) = \sum_{j \geq 0} \tau(\cf_j) x^j /j!$. We shall show that $F(\rho,\tau)$ is finite and $\tau(\ca_n) \sim F(\rho,\tau) \tau(\cc_n)$, from which it will follow immediately that $\cat$ is smooth. % Let $0<\eta<1$. Then we are to show that $F(\rho,\tau)$ is finite, and that for $n$ sufficiently large \begin{equation} \label{eqn.ctoa} (1-\eta) F(\rho,\tau) \tau(\cc_n) \leq \tau(\ca_n) \leq (1+\eta) F(\rho,\tau) \tau(\cc_n). \end{equation} Let $\eps>0$ be sufficiently small that $\eps \leq 1/(e^{\nu/\lambda}+2)$, and $(1-2\eps)^{-1}(1+\eps) \leq 1+\eta$ and $(1-\eps)^2 \geq 1 - \eta$. % By our assumptions and Lemma~\ref{lem.tauconn} (b), %\m{change?} we may fix positive integers $k$ and $n_0$ sufficiently large that $\sum_{j=0}^{k} \tau(\cf_j) \rho^j/j!$ is at least $(1-\eps) F(\rho,\tau)$ if $F(\rho,\tau)$ is finite, and is at least $e^{\nu/\lambda}+2$ otherwise; and $\pr[\frag(R_n)>k] < \eps$ and $\pr[\Frag(R_n) \not\in \cf]< \eps$ for all $n \geq n_0$. Since $(\cc,\tau)$ is smooth, there exists $n_1 \geq n_0$ sufficiently large that for all $n \geq n_1$, the ratio $\tilde{r}_n = n \tau(\cc_{n-1})/\tau(\cc_{n})$ satisfies \[ (1-\eps)^{1/k} \rho < \tilde{r}_n < (1+\eps)^{1/k} \rho. \] Then for each $n \geq n_1 +k$ and each $j=1,\ldots,k$, since \[ \frac{(n)_j \tau(\cc_{n-j})} {\tau(\cc_{n})} = \prod_{i=1}^j \tilde{r}_{n-i+1} \] we have \[ (1-\eps) \rho^j < \frac{(n)_j \tau(\cc_{n-j})}{\tau(\cc_{n})} < (1+\eps) \rho^j. \] Denote $\sum_{j=0}^{k} \binom{n}{j} \tau(\cf_j) \tau(\cc_{n-j})$ by $\tilde{a}_n$. Observe that $\tilde{a}_n \leq \tau(\ca_n)$: we shall see that $\tilde{a}_n$ is an approximation to $\tau(\ca_n)$. Note that \[ \tilde{a}_n = \tau(\cc_{n}) \sum_{j=0}^{k} \frac{\tau(\cf_j)}{j!} \frac{(n)_j \tau(\cc_{n-j})}{\tau(\cc_{n})}; \] and so for each $n \geq n_1 +k$ we have %$\tilde{a}_n \leq (1+\eps) \lambda(\cc_n) \sum_{j=0}^{k} %\frac{\lambda(\cb_j) \rho^j}{j!}$ and %$\tilde{a}_n \geq (1-\eps) \lambda(\cc_n) \sum_{j=0}^{k} %\frac{\lambda(\cb_j) \rho^j}{j!}$. \[ (1-\eps) \tau(\cc_n) \sum_{j=0}^{k}\frac{\tau(\cf_j) \rho^j}{j!} \leq \tilde{a}_n \leq (1+\eps) \tau(\cc_n) \sum_{j=0}^{k}\frac{\tau(\cf_j) \rho^j}{j!}. \] We may now see that $F(\rho,\tau)$ is finite. For suppose not. Then for each $n \geq n_1 +k$ \[ \tau(\ca_n) \geq \tilde{a}_n \geq (1-\eps)(e^{\nu/\lambda}+2) \tau(\cc_n) \geq (e^{\nu/\lambda}+1) \tau(\cc_n). \] But since $\ca$ is bridge-addable, by Lemma~\ref{lem.tauconn} % Theorem 2.2 of~\cite{msw05} the probability that $R_n$ is connected is at least $e^{-\nu/\lambda}$, and we obtain the contradiction that \[ e^{\nu/\lambda} \cdot \tau(\cc_n) \geq \tau(\ca_n) \geq (e^{\nu/\lambda}+1) \cdot \tau(\cc_n). \] Hence $F(\rho,\tau)$ must be finite. From the above we have $\tilde{a}_n \leq (1+\eps) \tau(\cc_n) F(\rho,\tau)$, and $\tilde{a}_n \geq (1-\eps)^2 \tau(\cc_n) F(\rho,\tau)$. But \[ \tau(\ca_n) = \tilde{a}_n + \sum_{G} \{\tau(G) : G \in \ca_n, \frag(G)>k \mbox{ or } \Frag(G) \not\in \cf \}. \] Thus $\tau(\ca_n) \leq \tilde{a}_n + 2 \eps \, \tau(\ca_n)$, and so \[ \tau(\ca_n) \leq (1- 2\eps)^{-1} \tilde{a}_n \leq (1+ \eta) \tau(\cc_n) F(\rho,\tau); \] and \[ \tau(\ca_n) \geq \tilde{a}_n \geq (1-\eps)^2 \tau(\cc_n) F(\rho,\tau) \geq (1- \eta) \tau(\cc_n) F(\rho,\tau). \] So~(\ref{eqn.ctoa}) holds and we are done. \end{proofof} We need Lemma~\ref{lem.smoothconv} for graph classes which may not be decomposable (such as $\cg^S$) but let us note here an elegant general result for a decomposable class $\ca$ and the corresponding class $\cc$ of connected graphs: %, in the uniform case: by Corollary 4.3 of Bell and Burris~\cite{bb03}, if $(\cc, \tau)$ is smooth then so is $\cat$. %\m{ok for $\tau$? not for here but ask Kerstin?} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\m{not yet} %\begin{proofof}{Theorem~\ref{thm.smooth}} % We may now read the theorem off from Lemma~\ref{lem.smoothconn} % and Lemma~\ref{lem.smoothconv} with $\ca$ addable, since then $\Frag(R_n)$ is always in $\ca$, and each graph in $\ca$ is %freely addable to $\ca$. %\end{proofof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\newpage \subsection{Connected graphs and smoothness} \label{subsec.conn-smooth} Let us call a class $\ca$ of graphs {\em trimmable} if it satisfies $\; G \in \ca \Leftrightarrow \core(G) \in \ca$. (To tell if a graph is in such a class, it does not matter if we repeatedly trim off leaves.) Recall that by convention the empty graph is in $\ca$, so if $\ca$ is trimmable then $\ca$ contains every forest. Observe also that a minor-closed class of graphs is trimmable if and only if each excluded minor $H$ has minimum degree $\delta(H) \geq 2$. % Also, if $\ca$ is bridge-addable and monotone (that is, closed under forming subgraphs) then the class $\cc$ of connected graphs in $\ca$ is trimmable. %\m{The next two lemmas concern connected graphs, so we could set $\nu=1$ wlog} Suppose that a non-empty class $\cc$ of connected %\m{want connected?} graphs is trimmable. Then from what we saw about trees we have $\liminf_n \left( \tau(\cc_n)/n! \right)^{1/n} \geq \lambda e$. Let $\cb=\cc^{\delta \geq 2}$. Then $C(x,\tau)=B(\nu^{-1} T^o(x,\tau),\tau)$, where $C$, $B$ and $T^o$ are the exponential generating functions for $\cc$, $\cb$ and the rooted trees, respectively. %Now suppose that $\rho(\cc^{\delta \geq 2},\tau) \geq \lambda^{-1}$, and let Now if $0 \lambda_0$, % in which case we let $\gamma = \beta e^{\lambda_0/\beta}$ (which is $>\lambda_0 e$) % and let $\alpha=1- \lambda_0/\beta$; % or (b) $\cb, \tau$ has radius of convergence $\geq \lambda_0^{-1}$ % in which case we let $\gamma = \lambda_0 e$ and let $\alpha =0$. % % Then $\ca, \tau$ is smooth, with growth constant~$\gamma$. % Further, let $R^{\ca}_n \in_{\tau} \ca$: then for any $\eps>0$ %\[ \pr[|v(\core(R^{\ca}_n))- \alpha n| > \eps n] = e^{-\Omega(n)}. \] %\end{lemma} \begin{lemma} \label{lem.ctrim1} Let the non-empty class $\cc$ of connected graphs be trimmable, and let $\cb = \cc^{\delta \geq 2}$. %\{G \in \cc: \delta(G) \geq 2 \}$. %$\cc^{\delta\geq 2}$, %let $\lambda>0$, let $\nu=1$ and %let $\tau=(\lambda,1)$; %\m{do not need $\nu=1$?} Suppose that either (a) $(\cb, \tau)$ has growth constant $\beta$ and $\beta > \lambda$, %\m{$\beta>\lambda/\nu$?} %(where $0<\beta<\infty$) in which case we let $\gamma = \beta e^{\lambda/\beta}$ (which is $>\lambda e$) and let $\alpha=1- \lambda/\beta$; or (b) $(\cb, \tau)$ has radius of convergence $\geq \lambda^{-1}$ in which case we let $\gamma = \lambda e$ and let $\alpha =0$. %\m{was: we set $\beta=0$} %In case (a) %If $\beta>\lambda$ %let $\gamma = \beta e^{\lambda_0/\beta}$ (which is $>\lambda_0 e$), %$\lambda= \frac{e^{\rho}}{\rho}$ %and let $\gamma = \lambda_0 e$ otherwise. Then $(\cc, \tau)$ is smooth, with growth constant~$\gamma$. Further, %let $\alpha=1- \lambda_0/\beta$ if $\beta>\lambda_0$ and let $\alpha =0$ otherwise; and let let $R^{\cc}_n \in_{\tau} \cc$: then for any $\eps>0$ \[ \pr[|v(\core(R^{\cc}_n))- \alpha n| > \eps n] = e^{-\Omega(n)}. \] %where $\rho=1/\gamma$. \end{lemma} \begin{proof} %\begin{proofof}{Lemma~\ref{lem.ctrim1}} %\hspace{.1in} %Let $\cb = \cc^{\delta\geq 2}$. If $\cb$ is empty then $\cc$ is the class $\ct$ of all trees, and we saw in Section~\ref{sec.comps} above that $(\ct, \tau)$ is smooth with growth constant $\lambda e$ (and $\beta=0, \gamma= \lambda e$ and $\alpha =0$). %and the result follows easily from Cayley's formula %$|\cc_n| = n^{n-2}$: Thus we may assume that $\cb$ is non-empty. For $3 \leq k \leq n$ let %\[ f(n,k)= |\{G \in \cc_n:|\core(G)|=k \}|.\] \[ f(n,k)= \nu \sum \left\{ \lambda^{e(G)}: G \in \cc_n, v(\core(G))=k \right\}.\] Observe that $|\cc_1|=1$ if the one-vertex graph $K_1$ is in $\cc$, and $|\cc_1|=0$ otherwise. %It is convenient to work with $\rho=1/\beta$ when $\beta>0$. %Note that $\beta e^{1/\beta} = e^{\rho}/\rho$. % The main idea of the proof was inspired by~\cite{bcr08}, and goes as follows for case (a), when $(\cb,\tau)$ has growth constant $\gamma>\lambda e$. (We consider the case (b) later.) %Suppose in the meantime that $\beta>1$. We first show that \[ f(n,k) = (1+o(1))^n \ n! \ \gamma^n \] when $k = (\alpha +o(1)) n$, and the expression on the right side gives an asymptotic approximation for $\tau(\cc_n)$. Further, the dominant contribution in the sum \begin{equation} \label{eqn.csum} \tau(\cc_n) = \sum_{k=3}^{n} f(n,k) + |\cc_1| \ n^{n-2} \lambda^{n-1} \nu \end{equation} is from $k$ as above; for all such $k$ \[ \frac{f(n+1,k)}{(n+1) f(n,k)} \sim \gamma ; \] and this yields \[ \frac{\tau(\cc_{n+1})}{(n+1) \tau(\cc_n)} \sim \gamma.\] Now for the details. Let us not yet assume that $\cb$ has a growth constant (so that we can re-use the argument later). Recall that the number of forests on $[n]$ consisting of $k$ trees where vertices $1,\ldots,k$ are all in different trees is $kn^{n-1-k}$, see for example Theorem 3.3 of~\cite{moon70}. %Let $\cb$ denote the class of graphs $G \in \cc$ with $\delta(G) \geq 2$. Thus \begin{equation} \label{eqn.fnk} f(n,k) = \binom{n}{k} \ \tau(\cb_k) \ \lambda k(\lambda n)^{n-1-k}. \end{equation} Of course $f(n,n)= \tau(\cb_n)$. % We aim next to prove the three results (\ref{eqn.beta1}), (\ref{eqn.beta2}) and~(\ref{eqn.beta3}) below. %We suppose first that $\beta>0$ so that we can handle case (a), We first consider case (a), %consider first the case $\beta>0$, and then case (b) will follow easily. Suppose then that $\beta>0$. % and let $\rho=\lambda/\beta$. Let $r(n) = \frac{\tau(\cb_n)}{n! \beta^n}$ (so that we will have $r(n) = (1+o(1))^n$ below once we assume that $(\cb, \tau)$ has growth constant $\beta$). %(and $g(n) \leq 1$ for all $n$ if $\ca$ is addable). % %Also, if we let $\tilde{g}(n) = \max_{3 \leq k \leq n} g(k)$ then %$\tilde{g}(n) = (1+o(1))^n$. Let $s(n) = \frac{n^n}{n! e^n}$, so that by Stirling's formula $s(n) \sim (2 \pi n)^{-\frac12}$, and $s(n) \leq 1$ for all $n$. Then for $3 \leq k \leq n-1$, writing $\kappa = k/n$, \begin{eqnarray*} f(n,k) & = & n! \ \frac{\tau(\cb_k) }{k!} \ \frac{\lambda k}{\lambda n} \ \left(\frac{\lambda n}{n-k}\right)^{n-k} \ \frac{(n-k)^{n-k}}{(n-k)!}\\ & = & n! \ r(k) \ \beta^k \ \frac{k}{n} \left(\frac{\lambda e}{1-k/n}\right)^{n-k} s(n-k)\\ & = & n! \ \beta^n \ \left(\frac{\lambda e}{\beta(1-\kappa)}\right)^{(1-\kappa)n} \cdot \kappa \, r(k) \, s(n-k)\\ & = & n! \ \beta^{n} \ \left(h(1-\kappa)\right)^{n} \cdot \kappa \, r(k) \, s(n-k) \end{eqnarray*} where $h(x) = (\frac{\lambda e}{\beta x})^{x}$ for $x>0$ and $h(0) =1$. Thus (without yet assuming that $(\cb, \tau)$ has a growth constant) we have \begin{equation} \label{eqn.pregc} f(n,k) = n! \ \beta^{n} \left(h(1-\kappa)\right)^{n} \cdot \kappa \, r(k)\, s(n-k). \end{equation} Note that the function $h(x)$ strictly increases up to $x=\lambda/\beta$, where it has value $e^{\lambda/\beta}$, and strictly decreases above $\lambda/\beta$. Hence \[f(n,k) \leq \ n! \ \beta^{n} \left(e^{\lambda/\beta}\right)^{n} r(k)\] and recalling that $\gamma= \beta e^{\lambda/\beta}$ we have \begin{equation} \label{eqn.pregcbound} f(n,k) \leq n! \, \gamma^n r(k). \end{equation} (We will use this inequality in the proof of lemma~\ref{lem.ctrim2}.) Now assume that $(\cb, \tau)$ has growth constant $\beta$, so that $g(n) = (1+o(1))^n$ by the definition of the growth constant. %(and $g(n) \leq 1$ for all $n$ if $\cb$ is addable). % Then from~(\ref{eqn.pregc}), uniformly over $k$ with $3 \leq k \leq n$, still writing $\kappa = k/n$, we have \begin{equation} \label{eqn.pregcapprox} f(n,k) = (1+o(1))^n \ n! \ \beta^{n} \left(h(1-\kappa)\right)^{n}. \end{equation} %Note that the function $h(x)$ strictly increases up to $x=\lambda_0/\beta$, %where it has value $e^{\lambda_0/\beta}$, and strictly decreases above $\lambda_0/\beta$. % We need to consider two subcases. (i) Suppose first that $\beta>\lambda$, so $\gamma = \beta e^{\lambda/\beta}$ and $\alpha=1-\lambda/\beta$. Then it follows from~(\ref{eqn.csum}), (\ref{eqn.pregcapprox}) and the properties of $h$ that \begin{equation} \label{eqn.beta1} \tau(\cc_n) = (1+o(1))^n \ n! \ \gamma^n \end{equation} (the possible term $n^{n-2}\lambda^{n-1} \nu$ in the sum~(\ref{eqn.csum}) is negligible since $\gamma > \lambda e$), and for any $\delta>0$ there exists $\eta>0$ such that \begin{equation} \label{eqn.beta2} \sum_{k:|k-\alpha n| \geq \delta n} f(n,k) \leq (1-\eta +o(1))^n \ n! \ \gamma^n. \end{equation} Thus for any $\delta>0$ \begin{equation} \label{eqn.beta3} \frac{\tau(\cc_{n+1})}{(n+1) \tau(\cc_{n})} \sim \frac{\sum_{k:|k- \alpha n| < \delta n} f(n+1,k) }{\sum_{k:|k- \alpha n| < \delta n} (n+1) f(n,k)}. \end{equation} (ii) %\m{was: If $0< \beta \leq \lambda$} If $\beta = \lambda$ then $\gamma= \lambda e$ and $\alpha=0$, and the results~(\ref{eqn.beta1}), (\ref{eqn.beta2}) and~(\ref{eqn.beta3}) follow as above. \smallskip %\begin{equation} \label{eqn.beta1} % |\cc_n| = (1+o(1))^n \ n! \ e^n %\end{equation} %and for any $\delta>0$ there exists $\eta>0$ such that % \begin{equation} \label{eqn.beta2} % \sum_{k \geq \delta n} f(n,k) \leq (1-\eta +o(1))^n \ n! \ e^n; %\end{equation} %and thus for any $\delta>0$ %\begin{equation} \label{eqn.ratiob} % \frac{|\cc_{n+1}|}{(n+1)|\cc_n|} \sim % \frac{\sum_{k < \delta n} f(n+1,k) }{\sum_{k < \delta n} (n+1) f(n,k)}. %\end{equation} Finally consider the case $\rho(\cb,\tau) \geq \lambda^{-1}$. We shall see that we have exactly the same results~(\ref{eqn.beta1}), (\ref{eqn.beta2}) and~(\ref{eqn.beta3}) as for the case (ii). % $0< \beta \leq \lambda_0$. %Since $\cb \neq \emptyset$ it follows We know that $\tau(\cc_n) \geq (1+o(1))^n n! (\lambda e)^n$. Also, we may add connected graphs to $\cc$, maintaining trimmability, to form $\cc'$ so that if $\cb'$ denotes $\{G \in \cc':\delta(G) \geq 2\}$ then $(\cb', \tau)$ has growth constant $\lambda$. %$\beta'$ with $0< \beta' \leq \lambda_0$. Thus from (\ref{eqn.beta1}) and~(\ref{eqn.beta2}) for $\cc'$ and $\cb'$ we obtain the corresponding results for $\cc$ and $\cb$ in this case, and then we may deduce~(\ref{eqn.beta3}). We have now established (\ref{eqn.beta1}), (\ref{eqn.beta2}) and~(\ref{eqn.beta3}) for both cases (a) and (b). By equation~(\ref{eqn.fnk}), for each $k$ such that $3 \leq k \leq n$ and $\cb_k \neq \emptyset$, writing $k = \kappa n$ we have \[ \frac{f(n+1,k)}{(n+1)f(n,k)} = \frac{\lambda n}{n+1-k} \ (1+\frac1{n})^{n-k} = \frac{\lambda(1+\frac1{n})^{(1-\kappa)n}}{1+ \frac1{n} - \kappa}. \] % %Recall that $\alpha=1-\rho$ if $\beta>1$ and $\alpha=0$ otherwise. Now $\lambda \frac{e^{1-\alpha}}{1-\alpha} = \beta e^{\lambda/\beta}= \gamma$ if $\beta>\lambda$, and $\lambda \frac{e^{1-\alpha}}{1-\alpha} = \lambda e = \gamma$ if $\beta =\lambda$. %\m{was: $0 \leq \beta \leq \lambda_0$} Let $\eps>0$. By considering the two cases for $\beta$, we see that there exist $n_0$ and $\delta>0$ such that whenever $n \geq n_0$ and $|\kappa-\alpha| < \delta$ we have \[ (1-\eps) \gamma \leq \frac{\lambda (1+\frac1{n})^{(1-\kappa)n}}{1+ \frac1{n} - \kappa} \leq (1+\eps) \gamma. \] Hence by~(\ref{eqn.beta3}) we have \[ (1-\eps +o(1)) \gamma \leq \frac{\tau(\cc_{n+1})}{(n+1) \tau(\cc_n)} \leq (1+\eps +o(1)) \gamma.\] Thus \[ \frac{\tau(\cc_{n+1})}{(n+1) \tau(\cc_n)} \to \gamma \;\; \mbox{ as } n \to \infty\] as required. The last part of the lemma, concerning the size of the core, follows directly from~(\ref{eqn.beta1}) and~(\ref{eqn.beta2}). %\end{proofof} \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \medskip %The following two lemmas are very similar and may be proved in the same way. %\m{deleted partner lemma} %We prove the latter, and leave the proof of the former to the reader. %\begin{lemma} \label{lem.atrim2} \m{never used? if so then delete?} % %Let $\lambda>0$, $\nu=1$ and $\tau=(\lambda,\tau)$; % Let the class $\ca$ of graphs be trimmable, and % suppose that $\ca,\tau$ has growth constant $\gamma$; % and let $\cb = \ca^{\delta \geq 2}$. % \{ G \in \ca : \delta(G) \geq 2 \}$. %\m{new - ok?} % If $\gamma> \lambda_0 e$ and $\cb, \tau$ maintains at least factorial growth % then $\cb,\tau$ has growth constant $\beta$ where $\beta$ is the unique root $>\lambda_0$ of % $\ \beta e^{\lambda_0/\beta} = \gamma$. % If $\gamma \leq \lambda_0 e$ then $\rho(\cb,\tau) \geq \beta^{-1}$ where $\beta=\lambda_0$. %\end{lemma} \begin{lemma} \label{lem.ctrim2} %Let $\lambda>0$, $\nu=1$ and $\tau=(\lambda,\tau)$; Let the class $\cc$ of connected graphs be trimmable, and %\m{was: let $\tau=(\lambda,1)$ - not needed?} suppose that $(\cc,\tau)$ has growth constant $\gamma$; and let $\cb = \cc^{\delta \geq 2}$. %\{ G \in \cc : \delta(G) \geq 2 \}$. If $\gamma> \lambda e$ and $(\cb, \tau)$ maintains at least factorial growth then $(\cb,\tau)$ has growth constant $\beta$ where $\beta$ is the unique root $>\lambda$ of $\ \beta e^{\lambda/\beta} = \gamma$. If $\gamma \leq \lambda e$ then $\rho(\cb,\tau) \geq \beta^{-1}$ where $\beta=\lambda$. %$\rho(\cb,\tau) \geq \lambda_0^{-1}$. \end{lemma} \begin{proof} %\begin{proofof}{Lemma~\ref{lem.ctrim2}} %Note that $0<\lambda_0/\beta <1$. We prove first that $\limsup (\tau(\cb_n)/n!)^{1/n} \leq \beta$, by showing that otherwise equation~(\ref{eqn.pregc}) in the proof of the last result will yield $\limsup (\tau(\cc_n)/n!)^{1/n} > \gamma$. %For let $\eta>0$ and let $\delta>0$ satisfy $1+\delta < (1+ \eta)^{1-(\lambda_0/\beta)}$. %Let $t = \lambda/\beta$, so that $0\beta$. If $\tau(\cb_k) \geq k! \hat{\beta}^k$ and we let $n = \lceil\frac{k}{1-(\lambda/\hat{\beta})} \rceil$ then $h(1-k/n) \sim h(\lambda/\hat{\beta}) = e^{\lambda/\hat{\beta}}$, and so by %~(\ref{eqn.pregc}) equation~ (\ref{eqn.pregc}) we have %in the proof of the last result \[ \left(\frac{\tau(\cc_n)}{n!}\right)^{\frac{1}{n}} \geq \left(\frac{f(n,k)}{n!}\right)^{\frac{1}{n}} \geq (1+o(1)) \hat{\beta} e^{\lambda/\hat{\beta}}. \] But the function $f(x)=x \ln \lambda/x$ is strictly increasing for $x>\lambda$, so $\hat{\beta} e^{\lambda/\hat{\beta}} > \beta e^{\lambda/\beta} = \gamma$. Thus $\limsup (\tau(\cc_n)/n!)^{1/n} > \gamma$, which contradicts the assumption that $(\cc,\tau)$ has growth constant $\gamma$. For the case when $\gamma> \lambda e$ we also need a lower bound. %The lower bound needs a little more care. %It is easy to see from the proof of the last result that in fact %$\limsup (|\cb_n|/n!)^{1/n} = \beta$, for otherwise $|\cc_n|$ %would be too small for all sufficiently large $n$, but we need %more. % Let $0<\eps<1$. We want to show that for all sufficiently large $n$ we have \begin{equation} \label{eqn.claim1} \tau(\cb_n) \geq n! \ \beta^n (1-\eps)^{n}. \end{equation} We now use the assumption that $(\cb,\tau)$ maintains at least factorial growth (in the form in Lemma~\ref{lem.malfgnod}). Let $\delta'>0$, $\eta>0$ and $g(n)=(1+o(1))^n$ be such that for each $n$ and each $j$ with $1 \leq j \leq \delta' n$ we have \[ \tau(\cb_n) \geq \tau(\cb_{n-j}) \ (n)_j \ \eta^j \ g(n). \] % Let $0<\delta<\min\{\delta',1- (\lambda/\beta) \}$ be sufficiently small that %$\beta^{-\delta} \geq 1- \eps/3$ and $(\eta/\beta)^{\delta} \geq 1- \eps/3$. We claim that there is an $n_0$ such that for all $n \geq n_0$ %we have $n^{-2} \geq (1- \eta/3)^n$, and there is an $\tilde{n}$ with $|n-\tilde{n}| < \delta n$ such that \begin{equation} \label{eqn.tildan} \tau(\cb_{\tilde{n}}) \geq \tilde{n}! \ \beta^{\tilde{n}} (1- \eps/3)^{\tilde{n}}. \end{equation} The idea is that the proof of the last result, Lemma~\ref{lem.ctrim1}, shows that there must be such an $n_0$ since otherwise $\tau(\cc_n)$ would be too small for each large~$n$. For suppose there is no such~$n_0$. Then for arbitrarily large values of $k$, each $j$ with $|j-k| \leq \delta k$ has $\tau(\cb_j) < j! \beta^j (1- \eps/3)^j$; that is, $r(j) < (1- \eps/3)^j$, where $r(j) = \frac{\tau(\cb_j)}{j! \beta^j}$ as in the proof of the last lemma. Consider such a $k$, and let $n = \lceil\frac{k}{1-(\lambda/\beta)} \rceil$ as above. As we saw in~(\ref{eqn.beta2}) above, there is a constant $\eta>0$ such that \[ \sum_{j:|j-k| \geq \delta k} f(n,j) \leq n! \, \gamma^n \, (1-\eta +o(1))^n, \] %\left( \frac{e^{\rho}}{\rho} \right)^n,\] and now also by~(\ref{eqn.pregcbound}) \[ \sum_{j:|j-k| < \delta k} f(n,j) \leq n! \, \gamma^n \sum_{j:|j-k| < \delta k} r(j) \leq c \cdot n! \, \gamma^n (1-\eps/3)^{(1-(\lambda/\beta)-\delta)n}. \] %\left( \frac{e^{\rho}}{\rho} \right)^n.\] for a suitable constant $c$. Let $\eta'>0$ satisfy $\eta'<\eta$ and $1-\eta' > (1-\eps/3)^{1-(\lambda/\beta)-\delta}$. Then by~(\ref{eqn.csum}) and the above \[ \left(\frac{\tau(\cc_n)}{n!}\right)^{\frac{1}{n}} \leq (1-\eta') \ \gamma \] if $n$ is sufficiently large. This contradicts the assumption that $(\cc, \tau)$ has growth constant $\gamma$, and completes the proof of~(\ref{eqn.tildan}). % Indeed we can insist that there is a value $\tilde{n}$ as above with $\tilde{n} \leq n \leq (1+ \delta) \tilde{n}$. To see this we may apply to $n -\lfloor \delta n/2 \rfloor$ the current version of~(\ref{eqn.tildan}) with $\delta$ replaced by $\delta/2$. %Let us assume that $n_0$ is chosen large enough so that %for all $n \geq n_0$ we also have $n^{-2} \geq (1- \eps/3)^n$. % and $|\cb_n| \geq 2$. Let $n_1 \geq 2 n_0$ be such that $g(n) \geq (1-\eps/3)^n$ for all $n \geq n_1$. Let $n \geq n_1$. It will suffice for us to show that~(\ref{eqn.claim1}) holds for $n$. Let $j=n-\tilde{n}$. If $j=0$ there is nothing to prove so we may assume that $1 \leq j \leq \delta n$. Then \begin{eqnarray*} \tau(\cb_n) & \geq & \tau(\cb_{\tilde{n}}) \ (n)_j \ \eta^j \ g(n)\\ & \geq & n! \beta^n \beta^{-j} (1- \eps/3)^n \eta^j \ g(n)\\ & \geq & n! \beta^n (\eta/\beta)^{j} (1- \eps/3)^{2n}\\ & \geq & n! \beta^n (1- \eps/3)^{3n} \; \geq \; n! \beta^n (1- \eps)^n, \end{eqnarray*} as required. % % Pick a set $S$ of $j$ vertices %from $[n]$, and list them as $v_1,v_2,\ldots,v_j$. %% ($(n)_j$ choices). %Pick a graph $G$ in $\cb_{\tilde{n}}$ %with at least one edge %on $[n]\setminus S$. % ($|\cb_{\tilde{n}}|$ choices). %Pick an edge $uw$ in $G$, where $u \lambda e$ then, since $\cc$ is trimmable, by Lemma~\ref{lem.ctrim2} $(\cb,\tau)$ has growth constant $\beta$. If $\gamma \leq \lambda e$ then $\rho(\cb,\tau) \geq \lambda^{-1}$. But now (without restriction on $\gamma$) Lemma~\ref{lem.ctrim1} shows that $(\cc,\tau)$ is smooth, and further shows that, for $R^{\cc}_n \in_{\tau} \cc$, we have for any $\eps>0$ that \begin{equation} \label{eqn.cc-core} \pr(|v(\core(R^{\cc}_n))-\alpha n| > \eps n) = e^{-\Omega(n)}. \end{equation} %and proves part 3. Also, for $R_n^{\ca} \in_{\tau} \ca$, $\pr(\Frag(R_n^{\ca}) \in \cf_{\ca}) = 1-o(1)$ by Lemma~\ref{lem.Frag}. %Since $\cc$ is smooth We may now use Lemma~\ref{lem.smoothconv} to show that $\cat$ is smooth. At this point we have proved~(\ref{eqn.cc-core}) and parts (a) and (b) of Theorem~\ref{thm.sumup}. %Next we consider part 5. Since $\frag(\core(G)) \leq \frag(G)$ for any graph $G$, this part %follows from Lemma 2.5 of~\cite{cmcd09} (see also Lemma 2.6 of that paper). Next we prove part (c). %\m{deleted: Write $\alpha$ for $1- \lambda_0/\beta$} % \m{now exponential tail?} Observe that conditional on $\bigc(R_n^{\ca})=n'$ the distribution of $\Bigc(R_n^{\ca})$ is the same as that of $R_{n'}^{\cc}$. Thus for each $j 0$. Let $\omega=\omega(n) = \lfloor \eps n/2 \rfloor$. Then $\pr(v(\core(R_{n}^{\ca})) \geq (\alpha\!+\!\eps)n)$ is at most %\begin{eqnarray*} % &&\pr(v(\core(R_{n}^{\ca})) \geq (\alpha +\eps)n)\\ % & \leq & \[ \pr(( v(\core(R_{n}^{\ca})) \geq (\alpha\!+\!\eps)n) \cap (\frag(R_{n}^{\ca}) \leq \omega)) + \pr(\frag(R_{n}^{\ca}) > \omega).\] %\end{eqnarray*} By Lemma~\ref{lem.tauconn} (b) % %2.5 of~\cite{cmcd09} (as we already noted) we know that the second term $\pr(\frag(R_{n}^{\ca}) > \omega)$ is $o(1)$. But the first term equals \begin{eqnarray*} && \sum_{j=0}^{\omega} \pr\left( (v(\core(R_{n}^{\ca})) \geq (\alpha\!+\!\eps)n) \cap ( \frag(R_{n}^{\ca} ) =j) \right)\\ & \leq & \sum_{j=0}^{\omega} \pr\left( v(\core(R_{n-j}^{\cc})) \geq (\alpha\!+\!\eps)n -j\right) \;\; = e^{-\Omega(n)}. \end{eqnarray*} Thus \[ \pr(v(\core(R_{n}^{\ca})) \geq (\alpha\!+\!\eps)n) = o(1). \] Similarly \begin{eqnarray*} &&\pr(v(\core(R_{n}^{\ca})) \leq (\alpha\!-\!\eps)n)\\ & \leq & \sum_{j=0}^{\omega} \pr\left( v(\core(R_{n-j}^{\cc})) \leq (\alpha\!-\!\eps)n \right) + \pr(\frag(R_{n}^{\ca}) > \omega) \;\; = \; o(1). \end{eqnarray*} Now consider the remaining part of the theorem, part (d), and assume that $\gamma>\lambda e$. Note first that is it very unlikely that $\core(R_n)$ is empty; for this happens (if and) only if $R_n$ is a forest, and the probability of this happening is $(\lambda e /\gamma +\!o(1))^n = e^{-\Omega(n)}$. Also, the probability that $\Bigc(R_n)$ is a tree is $e^{-\Omega(n)}$. For \begin{eqnarray*} && \pr(\Bigc(R_n) \mbox{ is a tree and } \bigc(R_n) \geq \frac23 n)\\ & \leq & \sum_{\frac23 n \leq a \leq n} \binom{n}{a} \frac{\tau(\ct_a) \cdot \tau(\ca_{n-a})}{\tau(\ca_n)} = \sum_{\frac23 n \leq a \leq n} \frac{ \frac{\tau(\ct_a)}{a!} \cdot \frac{\tau(\ca_{n-a})}{(n-a)!} } {\frac{\tau(\ca_n)}{n!} }\\ &=& (1+o(1))^n \sum_{\frac23 n \leq a \leq n} \frac{ (\lambda e)^a \gamma^{n-a} }{\gamma^n} = (1+o(1))^n (\lambda e / \gamma)^{\frac23 n} = e^{-\Omega(n)}. \end{eqnarray*} But if $\core(R_n)$ is non-empty and $\Bigc(R_n)$ is not a tree, then $\core(R_n)$ is connected if and only if $\Frag(R_n)$ is acyclic. Thus \[ | \pr(\core(R_n) \mbox{ connected (and $\neq \emptyset$)})- \pr(\Frag(R_n) \mbox{ acyclic})| = e^{-\Omega(n)}.\] Finally, the probability that $\Frag(R^{\ca}_n)$ has no non-tree components tends to $e^{-(D(\rho,\tau) - T(\rho,\tau))}$ by Corollary~\ref{cor.comps} (b) applied to $\cd \setminus \ct$. %note that $\Bigc(R^{\ca}_n)$ is very unlikely to be a tree; and if %$\Bigc(R^{\ca}_n)$ is not a tree then $\core(R^{\ca}_n)$ is connected if and only if %$\Frag(R^{\ca}_n)$ has no non-tree components. Now this part %will follow directly from Corollary~\ref{cor.comps} (b) applied to %$\cd \setminus \ct$. %Lemma 4.3 of~\cite{cmcd09} (see also Lemma 4.4 of that paper). %\end{proofof} %\bigskip %\m{move these points?} % Note that if $\ca$ is addable and minor-closed, and not just the class $\cf$ of forests, then % $\ca$ contains $\ex(C_4)$ which has growth constant $\gamma \approx 3.63 > e$ (see~\cite{bnw09}). % \m{? and so $\ca, \tau$ has growth constant $ > e \lambda_0$?} % \m{was: and so $\ca$ has growth constant $\gamma \lambda_0 > e \lambda_0$ - NO} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Poisson convergence} \label{sec.poisson-conv} Let $\tau=(\lambda, \nu)$ and $\rho>0$ be given. As in~(\ref{eqn.mudef}), we use the notation \[ \mu(H)=\rho^{v(H)} \lambda^{e(H)} \nu^{\kappa(H)}/\aut(H) \;\;\; \mbox{ for each graph } H . \] %\m{(deleted: where $\lambda^{e(H)}$ denotes $\lambda_0^{e_0(H)} \lambda_1^{e_1(H)}$)} %and $A(z)$ for the exponential generating function of $\ca$ and so on. Also, let $r_n=n \tau(\ca_{n-1})/\tau(\ca_n)$, and assume that $\ca_n \neq \emptyset$ when necessary. Further, recall the notation $(n)_k = n(n-1) \cdots (n-k+1)$. The following lemma is a slight extension %of Lemma 5.1 of McDiarmid~\cite{cmcd06}, for example of Lemma 4.1 of~\cite{cmcd09}. It will be a key result for taking advantage of smoothness. %(see also Lemma 5.3 of~\cite{msw05} and its %proof, and the discussion in the last section %of~\cite{msw06}). Given a graph $G$ and a connected graph $H$ we let $\kappa(G,H)$ be the number of components of $G$ isomorphic to $H$. % \begin{lemma} \label{lem.pconv1} Let $\ca$ be any class of graphs, and let $\tau$ % $\lambda>0$, $\nu>0$, $\tau=(\lambda, \nu)$ and $\rho>0$ be given. Let $H_{1}, \ldots, H_{h}$ be pairwise non-isomorphic connected graphs, each freely addable to $\ca$. Let $k_{1}, \ldots, k_{h}$ be non-negative integers, and let $K = \sum_{i = 1}^{h} k_{i} v(H_i)$. Then for $R_{n} \in_{\tau} \ca$ \[\E\left[\prod_{i=1}^h \left( \kappa(R_n,H_i) \right)_{k_{i}}\right] = \prod_{i=1}^h \mu(H_i)^{k_i} \cdot \prod_{j=1}^{K} (r_{n-j+1}/\rho).\] \end{lemma} \begin{proof} %Let $v_i=v(H_i)$ and $e_i=e(H_i)$ for each $i=1,\ldots,h$. %%\m{Let $v^*= \max_iv_i$} We may construct a graph $G$ in $\mathcal{A}_{n}$ with $\kappa(G,H_i) \geq k_i$ for each $i$ %at least $k_{i}$ components isomorphic to $H_{i}$ as follows: choose a list of $K$ vertices; put a copy of $H_1$ on the first $v(H_1)$ vertices in the list, if $k_1>1$ put another copy of $H_1$ on the next $v(H_1)$ vertices, and so on until we put a copy of $H_h$ on the last $v(H_h)$ vertices in the list; and finally put any graph of order $n-K$ in $\ca$ on the remaining $n-K$ vertices. % choose the vertex sets of the different components %one after another, then insert appropriate copies of $H_{i}$ %on the vertices of each component; %and finally put any graph of order $n-K$ in $\ca$ %on the remaining $n-K$ vertices. % The sum over all such constructions of the weight $\lambda^{e(G)} \nu^{\kappa(G)}$ of the graph $G$ constructed is %\[ \prod_{i=1}^{h} \prod_{j=1}^{k_i} % \left({{n - \sum_{s=1}^{i-1}k_{s}v_{s} - % (j-1)v_{i}}\choose{v_{i}}} % {\frac{v_{i}!}{aut(H_i)}} \lambda^{e_i} \right) % \cdot \lambda(\ca_{n-K})\] \[ (n)_K \prod_{i=1}^{h}\left( \aut(H_i)^{-1} \lambda^{e(H_i)} \nu \right)^{k_i} \cdot \tau(\ca_{n-K}). \] %How often is a specific $G \in \mathcal{A}_{n}$ constructed? %This depends on the number of components of $G$ that are isomorphic %to some $H_{i}$. %If $G$ contains exactly $t_{i}$ components isomorphic to $H_{i}$ for each $i$, Now observe that each graph $G \in \ca_n$ is constructed $\prod_{i = 1}^{h}(\kappa(G,H_{i}))_{k_i}$ times (exactly); and so the above expression equals %\begin{equation} \label{eqn.sumcount} \[ \sum_{G \in \ca_n} \prod_{i=1}^h (\kappa(G,H_i))_{k_{i}} \lambda^{e(G)} \nu^{\kappa(G)}.\] %\end{equation} But by definition $\E\left[\prod_{i=1}^m (\kappa(R_{n},H_i))_{k_{i}}\right]$ is $\tau(\ca_n)^{-1}$ times this last quantity. %in~(\ref{eqn.sumcount}). Hence \begin{eqnarray*} \E\left[\prod_{i=1}^m (\kappa(R_{n},H_i))_{k_{i}}\right] &=& (n)_K \prod_{i=1}^{h}\left( \aut(H_i)^{-1} \lambda^{e(H_i)} \nu \right)^{k_i} \cdot \tau(\ca_{n-K})/\tau(\ca_n)\\ &=& \prod_{i=1}^{h} \mu(H_i)^{k_i} \cdot \prod_{j=1}^K \left(\rho^{-1} (n-j+1) \frac{\tau(\ca_{n-j})}{\tau(\ca_{n-j+1})}\right)\\ &=& \prod_{i=1}^{h} \mu(H_i)^{k_i} \cdot \prod_{j=1}^K (r_{n-j+1}/\rho) \end{eqnarray*} as required. % \end{proof} \bigskip \noindent When we add the assumption that $\cat$ is smooth, we find convergence of distributions. % Consider the three-variable generating function %\[ % A(x,y,z)= \sum_{G \in \ca} \frac{x^{v(G)}}{n!} y^{e(G)} z^{(\kappa(G)} = % \sum_{n \geq 0} \frac{x^n}{n!} \sum_{G \in \ca_n} y^{e(G)} z^{(\kappa(G)}. %\] % We write $A(x,\tau)$ for $A(x,\lambda,\nu)$. Recall that $\rho(\ca,\tau)$ denotes the radius of convergence of $A(x,\tau)$ as a power series in~$x$. %Let $\rho(\ca,\tau)$ denote the radius of convergence of $A(x,\tau)$ %as a power series in~$x$, where $A$ is as given in Section~\ref{subsec.boltzmann}. \m{move earlier?} %If $\ca,\tau$ has a growth constant, say $\gamma$, %then $\rho(\ca,\tau)=1/\gamma$. \begin{lemma} \label{lem.conv2} Let the weighted graph class $\cat$ be smooth, and let $\rho = \rho({\ca, \tau})$. Let $H_1,\ldots,H_h$ be a fixed family of pairwise non-isomorphic connected graphs, each freely addable to $\ca$. Then as $n \to \infty$ the joint distribution of the random variables $\kappa(R_n,H_1)$, $\ldots,$ $\kappa(R_n,H_h)$ converges in total variation to the product distribution $\Po(\mu(H_1)) \otimes \cdots \otimes \Po(\mu(H_h))$. %Thus in particular for each graph $H$ %\[ \Pr[R_n \mbox{ has no component isomorphic to $H$}] \;\to\; %e^{-\lambda(H)} \;\;\; \mbox{as} \; n \to \infty. \] %Further, we also have convergence for all moments; that is, %for each positive integer $j$ we have %$\E[X_n(H)^j] \to \lambda(H)^j$ as $n \to \infty$. \end{lemma} \begin{proof} Since $r_n \to \rho$ as $n \to \infty$, by the last lemma \[ \E\left[\prod_{i=1}^h \left(\kappa(R_n,H_i) \right)_{k_{i}}\right] \to \prod_{i=1}^{h} \mu(H_i)^{k_i} \] as $n \to \infty$, for all non-negative integers $k_1,\ldots,k_h$. A standard result on the Poisson distribution now shows that the joint distribution of the random variables $\kappa(R_n,H_1),\ldots,\kappa(R_n,H_h)$ tends to that of independent random variables $\Po(\tau(H_1)),\ldots, \Po(\tau(H_h))$, see for example Theorem~6.10 of %Lemma 5.4 of McDiarmid, Steger and Welsh~\cite{msw05} or see Janson, {\L}uczak and Ruci{\'n}ski~\cite{jlr00}. Thus for each $h$-tuple of non-negative integers $(t_1,\ldots,t_h)$ \[ \pr[\kappa(R_n,H_i)=t_i \; \forall i] \to \prod_i \pr[\kappa(R_n,H_i)=t_i] \;\; \mbox{ as } n \to \infty; \] and so we have pointwise convergence of probabilities, which is equivalent to convergence in total variation. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{$\Frag(R_n)$ and connectivity} \label{sec.frag-conn} The following lemma parallels Lemma~\ref{lem.smoothconv}, which showed that, under suitable conditions, if the weighted class $(\cc,\tau)$ of connected graphs in $\ca$ is smooth then $\cat$ is smooth. The lemma below shows the converse result that if $\cat$ is smooth then, for $R_n \in_{\tau} \ca$ the probability that $R_n$ is connected tends to a limit, and so $(\cc,\tau)$ is smooth. % \begin{lemma} \label{lem.stillgen1} Let the graph class $\ca$ be bridge-addable; let $\rho = \rho({\ca,\tau})$; let $\cf_{\ca}$ denote the class of graphs freely addable to~$\ca$; and suppose that, for $R_n \in_{\tau} \ca$, \whp $\Frag(R_n) \in \cf_{\ca}$. Let $\cc$ and $\cd$ be the classes of connected graphs in $\ca$ and $\cf_{\ca}$ respectively, and let $F_{\ca}$ denote the exponential generating function of $\cf_{\ca}$. Suppose that $\cat$ is smooth. Then $F_{\ca}(\rho,\tau)$ and $D(\rho,\tau)$ are finite; $\kappa(R_n) \to_{TV} 1+ \Po(D(\rho,\tau))$; and in particular \[ \Pr[R_n\mbox{ is connected }] \;\to\; e^{-D(\rho,\tau)} = 1/F_{\ca}(\rho,\tau) \;\; \mbox{ as } n \to \infty, \] and so $(\cc,\tau)$ is smooth. \end{lemma} \begin{proof} We follow the method of proof of Lemma 4.3 of~\cite{cmcd09}. %Theorem 3.2 of McDiarmid~\cite{cmcd06}. We first show that $D(\rho,\tau)$ is finite. By Lemma~\ref{lem.tauconn} (b) we may choose a (fixed) $k$ sufficiently large that $\pr[\frag(R_n) \geq k] \leq \frac13$ for all $n$, and $\pr[\Po(2k) \geq k] \geq \frac23$. Suppose that $D(\rho,\tau) \geq 2k+1$. Then by~(\ref{eqn.Agen}) there are distinct $H_1,\ldots,H_m$ in $\cu \cd$ such that $\sum_{i=1}^{m} \mu(H_i) = \mu_0 \geq 2k$. It follows by Lemma~\ref{lem.conv2} that, for $n>k \max_{i} v(H_i)$ \[ \frac13 \geq \pr[\frag(R_n) \geq k] \geq \pr[\sum_{i=1}^{m} \kappa(R_n,H_i) \geq k] \to \pr[\Po(\mu_0) \geq k] \geq \frac23 \] as $n \to \infty$, a contradiction. Hence $D(\rho,\tau)$ is finite, and so $F_{\ca}(\rho,\tau)$ is finite too. Now let $\mu = D(\rho,\tau)$. Let $k$ be a fixed positive integer and let $\eps >0$. We want to show that for $n$ sufficiently large we have \begin{equation} \label{eqn.poisson1} |\pr[\kappa(\Frag(R_n))=k] - \pr[\Po(\mu)=k]| < \eps. \end{equation} % By our assumptions, there is an $n_0$ such that for each $n \geq n_0$ \begin{equation} \label{eqn.k1} \pr[\frag(R_n) > n_0] + \pr[ \Frag(R_n) \not\in \cf_{\ca} ] < \eps/3. \end{equation} List the graphs in ${\cal U} \cd$ in non-decreasing order of the number of vertices as $H_1,H_2,\ldots$. For each positive integer $m$ let $\mu^{(m)} = \sum_{i=1}^{m} \mu(H_i)$. % Note that $D(\rho,\tau)= \sum_{H \in \cu \cd} \mu(H)$ by~(\ref{eqn.Agen}) applied to $\cd$. Thus we may choose $n_1 \geq n_0$ such that, if $m$ is the largest index such that $v(H_m) \leq n_1$, then \begin{equation} \label{eqn.k2} |\pr[\Po(\mu)=k] - \pr[\Po(\mu^{(m)})=k]| < \eps /3. \end{equation} % Observe that for any graph $G$ with more than $2n_1$ vertices, if $\frag(G) \leq n_0$ and $\Frag(G) \in \cf_{\ca}$, then $\kappa(\Frag(G))$ is the number of components of $G$ isomorphic to one of $H_1,\ldots,H_m$ (that is, with order at most $n_1$). Let $X_n$ denote the number of components of $R_n$ isomorphic to one of $H_1,\ldots,H_m$. Let $n > 2n_1$. Then \begin{equation} \label{eqn.k5} |\pr[\kappa(\Frag(R_n))\!=\!k]\!-\!\pr[X_n\!=\!k]| \leq \pr[\frag(R_n)\!>\!n_0] + \pr[\Frag(R_n)\!\not\in\!\cf_{\ca}] < \eps /3. \end{equation} But by Lemma~\ref{lem.conv2}, for $n$ sufficiently large, \[ |\pr[X_n=k] - \pr[\Po(\mu^{(m)})=k]| < \eps/3,\] and then by~(\ref{eqn.k2}) and~(\ref{eqn.k5}) the inequality~(\ref{eqn.poisson1}) follows. Thus we have shown that $\kappa(R_n) \to_{TV} 1+ \Po(D(\rho,\tau))$, and in particular \begin{equation} \label{eqn.conn0} \tau(\cc_n)/\tau(\ca_n) = \pr(R_n \mbox{ is connected }) \to e^{-D(\rho,\tau)} \mbox{ as } n \to \infty. \end{equation} Finally observe that since $\cat$ is smooth, and $\tau(\cc_n)/\tau(\ca_n)$ tends to a non-zero limit as $ n \to \infty$ (namely $e^{-D(\rho,\tau)}$), it follows that $(\cc,\tau)$ is smooth. \end{proof} \medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent The next lemma has similar premises to %Lemma~\ref{lem.smoothconv} and Lemma~\ref{lem.stillgen1}, and obtains further conclusions. We use the same notation. \begin{lemma} \label{lem.stillgen2} Let $\ca$ be %minor closed and bridge-addable; let $\rho = \rho({\ca,\tau})$, %\m{replace minor closed and bridge-addable by has tight fragments?} %let $\cf$ be the class $\cf(\ca)$ of graphs freely addable to $\ca$; and suppose that $\Frag(R_n) \in \cf_{\ca}$ \whp where $R_n \in_{\tau} \ca$. Let $\cc$ be the class of connected graphs in $\ca$. % Assume that either $\cat$ or $(\cc,\tau)$ is smooth. Then both $\cat$ and $(\cc,\tau)$ are smooth; % with ratio limit $\rho$; $F_{\ca}(\rho,\tau)$ is finite; and the unlabelled graph $F_n$ corresponding to $\Frag(R_n)$ satisfies $F_n \to_{TV} F$, where \[ \pr[F=H] = \frac{\mu(H)}{F_{\ca}(\rho,\tau)} \;\; \mbox{ for each } H \in \cu \cf_{\ca}. \] \end{lemma} \begin{proof} Lemmas~\ref{lem.smoothconv} and~\ref{lem.stillgen1} show that both $\cat$ and $(\cc,\tau)$ are smooth, and that $F_{\ca}(\rho,\tau)$ is finite. Let $a_n = \tau(\ca_n)$ and $c_n =\tau(\cc_n)$. Let $\cd$ be the class of connected graphs in $\cf_{\ca}$. By Lemma~\ref{lem.stillgen1} \begin{equation} \label{eqn.conn} c_n/a_n \to e^{-D(\rho,\tau)} = 1/F_{\ca}(\rho,\tau) \mbox{ as } n \to \infty. \end{equation} % Given a graph $G$ on a finite subset $V$ of the positive integers let $\phi(G)$ be the natural copy of $G$ moved down on to $\{1,\ldots,|V|\}$; that is, let $\phi(G)$ be the graph on $\{1,\ldots,|V|\}$ such that the increasing bijection between $V$ and $\{1,\ldots,|V|\}$ is an isomorphism between $G$ and $\phi(G)$. Let $H$ be any graph in $\cb$ on $[h]$. Then \begin{eqnarray*} \pr[\phi(\Frag(R_n))=H] & = & \binom{n}{h} \ \frac{c_{n-h}}{a_n} \;\; = \;\; \frac{c_{n-h}}{a_{n-h}} \ \frac{1}{h!} \ \frac{(n)_h a_{n-h}}{a_n}\\ & = & \frac{c_{n-h}}{a_{n-h}} \ \frac{1}{h!} \ \prod_{i=0}^{h-1} r_{n-i} \;\; \to \;\; e^{-D(\rho,\tau)} \frac{\rho^h}{h!} \end{eqnarray*} %\begin{eqnarray*} % \pr[\phi(\Frag(R_n))=H] & = & {n \choose h} \ \frac{c_{n-h}}{a_n}\\ % & = & \frac{c_{n-h}}{a_{n-h}} \ \frac{1}{h!} \ \frac{(n)_h a_{n-h}}{a_n}\\ % & = & \frac{c_{n-h}}{a_{n-h}} \ \frac{1}{h!} \ \prod_{i=0}^{h-1} r_{n-i}\\ % & \to & e^{-D(\rho,\tau)} \frac{\rho^h}{h!} %\end{eqnarray*} as $n \to \infty$ by~(\ref{eqn.conn}) and the fact that $\cat$ is smooth. Now by symmetry \[ \pr [F_n \cong H ] = \frac{h!}{\aut(H)} \ \pr[\phi(\Frag(R_n))= H]\] and hence as $n \to \infty$ \[\pr[F_n \cong H] \to e^{-D(\rho,\tau)} \frac{\rho^h}{\aut(H)} = \Pr(F \cong H).\] Thus for each $H \in \cu \cb$, as $n \to \infty$ we have $\pr[F_n = H] \to \pr(F=H)$; that is, $F_n \to_{TV} U$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bigskip We need one last lemma to complete the proof of Theorem~\ref{thm.Frag}. \begin{lemma} \label{lem.mc2} Let the weighted graph class $\cat$ be well-behaved; %let $\cf$ be the class $\cf(\ca)$ of graphs freely addable to $\ca$; let $\cd$ be the class of connected graphs in $\cf_{\ca}$, with generating function $D$; and let $\rho = \rho({\ca,\tau})$. Then %$A'(\rho,\tau)$ and $D'(\rho,\tau)$ is finite (where we are differentiating with respect to the first variable). \end{lemma} \begin{proof} Note that $0<\rho<\infty$. %By the exponential formula %$A(x)=e^{C(x)}$, %it suffices to show that $C'(\rho,\tau)$ is finite. By Lemma~\ref{lem.tauconn} (b), %there is a constant $c$ such that $\E[\frag(R_n)] \leq c $ for all~$n$ where $c=2\nu/\lambda$. %(We write $c$ rather than $c \nu/\lambda_0$ here.) Suppose that $D'(\rho,\tau) \geq (c+3)/\rho$. Then by~(\ref{eqn.Agen}) applied to $\cd$, there are distinct $H_1,\ldots,H_m$ in $\cu \cd$ such that $\sum_{i=1}^{m} v(H_i) \ \mu(H_i) = \alpha \geq c+2$. Let $n_0 = \max_i v(H_i)$. Then \[ \E[\frag(R_n)] \geq \E\left[ \sum_{i=1}^{m} v(H_i)\ \kappa(R_n,H_i)\right] - n_0 \pr[\bigc(R_n) \leq n_0]. \] Now $\cat$ is smooth by Theorem~\ref{thm.sumup} (a). Thus as $n \to \infty$ \[ \E\left[ \sum_{i=1}^{m} v(H_i) \kappa(R_n,H_i)\right] \to \alpha \] by Lemma~\ref{lem.conv2}, and by Lemma~\ref{lem.tauconn} %Theorem 2.2 of McDiarmid, Steger and Welsh~\cite{msw05} \[ \pr[\bigc(R_n) \leq n_0] \leq \pr[\kappa(R_n) \geq n/n_0] \leq \pr[\Po(\frac{\nu}{\lambda}) \geq n/n_0 -1] = o(1). \] Hence %\m{was $\alpha -1$?} $\E[\frag(R_n)] \geq \alpha -o(1) \geq c+1$ for $n$ sufficiently large, contradicting our choice of $c$. \end{proof} \bigskip \begin{proofof}{Theorem~\ref{thm.Frag}} By Lemma~\ref{lem.Frag}, \whp $\Frag(R_n) \in \cf_{\ca}$. Hence by Lemma~\ref{lem.stillgen2}, $\cat$ and $(\cc,\tau)$ are smooth (this also follows from Theorem~\ref{thm.sumup} (a)) and $F_n \to_{TV} R$ as required. Finally note that $\E[v(F)]$ is $\rho \, D'(\rho,\tau)$, which is finite by the last lemma. % %We may deduce the theorem from Lemma~\ref{lem.Frag}, Theorem~\ref{thm.sumup} (a) %and Lemma~\ref{lem.stillgen2}, on noting that \m{amplify?} %$v(F)$ has mean $\rho \ D'(\rho,\tau)$ which is finite by the last lemma. \end{proofof} \bigskip \begin{proofof}{Corollary \ref{cor.comps}} The only thing that does not follow directly from the fact that $F_n \to_{TV} F$ is the convergence of the moments in part (b) (which yields the results on moments in part~(c)). But $0 \leq \kappa(F_n,\cd) \leq \kappa(R_n) -1 \leq \Po(\frac{\nu}{\lambda})$ in distribution by Lemma~\ref{lem.tauconn}, %Theorem 2.2 of McDiarmid, Steger and Welsh~\cite{msw05}, and so convergence for the $j$th moment follows from convergence in total variation. \end{proofof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of appearances results} \label{sec.apps-proofs} Theorem~\ref{thm.appearances1} and Proposition~\ref{thm.apps2} may be proved along the lines of the corresponding proofs in~\cite{cmcd08}, but for completeness we give proofs here. \medskip %\m{also see max degree paper~\cite{cb08}} \begin{proofof}{Theorem~\ref{thm.appearances1}} Let $\alpha = \lambda^{e(H)+1}/(2e^2 \gamma^h (h+2)h!)$. We shall prove that there exists $n_0$ such that \begin{equation} \label{eqna} \Pr[f_H(R_n) \leq \alpha n] < e^{-\alpha n} \;\;\; \mbox{ for all } \; n \geq n_0. \end{equation} %To do this we adapt the proof of Theorem 4.1 in~\cite{msw05}. We often write $x$ instead of $\lfloor x \rfloor$ or $\lceil x \rceil$ to avoid cluttering up formulae: this should cause the reader no problems. %Let $\beta = e^2 c^h (h+2) h!$. Observe that the bound on $\alpha$ %implies that $\alpha\beta<1$ and Since $\alpha>0$, $2^{\alpha} \geq (1+ \eps)^4$ for some $0<\eps< \frac12$. Note that \begin{equation}\label{eq:num-pg-true2} (1-\eps)(1+\eps)^2>1. \end{equation} Let $g(n)$ denote $\tau(\ca_n)$. Since $\cat$ has growth constant~$\gamma$, there is a positive integer $n_0$ such that for each $n \geq n_0$ we have \begin{equation}\label{eq:num-pg-true3} (1-\eps)^n \cdot n! \ \gamma^n \le g(n) \le (1+\eps)^n \cdot n! \ \gamma^n. \end{equation} %Let $\delta = \alpha h$ and note that $\delta \leq 1$. Let $\cb$ denote the class of graphs in $\ca$ such that $f_H(G) \leq \alpha \ v(G)$. Assume that equation~(\ref{eqna}) does not hold for some $n\ge n_0$; that is, assume that $\tau(\cb_n) \geq e^{-\alpha n} g(n)$. Let $\delta = \alpha h$. We shall show that \[ g((1+\delta)n) > (1+\eps)^{(1+\delta)n} \cdot [(1+\delta)n]! \cdot \gamma^{(1+\delta)n}, \] which will contradict~(\ref{eq:num-pg-true3}) and complete the proof of the theorem. In order to establish this inequality, we construct graphs $G'$ in $\ca$ on vertex set $\{1,\ldots,(1+\delta)n\}$ as follows. First we choose a subset of $\delta n$ special vertices ($\binom{(1+\delta)n}{\delta n}$ choices) and a graph $G \in \cb$ on the remaining $n$ vertices. By assumption \[ \tau(\cb_n) \geq e^{-\alpha n}\cdot g(n) \ge e^{-\alpha n} (1-\eps)^n \gamma^n n!. \] % Next we consider the $\delta n$ special vertices. We partition them into $\alpha n$ (unordered) blocks of size $h$. On each block $B$ we put a copy of $H$ such that the increasing bijection from $\{1,\ldots,h\}$ to $B$ is an isomorphism between $H$ and this copy. Call the lowest numbered vertex in $B$ the {\em root} $r_B$ of the block. For each block $B$ we choose a non-special vertex $v_B$ and add the edge $r_B v_B$ between the root and this vertex: observe that $H$ appears at $B$ in $G'$. This completes the construction of $G'$: note that $G \in \ca$ since $H$ is freely attachable to $\ca$. For each choice of special vertices, %and each $G \in \ca$ on the remaining $n$ vertices, the weight of constructions is \begin{eqnarray*} && \tau(\cb_n) \cdot \binom{\delta n}{ h \cdots h} \cdot \frac{1}{(\alpha n)!} \cdot n^{\alpha n} (\lambda \lambda^{e(H)})^{\alpha n}\\ & = & \tau(\cb_n) \cdot \frac{(\delta n)! n^{\alpha n}}{(h!)^{\alpha n} (\alpha n)!} (\lambda^{e(H)+1})^{ \alpha n}\\ & \geq & \tau(\cb_n) \cdot (\delta n)! \ \left(\frac{\lambda^{e(H)+1}}{h! \alpha} \right)^{\alpha n} %(\lambda \lambda^{e(H)})^{\alpha n}. \end{eqnarray*} since $(\alpha n)! \leq \alpha^{\alpha n} n^{\alpha n}$. How often is the same graph $G'$ constructed? Call an oriented edge $e=uv$ {\em good} in $G'$ if it is a cut-edge in $G'$, the component $\tilde{G}$ of $G' - e$ containing $u$ has $h$ nodes, $u$ is the least of these nodes, and the increasing map from $\{1,\ldots,h\}$ to $V(\tilde{G})$ is an isomorphism between $H$ and $\tilde{G}$. Observe that each added oriented edge $r_B v_B$ is good. Indeed, there is exactly one good oriented edge for each appearance of $H$ in $G$. We shall see that $G'$ contains at most $(h+2) \alpha n$ good oriented edges. % which could be the added edge from a block to a non-special vertex. It will then follow that the number of times that $G'$ can be constructed is at most $\binom{(h+2)\alpha n}{\alpha n} \leq ((h+2)e)^{\alpha n}$. We may bound the number of good edges in $G'$ as follows. (a) There are exactly $\alpha n$ added oriented edges $r_B v_B$. (b) There are at most $\alpha n$ good oriented edges $e=uv$ in $E(G)$ (that is, such that the unoriented edge is in $G$): for in this case the entire component of $G' - e$ containing $u$ must be contained in $G$ (if it contained any other vertex it would have more than $h$ vertices), and so the number of them is at most $f_H(G)$. (c) There are at most $h \alpha n$ `extra' good oriented edges. To see this, consider a block $B$, and let $\tilde{H}$ denote the connected graph formed from the induced subgraph $G'[B]$ (which is isomorphic to $H$) together with the vertex $v_B$ and the edge $r_B v_B$. Each `extra' good oriented edge must be a cut edge in such a graph $\tilde{H}$ oriented away from $v_B$, and in each graph $\tilde{H}$ there are at most $h$ cut-edges. We may put the above results together to obtain \begin{eqnarray*} && g((1+\delta)n)\\ & \ge & \binom{(1\!+\!\delta)n }{ \delta n} \cdot e^{-\alpha n} (1\!-\!\eps)^n \gamma^n n! \cdot (\delta n)! \left(\frac{\lambda^{e(H)+1}}{h! \alpha} \right)^{\alpha n} %(h! \alpha)^{-\alpha n} \lambda^{(e(H)\!+\!1) \alpha n} ((h\!+\!2)e)^{-\alpha n}\\ %& = & % \left((1+\delta)n \right)! \cdot \gamma^{(1+\delta)n} \cdot (1-\eps)^n \cdot % \left(e^2 c^h (h+2) h! \lambda^{-(1+e(H))} \alpha \right)^{-\alpha n} \\ & = & \left((1+\delta)n \right)! \cdot \gamma^{(1+\delta)n} \cdot (1-\eps)^n \cdot 2^{\alpha n} \\ %& \stackrel{{\footnotesize (\ref{eq:num-pg-true3})}}{\ge}& & \geq & g((1+\delta)n) \ (1+\eps)^{-(1+\delta)n} \cdot (1-\eps)^n \cdot (1+ \eps)^{4n} \\ & \geq & g((1+\delta)n) \ ((1-\eps)(1+\eps)^2)^n \;\; > \; g((1+\delta)n), %& \stackrel{{\footnotesize (\ref{eq:num-pg-true2})}}{>} & %& > & % f((1+\delta)n), \end{eqnarray*} which is the desired contradiction. \end{proofof} \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{proofof}{Proposition~\ref{thm.apps2}} Denote $v(H)$ by $h$ and $\gamma^{-1}$ by $\rho$. Observe first that \[ \E[X_n(H)] = \binom{n}{h} (n-h) \lambda \lambda^{e(H)} \frac{\tau(\ca_{n-h})}{\tau(\ca_{n})} \sim \lambda n \frac{\rho^{h} \lambda^{e(H)}}{h!}.\] % Now consider $\E[(X_n(H))_2]$. For each graph $G$ on $\{1,\ldots,n\}$ let $Y_1(G,H)$ be the number of ordered pairs of appearances in $G$ of $H$ with disjoint vertex sets and such that the roots are not adjacent; and let $Y_2(G,H)$ be the number of ordered pairs of appearances in $G$ of $H$ such that either the vertex sets meet or the roots are adjacent. Thus $\left(X_n(H)\right)_2 = Y_1(R_n,H) + Y_2(R_n,H)$. Now \[ \E[ Y_1(R_n,H) ] = \frac{(n)_{2h}}{(h!)^2} (n-2h)^2 \lambda^2 \lambda^{2e(H)} \frac{\tau(\ca_{n-2h})}{\tau(\ca_{n})} \sim \left(\lambda n \frac{\rho^{h} \lambda^{e(H)}}{h!} \right)^2. \] But a graph $G$ of order at most $2h$ either consists of two appearances of $H$ with adjacent roots (and then $G$ has exactly two appearances of $H$), or the number of appearances of $H$ is at most the number of bridges in $G$. Thus $Y_2(G,H)$ is at most $2h$ times the number of components of $G$ of order at most $2h$, which is at most $2h \kappa(G)$; and so \[ \E[ Y_2(R_n,H) ] \leq 2h \E[\kappa(R_n)] \leq 2h(1+\frac{\nu}{\lambda}) \] since $\E[\kappa(R_n)] \leq 1+\frac{\nu}{\lambda}$ by Lemma~\ref{lem.tauconn}. %Theorem 2.2 of McDiarmid, Steger and Welsh~\cite{msw05}. Hence \[ \E[(X_n(H))_2] = \E[ Y_1(R_n,H) ] + O(1) \sim \left(\lambda n \frac{\rho^{h} \lambda^{e(H)}}{h!} \right)^2. %(n \rho^{h}/h!)^2. \] Thus the variance of $X_n(H)$ is $o(\E[(X_n(H))^2])$, and the result follows by Chebyshev's inequality. \end{proofof} \medskip Finally consider the remark concerning disjoint pendant appearances following Proposition~\ref{thm.apps2}. By the above proof, it suffices to note that in any graph $G$ the number of pendant appearances of $H$ that share a vertex or edge with some other pendant appearance is at most $Y_2(G,H)$, and so $\E[\tilde{X}_n(H)] \leq \E[Y_2(R_n,H)] = O(1)$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{Concluding remarks} %\label{sec.concl} % As we noted earlier, sometimes we learn more by having distinct edge-weights for bridges and non-bridges. % We need to know that there was a growth constant, and this was the case for an addable minor-closed class. % But what about the class $\cg^S$ of graphs embeddable on a given surface $S$? % We saw that the weighted class $\cg^S,\tau$ has a growth constant as long as % $\lambda_0=\lambda_1$; but does this hold without the extra condition? %insisting that $\lambda_0=\lambda_1$? %It seems likely that further work will show that $\cg^S,\tau$ has a growth constant for any $\tau$. % There is a similar question for the class of graphs with at most $k$ disjoint cycles. % the weighted class $\ca,\tau$ has a growth constant if $\lambda_0=\lambda_1$; %but does this hold without this extra condition? %Indeed, how generally is it true that if $\ca,\tau$ is well-behaved then so is $\ca,\tau'$? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Concluding remarks} \label{sec.concluding} Sometimes it may be helpful to generalise our probability model one step further. Bridges play a major role in this work. Recall that a {\em bridge} in a graph $G$ is an edge $e$ such that $G-e$ has one more component than $G$. For a graph $G$ we let $e_0(G)$ be the number of bridges in $G$ (the 0 is since a bridge is in 0 cycles) and let $e_1(G)=e(G)-e_0(G)$. In the definition of $\tau(G)$ let us replace $\lambda^{e(G)}$ by $\lambda_0^{e_0(G)} \lambda_1^{e_1(G)}$, where $\lambda_0$ and $\lambda_1$ are the {\em edge-parameters}. % and $\nu$ the {\em component-parameter}. Thus the distribution of the random graph $R_n \in_{\tau} \ca$ is as follows. Let $\lambda_0>0$, $\lambda_1>0$ and $\nu>0$, let $\lambda=(\lambda_0,\lambda_1)$, and let %$\tau=(\lambda_0,\lambda_1,\nu)$. $\tau=(\lambda,\nu)$. For each graph $G$ we let $\lambda^{e(G)}$ denote $\lambda_0^{e_0(G)} \lambda_1^{e_1(G)}$, and let $\tau(G) = \lambda^{e(G)} \nu^{\kappa(G)}$. Now we proceed as before, and let $\pr(R_n=G) \propto \tau(G)$ for each $G \in \ca_n$. %\m{Let $\tau(G)= \lambda^{e(G)} \nu^{\kappa(G)}$?} The most natural and interesting case is when $\lambda_0=\lambda_1$ but we learn more about the role of bridges by allowing the edge-parameters to differ. The results and proofs above change in a predictable way. We simply replace $\lambda$ by $\lambda_0$, except when $\lambda$ appears as $\lambda^{e(G)}$, which we now interpret as $\lambda_0^{e_0(G)} \lambda_1^{e_1(G)}$. This holds even for Proposition~\ref{thm.apps2}, where $\lambda \cdot \lambda^{e(H)}$ becomes $\lambda_0 \cdot \lambda_0^{e_0(H)} \lambda_1^{e_1(H)}$. There are two places where the change is most apparent. Theorem~\ref{thm.sumup} is the upside, where the role of bridges is brought out: each $\lambda$ is replaced by $\lambda_0$, and in particular everything depends on how $\gamma$ compares to $\lambda_0 e$. Lemma~\ref{lem.wellb} is the downside: we noted that the previous proofs that the classes in parts (b) and (c) had growth constants in the uniform case extended easily to yield growth constants in the weighted case, but that holds only when $\lambda_0=\lambda_1$. Can we drop this extra condition? %we write $y$ for $y_0,y_1$ and $y^{e(G)}$ for $y_0^{e_0(G)} y_1^{e_1(G)}$ In the addable minor-closed case we could easily introduce more edge-weights, though it is not clear how much more we would learn. For example, given a graph $G$ and an edge $e=uv$ in $G$, we could let $f(e)$ be the maximum number of edge-disjoint paths between $u$ and $v$ in $G - e$; let $e_k(G)$ be the number of edges $e$ in $G$ with $f(e)=k$; and let $\lambda^{e(G)}$ mean $\prod_{k \geq 0} \lambda_k^{e_k(G)}$, where each parameter $\lambda_k>0$. %(Or say let $f(e)$ be the maximum $k$ such that $e$ is in a $(k+1)$-connected subgraph of $G$.) \m{delete?} Then the results above for an addable minor-closed class still hold, with the same proofs -- and perhaps we do learn something? Indeed, we could go as far as the very general model in~\cite{cmcd12}, as long as we ensure that $\log \tau(G) = O(v(G))$. %\m{ok?} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bigskip \noindent {\bf Acknowledgement} I would like to thank Kerstin Weller and the referee for helpful comments. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %{\small \begin{thebibliography}{99} %\bibitem{amr08} % L. Addario-Berry, C. McDiarmid and B. Reed, % Connectivity for bridge-addable monotone graph classes, % {\em Combinatorics, Probability and Computing} FirstView Article, 1 -- 13, August 2012. %\bibitem{amr2011} L. Addario-Berry, C. McDiarmid and B. Reed, % Connectivity for bridge-addable monotone graph classes, 2011. %\bibitem{bbg07} % P. Balister, B. Bollob{\'a}s and S. Gerke, % {Connectivity of addable graph classes}. {\em J. Combin. Th. B} {\bf 98} (2008) 577 -- 584. %\bibitem{bbg10} % P. Balister, B. Bollob{\'a}s and S. Gerke (2010) % Connectivity of random addable graphs, {\em Proc. ICDM 2008}, No 13, 2010, 127 -- 134. %\bibitem{bbcr00} \m{not used? wanted?} % J.P. Bell, E.A. Bender, P.J. Cameron and L.B. Richmond, % Asymptotics for the probability of connectedness and the % distribution of number of components. % {\em Electron. J. Combin.} {\bf 7} (2000) R33. \bibitem{bb03} J.P. Bell and S.N. Burris. Asymptotics for logical limit laws; when the growth of the components is in an RT class. {\em Trans. Amer. Math. Soc} {\bf 355} (2003) 3777 -- 3794. %\bibitem{bb04} \m{wanted?} % J.P. Bell and S.N. Burris, % Partition identities I: sandwich theorems and logical 0-1 laws, % {\em Electron. J. Combin.} {\bf 11} (2004) R49. \bibitem{bcr08} E.A.~Bender, E.R.~Canfield and L.B.~Richmond. Coefficients of functional compositions often grow smoothly. {\em Electron. J. Combin.} {\bf 15} (2008) \#R21. \bibitem{bg09} E. Bender and Z. Gao. Asymptotic enumeration of labelled graphs with a given genus. {\em Electron. J. Combin.} {\bf 18} (2011) \#P13. %\m{P?} %arXiv:0912.4670. \bibitem{bgw02} %\m{or bgw01} E. Bender, Z. Gao and N. Wormald. The number of labeled 2-connected planar graphs. {\em Electron. J. Combin.} {\bf 9} (2002) \#R43. \bibitem{bs94} J. van den Berg and J.E. Steif. Percolation and the hard-core lattice gas model. \emph{Stoch. Proc. Appl.} {\bf 49} (1994) 179 -- 197. \bibitem{bnw09} O. Bernardi, M. Noy and D. Welsh. %(2009) Growth constants of minor-closed classes of graphs. {\em J. Combin. Theory B} {\bf 100} (2010) 468 -- 484. \bibitem{bps08a} N. Bernasconi, K. Panagiotou and A. Steger. On properties of random dissections and triangulations. in {\em Proc SODA} 2008, 132 -- 141. \bibitem{bps08b} N. Bernasconi, K. Panagiotou and A. Steger. On the degree sequence of random outerplanar and series-parallel graphs. {\em LNCS} {\bf 5171} (2008) 303 -- 316. \bibitem{bps09} N. Bernasconi, K. Panagiotou and A. Steger. The degree sequence of random graphs from subcritical classes. \emph{Combin. Prob. Comput.} {\bf 18} (2009) 647 -- 681. % pre-2010 %\bibitem{bfkv07} % M. Bodirsky, E. Fusy, M. Kang and S. Vigerske, % Enumeration and asymptotic properties of unlabeled outerplanar graphs, % {\em Electronic J. Combinatorics} {\bf 14} (2007), \#R66, 24 pages. \bibitem{bfkv11} %\m{not used, wanted? update} M. Bodirsky, E. Fusy, M. Kang and S. Vigerske. Boltzmann samplers, P\'olya theory, and cycle pointing. {\em SIAM J. Comput.} {\bf 40} (2011) 721 -- 769. \bibitem{bgkn05} M.~Bodirsky, O.~Gim\'enez, M.~Kang and M.~Noy. On the number of series-parallel and outerplanar graphs. Proceedings of European Conference on Combinatorics, Graph Theory, and Applications (EuroComb 2005), {\em Discrete Math. Theor. Comput. Sci. Proc. Vol. AE} (2005) 383 -- 388. \bibitem{bgkn07} M.~Bodirsky, O.~Gim\'enez, M.~Kang and M.~Noy. Enumeration and limit laws for series-parallel graphs. {\em European Journal of Combinatorics} {\bf 28} (2007) 2091 -- 2105. %bgkn07.pdf \bibitem{blkm05} M.~Bodirsky, M.L.~L\"offler, M.~Kang and C.~McDiarmid. Random cubic planar graphs. {\em Random Structures Algorithms} {\bf 30} (2007) 78 -- 94. \bibitem{bollobas} B.~Bollob\'as. {\em Random Graphs}. Second Edition, Cambridge University Press, 2001. \bibitem{burris2001} %\m{wanted} S.N. Burris. {\em Number theoretic density and logical limit laws}. Mathematical Surveys and Monographs 86, AMS, 2001. \bibitem{cfgn10} G.~Chapuy, E.~Fusy, O.~Gim\'enez and M.~Noy. On the diameter of random planar graphs. Proceedings of the 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings, vol.AM (2010) 65-78. %On the diameter of random planar graphs, manuscript, 2010. \bibitem{cfgmn11} G.~Chapuy, E.~Fusy, O.~Gim\'enez, B.~Mohar and M.~Noy. Asymptotic enumeration and limit laws for graphs of fixed genus. {\em J. Combinatorial Theory Ser A} {\bf 118} (2011) 748 -- 777. \bibitem{cfks08} G.~Chapuy, E.~Fusy, M. Kang and B. Shoilekova. A complete grammar for decomposing a family of graphs into 3-connected components. {\em Electronic J. Combinatorics} {\bf 15} (2008) \#R148. %\bibitem{dvw96} % A.~Denise, M.~Vasconcellos and D.~Welsh, % The random planar graph, % {\em Congressus Numerantium }{\bf 113} (1996) 61--79. \bibitem{diestel05} R. Diestel. {\em Graph Theory}. Fourth Edition, Springer-Verlag, Heidelberg, 2010. %\m{corrected 2012} \bibitem{dowden10} C. Dowden. The evolution of uniform random planar graph. {\em Electronic J. Combinatorics} {\bf 17} (2010) 1 -- 20. \bibitem{dowden11} C. Dowden. Random planar graphs with bounds on the maximum and minimum degrees. {\em Graphs and Combinatorics} {\bf 27} (2011) 87 -- 107. %\bibitem{drmota2009} % M. Drmota, {\em Random Trees}, Springer, 2009. \bibitem{dgn2011} M. Drmota, E. Fusy, M. Kang, V. Kraus and J. Ru\'e. Asymptotic study of subcritical graph classes. {\em SIAM J. Discrete Mathematics} {\bf 25} (2011), 1615-1651. %to appear (arxiv:1003:4699 24 march 2010). \bibitem{dgn10} M. Drmota, O.~Gim\'enez and M.~Noy. %Michael Drmota, Omer Giménez, Marc Noy: Vertices of given degree in series-parallel graphs. {\em Random Struct. Algorithms} {\bf 36} (2010) 273-314. \bibitem{dgn11a} M. Drmota, O.~Gim\'enez and M.~Noy. %Michael Drmota, Omer Giménez, Marc Noy: Degree distribution in random planar graphs. {\em J. Comb. Theory, Ser. A} {\bf 118} (2011) 2102-2130. \bibitem{dgn11b} M. Drmota, O.~Gim\'enez and M.~Noy. %\m{wanted?} The Maximum Degree of Series-Parallel Graphs. {\em Combinatorics, Probability \& Computing} {\bf 20} (2011) 529-570. \bibitem{dgnps12} M. Drmota, O.~Gim\'enez, M.~Noy, K. Panagiotou and A. Steger. The maximum degree of random planar graphs. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '12), 2012, 281-287. %manuscript, 12 July 2011. %\bibitem{dfls04} \m{wanted?} % P. Duchon, P. Flajolet, G. Louchard and G. Schaeffer, % Boltzmann samplers for the random generation of combinatorial structures, % {\em Combinatorics, Probability \& Computing} {\bf 13} (2004) 577 -- 625. \bibitem{dn10} Z. Dvor\'ak and S. Norine. Small graph classes and bounded expansion. {\em J. Combinatorial Theory B} {\bf 100} (2010) 171 -- 175. %\bibitem{ffp11} % P. Flajolet, E. Fusy and C. Pivoteau, % Boltzmann sampling of unlabelled structures, % manuscript, 2011. \bibitem{fs09} P. Flajolet and R. Sedgewick. {\em Analytic Combinatorics}. CUP, 2009. \bibitem{fp11} N. Fountoulakis and K. Panagiotou. 3-connected cores in random planar graphs. {\em Combinatorics, Probability \& Computing} {\bf 20} (2011) 381 -- 412. \bibitem{fusy09} E. Fusy. Uniform random sampling of planar graphs in linear time. {\em Random Structures and Algorithms} {\bf 35} (2009) 464 -- 522. \bibitem{ggnw07} S.~Gerke, O.~Gim\'enez, M.~Noy and A.~Wei{\ss}l. The number of graphs not containing $K_{3,3}$ as a minor. %On the number of $K_{3,3}$-minor-free and maximal %$K_{3,3}$-minor-free graphs. {\em Electron. J. Combin.} {\bf 15} (2008) R114. \bibitem{gm04} %\m{wanted?} S. Gerke and C. McDiarmid. On the number of edges in random planar graphs. {\em Combinatorics, Probability and Computing} {\bf 13} (2004) 165 -- 183. \bibitem{gmsw05} %\m{wanted?} S. Gerke, C. McDiarmid, A. Steger and A. Weissl. Random planar graphs with n nodes and a fixed number of edges. {\em Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)} 2005, 999 -- 1007. \bibitem{gmsw07} S. Gerke, C. McDiarmid, A. Steger and A. Weissl. Random planar graphs with given average degree. in {\em Combinatorics, Complexity and Chance, a tribute to Dominic Welsh} (G. Grimmett and C. McDiarmid eds) Oxford University Press, 2007, 83 -- 102. \bibitem{gn09a} O. Gim\'enez and M. Noy. Asymptotic enumeration and limit laws of planar graphs. %arXiv: math.CO/0501269, 2005 arXiv: math.CO/0501269. {\em J. Amer. Math. Soc.} {\bf 22} (2009) 309--329. \bibitem{gn09b} O. Gim\'enez and M. Noy. Counting planar graphs and related families of graphs. in {\em Surveys in Combinatorics 2009}, 169 -- 329, Cambridge University Press, Cambridge, 2009. \bibitem{gnr07} O. Gim\'enez, M. Noy and J. Ru\'{e}. %Omer Giménez, Marc Noy, Juan José Rué: Graph classes with given 3-connected components: asymptotic counting and critical phenomena. {\em Electronic Notes in Discrete Mathematics} {\bf 29} (2007) 521 -- 529. %\bibitem{gnr11?} % O. Gim\'enez, M. Noy and J. Ru\'{e}, % Graph classes with given 3-connected components: asymptotic % counting and critical phenomena, % arXiv:0907.0376. \bibitem{grimmett06} G. Grimmett. {\em The Random-Cluster Model}. Springer, 2006. \bibitem{jlr00} S. Janson, T. {\L}uczak and A. Ruci{\'n}ski. {\em Random Graphs}. Wiley Interscience, 2000. \bibitem{kl09} M. Kang and M. Loebl. The enumeration of planar graphs via Wick's theorem. {\em Advances in Mathematics} {\bf 221} (2009) 1703 -- 1724. \bibitem{kl10} M. Kang and T. {\L}uczak. Two critical periods in the evolution of random planar graphs. {\em Trans. Amer. Math. Soc} {\bf 364} (2012), 4239-4265. %arXiv:1006.0444v1. \bibitem{kmcd11} M. Kang and C. McDiarmid. Random unlabelled graphs containing few disjoint cycles. {\em Random Structures and Algorithms} {\bf 38} (2011) 174 -- 204. %\bibitem{kp2011} % M. Kang and K. Panagiotou, % On the connectivity of random graphs from addable classes, 2011. \bibitem{km08b} V.~Kurauskas and C.~McDiarmid. Random graphs with few disjoint cycles. %{\em Combinatorics, Probability and Computing}, published online 9 June 2011. {\em Combinatorics, Probability and Computing} {\bf 20} (2011) 763 -- 775. \bibitem{km11} V.~Kurauskas and C.~McDiarmid. Random graphs containing few disjoint excluded minors. {\em Random Structures and Algorithms}, published online 27 July 2012. \bibitem{lint-wilson} J.H. van Lint and R.M. Wilson. {\em A Course in Combinatorics}. 2nd ed. Cambridge University Press, Cambridge, 2001. %\bibitem{luczak98} % T. {\L}uczak, % Random trees and random graphs, % {\em Random Structures and Algorithms} {\bf 13} (1998) 485 -- 500. %\bibitem{lp92} % T. {\L}uczak and B. Pittel. % Components of random forests, % {\em Combinatorics, Probability and Computing} {\bf 1} (1992) 35 -- 52. \bibitem{mader68} W.~Mader. Homomorphies\"atze f\"ur Graphen. {\em Math. Ann.} (1968) {\bf 178} 154 -- 168. \bibitem{cmcd08} C.~McDiarmid. Random graphs on surfaces. {\em J. Combinatorial Theory B} {\bf 98} (2008) 778 -- 797. \bibitem{cmcd09} C.~McDiarmid. Random graphs from a minor-closed class. {\em Combinatorics, Probability and Computing} {\bf 18} (2009) 583 -- 599. \bibitem{cmcd11} C.~McDiarmid. On graphs with few disjoint $t$-star minors. {\em European J. Comb.} {\bf 32} (2011) 1394 -- 1406. \bibitem{cmcd12} C.~McDiarmid. Connectivity for random graphs from a weighted bridge-addable class, 2012, %submitted to {\em Electronic J Combinatorics} on 01-08-2012. Also updated on arxiv, still at http://arxiv.org/abs/1203.3398. %\arxiv{1203.3398}. %submitted to Elec J C ? %\bibitem{cmcd12b} % C.~McDiarmid, % Random graphs from a weighted minor-closed class, % arXiv \m{extended version - do!} %\bibitem{cmcd12c} \m{delete} % C.~McDiarmid, % Minor-closed unlabelled graph classes. % In preparation. \bibitem{cb08} C.~McDiarmid and B. Reed. On the maximum degree of a random planar graph. {\em Combinatorics, Probability and Computing} {\bf 17} (2008) 591-- 601. \bibitem{msw05} C.~McDiarmid, A.~Steger and D.~Welsh. Random planar graphs. {\em J. Combinatorial Theory B} {\bf 93} (2005) 187 -- 206. \bibitem{msw06} C.~McDiarmid, A.~Steger and D.~Welsh. Random graphs from planar and other addable classes. {\em Topics in Discrete Mathematics} (M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, P. Valtr eds), Algorithms and Combinatorics 26, Springer, 2006, 231 -- 246. %\bibitem{mt01} B.~Mohar and C.~Thomassen, % {\em Graphs on Surfaces}, % The Johns Hopkins University Press, 2001. \bibitem{moon70} J.W.~Moon. {\em Counting labelled trees}. {Canadian Mathematical Monographs 1}, 1970. \bibitem{nstw06} S.~Norine, P.~Seymour, R.~Thomas and P.~Wollan. Proper minor-closed families are small. {\em J. Combin. Theory B} {\bf 96} (2006) 754 -- 757. \bibitem{ps10} K. Panagiotou and A. Steger. Maximal biconnected subgraphs of random planar graphs. {\em ACM Transactions on Algorithms} {\bf 6} (2010) art. no. 31. \bibitem{ps11} K. Panagiotou and A. Steger. On the degree sequence of random planar graphs. Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), 2011, 1198-1210. %in {\em Proc SODA} 2011, 1198 -- 1210. %\bibitem{renyi59} % R\'enyi, A. (1959) % Some remarks on the theory of trees. % {\em Publications of the Mathematical Institute of the % Hungarian Academy of Sciences} {\bf 4} 73 -- 85. \bibitem{rs04} N.~Robertson and P.D.~Seymour. Graph minors I - XX. {\em J. Combin. Theory B} (1983 -- 2004). \bibitem{stanley99} R.P.~Stanley. {\em Enumerative Combinatorics}, Vol 2. Cambridge University Press, 1999. \end{thebibliography} %} \end{document}