%Typeset with LaTeX format \documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.50}{25(4)}{2018} \usepackage{amsmath, amssymb} \usepackage{amsfonts} \usepackage{mathrsfs} \usepackage[arrow,matrix,curve,cmtip,ps]{xy} \usepackage{graphicx} \usepackage{comment} %\usepackage{hyperref} \usepackage[utf8]{inputenc} %\usepackage[capitalise]{cleveref} \usepackage{tikz} %\usepackage{tkz-graph} \usepackage{float} %\usepackage{appendix} \usepackage{amsthm} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \makeatletter \let\@wraptoccontribs\wraptoccontribs \makeatother %\crefname{section}{\S}{\S\S} %\Crefname{section}{\S}{\S\S} %\newenvironment{changemargin}[2]{% % \begin{list}{}{% % \setlength{\topsep}{0pt}% % \setlength{\leftmargin}{#1}% % \setlength{\rightmargin}{#2}% % \setlength{\listparindent}{\parindent}% % \setlength{\itemindent}{\parindent}% % \setlength{\parsep}{\parskip}% % }% % \item[]}{\end{list}} \tikzset{node distance=2cm, auto} \allowdisplaybreaks %\newtheorem{theorem}{Theorem}[section] %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{notation}[theorem]{Notation} %\newtheorem{formula}[theorem]{Formula} %\newtheorem*{theorem*}{Theorem} %\theoremstyle{remark} %\newtheorem{remark}[theorem]{Remark} %\newtheorem{note}[theorem]{Note} %\newtheorem{definition}[theorem]{Definition} %\newtheorem{example}[theorem]{Example} %\newtheorem{question}{Question} %\newtheorem{conjecture}{Conjecture} %this has equations numbered within sections 1.1,1.2,... 2.1,... \numberwithin{equation}{section} %------------------------------------------- % Begin Local Macros %------------------------------------------- \newcommand{\U}{\mathcal{U}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\T}{\mathbb{T}} \newcommand{\cT}{\mathcal{T}} \newcommand{\im}{\operatorname{im}} \newcommand{\coker}{\operatorname{coker}} \newcommand{\ind}{\operatorname{ind}} \newcommand{\rank}{\operatorname{rank}} \newcommand\mc[1]{\marginpar{\sloppy\protect\footnotesize #1}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\Hi}{\mathcal{H}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cW}{\mathcal{W}} \newcommand{\reals}{\mathbb{R}} \newcommand{\maxrank}{\operatorname{maxrank}} \newcommand{\minrank}{\operatorname{minrank}} \newcommand{\abs}[1]{\left\lvert #1 \right\rvert} \renewcommand{\P}{\mathbb{P}} \newcommand{\internal}{\operatorname{int}} \newcommand{\external}{\operatorname{ext}} \newcommand{\co}{\text{Con}} \newcommand{\conn}{\mathrm{conn}} \newcommand{\Om}{\Omega} \newcommand{\vol}{\text{vol}} \newcommand{\diag}{\mathop{\mathrm{diag}}} \newcommand{\bd}{\partial} \newcommand{\tw}{\widetilde{w}} \newcommand{\Perm}{\operatorname{Perm}} %Sergey's macros \newcommand{\eps}{\varepsilon} \renewcommand{\mc}[1]{\mathcal{#1}} \newcommand{\bb}[1]{\mathbb{#1}} \newcommand{\bl}[1]{\boldsymbol{#1}} \newcommand{\brm}[1]{\operatorname{#1}} \renewcommand{\bd}[1]{\partial #1} %Calum's macros %\newcommand{\cal}{\mathcal} \newcommand{\mb}{\mathbb} \newcommand{\ep}{\epsilon} \newcommand{\scr}{\mathscr} \newcommand{\supp}{\text{supp}} %Calum's packages \usepackage{enumerate} %------------------------------------------- % End Local Macros %------------------------------------------- \dateline{Jul 7, 2017}{Nov 9, 2018}{Dec 21, 2018} \MSC{05C31,05C80,05C63,60B10} \Copyright{ The authors. Released under the CC BY-ND license (International 4.0).} \title{Distribution of Coefficients of Rank Polynomials\\ for Random Sparse Graphs} \author{ Dmitry Jakobson\thanks{Supported by NSERC, FQRNT and Peter Redpath fellowship.}\\ \small\tt jakobson@math.mcgill.ca\\ \and Calum MacRury\thanks{Supported by NSERC}\\ \small\tt calum.macrury@mail.mcgill.ca\\ \and Sergey Norin\thanks{Supported by NSERC}\\ \small\tt snorine@gmail.com\\ \and Lise Turner\thanks{Supported by NSERC}\\ \small\tt lise.turner@mail.mcgill.ca\\ \small Department of Mathematics and Statistics\\[-0.8ex] \small McGill University\\[-0.8ex] \small 805 Sherbrooke Str. West, Montr\'eal QC H3A 0B9, Ca\-na\-da} %\thanks{D. J. was supported by NSERC, FQRNT and Peter Redpath %fellowship. S. N. and L. T. were supported by NSERC} \begin{document} \maketitle \begin{abstract} We study the distribution of coefficients of rank polynomials of random sparse graphs. We first discuss the limiting distribution for general graph sequences that converge in the sense of Benjamini-Schramm. Then we compute the limiting distribution and Newton polygons of the coefficients of the rank polynomial of random $d$-regular graphs. \end{abstract} %\maketitle \section{Introduction} Dichromatic polynomial is the most general graph invariant satisfying deletion-contraction properties. It contains important information about $G$, in particular about its connectivity properties, and about nowhere-zero flows on $G$. In Statistical Physics, it describes the partition function for the Potts model on $G$. When restricted to certain curves (or points), the dichromatic polynomial specializes to some well-known graph invariants, including chromatic polynomial, the number of spanning trees, the number of acyclic orientations etc. It is closely related to important invariants in knot theory, including the Jones polynomial. Equivalent forms of dichromatic polynomial include the Tutte and the rank polynomials of the graph. The Tutte polynomial is perhaps better known. (See \cite{Welsh} for an excellent survey on the properties of the Tutte polynomial.) In this paper, however, we consider rank polynomials (defined in \ref{rank:polynomial:def}), focusing on the coefficients, as it turns out that the behaviour of the coefficients of rank polynomial is more tangible. We focus on the asymptotic properties of the rank polynomial, focusing primarily on the sparse graphs. The asymptotic behaviour of many graph invariants, including Laplace spectrum, cycle distribution, colouring properties, non-concentration of eigenvectors etc. has been studied extensively before. However, several asymptotic properties of the rank and Tutte polynomials have not been considered before, to our knowledge. In our paper, we focus on the {\em coefficients} of those polynomials. We first study {\em Newton polygons} for the rank polynomials for random regular graphs in \ref{sec:Newton}. We determine them for $d$-edge connected $d$-regular graphs (Theorem \ref{rank:Newton:triangle}), then describe them for general graphs. Next, we define probability measures describing the concentration of the (normalized) coefficients of those polynomials. The \emph{coefficient measure} for the rank polynomial is defined in \ref{measure:rank:defn}. In sections \ref{BS:coefficients} and \ref{sec:generating:function}, we discuss the limiting distribution of the coefficients of the rank polynomial associated for Benjamini-Schramm convergent sequences of graphs and compute it exactly for random $d$-regular graphs. The questions considered in this paper were suggested by numerical experiments in the paper \cite{JLMRT}, where some a priori results on the coefficient measures for the Tutte polynomial were also established. %%%%% \section{Rank polynomial}\label{sec:rank} Let $G$ be a graph without loops or multiple edges, with the vertex set $V=V(G)$ and the edge set $E=E(G)$. We let $|V(G)|=n$ and $|E(G)|=m$. We denote by $G|A$ the subgraph of $G$ whose edge set is $A$ and whose vertex set is $V(G)$, and we denote by $k(H)$ the number of connected components of a graph $H$. The {\em rank polynomial} $R_G$ of a graph $G$ with $n$ vertices and $m$ edges, cf. \cite[Definition 10.1]{biggs} is defined by \begin{equation}\label{rank:polynomial:def} R_G(x,y):=\sum_{A\subseteq E(G)} x^{r(G|A)}y^{s(G|A)}, \end{equation} where $r(G|A)=n-k(G|A)$ denotes the {\em rank} of $G|A$, and $s(G|A)=|A|-n+k(G|A)$ denotes the {\em co-rank} of $G|A$. It is easy to see that $R_G(x,y)$ is indeed a polynomial. Let $G_1,\ldots,G_k$ be the connected components of $G|A$; we see that $$ |A|=\sum_{i=1}^k|E(G_i)|\geq \sum_{i=1}^k (|V(G_i)|-1)=n-k(G|A), $$ therefore $s(G|A)\geq 0$. The above argument also shows that $s(G|A)=0$ if and only if $G|A$ is a forest. Also, clearly $r(G|A)\geq 0$, and the equality holds if and only if $A=\emptyset$. Thus $A=\emptyset$ corresponds to the constant term $1$ in $R_G(x,y)$. Denote the coefficients of the rank polynomial by $\rho_{rs}$: \begin{equation}\label{rank:polynomial:coefficients} R_G(x,y)=\sum_{r,s}\rho_{rs}x^ry^s. \end{equation} Thus $\rho_{rs}$ denotes the number of subgraphs of $G$ with rank $r$ and co-rank $s$. Those coefficients are the entries of the {\em rank matrix} $\rho_{rs}(G)$ of the graph $G$, see \cite[Ch. 10]{biggs} or \cite[Ch. 15]{GR}. \subsection{Newton polygon of the rank polynomial}\label{sec:Newton} In this section we consider the {\em Newton polygon} $\Pi(R_G)$ for the rank polynomial $R_G$. It is the convex hull of the set of all lattice points $\{(r,s)\in\Z^2:\rho_{rs}\neq 0\}$. We start by making some simple observations about $\Pi(R_G)$. We first remark that all the points lying on the line segment $I_0(G):=\{(a,0):0\leq a\leq n-1\}$ belong to $\Pi(R_G)$: They correspond to forest subgraphs of $G$ with $a$ edges. This segment coincides with $\Pi(R_G)$ if and only if $G$ is a forest. From now on, we assume that $G$ is connected and has at least one cycle; in that case $I_0(G)$ is a proper subset of $\Pi(R_G)$. If the graph $G|A$ has one connected component and contains all the vertices of $G$, then $r(G|A)=n-1$; its co-rank varies between $s=0$ (a spanning tree) and $s=m-n+1$ ($A=E$); accordingly all the points $\{(n-1,b):0\leq b\leq m-n+1\}$ belong to $\Pi(R_G)$. The tangent of the angle $\alpha(m,n)$ that the line from $(0,0)$ to $(n-1,m-n+1)$ forms with the $x$-axis satisfies $\tan\alpha(m,n)=\frac{m-n+1}{n-1}=\frac{m}{n-1}-1$. Accordingly, if we denote by $\alpha_0$ the angle formed by the sides of $\Pi(R_G)$ at the origin $(0,0)$, it will satisfy $$ \tan\alpha_0=\sup_{A\subseteq E:(G|A)\ has\ cycles} \frac{|E(G|A)|}{|V(G|A)|-1}-1. $$ In general, the supremum need not be attained for $A=E$. \begin{example} Consider a graph $G(n,s)$ consisting of complete graph $K_{n+1}$ on $(n+1)$ vertices; and a path of length $s$ starting at one of the vertices of $K_{n+1}$. If we take $A$ to be all the edges of $K_{n+1}$, then $\tan\alpha(A)=\frac{(n+1)n}{2n}-1=\frac{n-1}{2}$. If we take $A=E$, then we get $\tan\alpha(E)=\frac{(n+1)n/2+s}{n+s}-1<\tan\alpha(A)$ by an easy calculation. \end{example} For regular graphs, $\Pi(R_G)$ also need not be a triangle. \begin{example} Consider a graph $G(k,q)$ constructed as follows: take $q\geq 2$ disjoint copies of the complete graph $K_k$; then connect those graphs by edge switching along a cycle of length $q$. Clearly, after removing $2\leq p\leq q$ ``cycle'' edges from that graph, we will get a graph $G_p(k,q)$ with $p$ connected components. It is easy to show that for $k\geq 5$, we shall have $$ \tan\alpha(G_p(k,q))=\frac{qk(k-3)}{2(kq-p)}>\frac{qk(k-3)+2}{2(kq-1)}=\tan\alpha(G(k,q)). $$ It follows that $\Pi(R_{G(k,q)})$ is not a triangle. \end{example} The situation is simpler for $d$-edge connected $d$-regular graphs. \begin{theorem}\label{rank:Newton:triangle} Let $G$ be a $d$-edge connected $d$-regular graph $(d\geq 3)$ on $n$ vertices. Then the Newton polygon $\Pi(R_G)$ of the rank polynomial $R_G$ is the triangle $T(n,d)$ with the vertices at $(0,0),(0,n-1)$ and $(n-1,m-n+1)$. \end{theorem} \noindent{\bf Proof:} Let $A_n=(0,0),B_n=(0,n-1)$ and $C_n=(n-1,m-n+1)$ be the vertices of $T(n,d)$; since $d$ is fixed, we suppress the dependence on $d$. We have shown previously that the line segments $[A_n,B_n]$ and $[B_n,C_n]$ belong to the boundary of $\Pi(R_G)$; it remains to be shown that $\Pi(R_G)\subseteq T(n,d)$. Equivalently, all points in $\Pi(R_G)$ lie below the line segment $[A_n,C_n]$. The tangent of the angle $\alpha(G)$ formed by the sides $C_n,A_n$ and $B_n,A_n$ of $T_n$ is equal to $$ \tan\alpha(G)=\frac{m-n+1}{n-1}=\frac{dn/2-n+1}{n-1}. $$ Let $A\subseteq E$; suppose the graph $G|A$ has $k$ connected components. We have $$ \frac{dn}{2}-|A| = |E\setminus A| \geq \frac{d k}{2}, $$ where the second inequality is by the $d$-edge connectivity of $G$: for a fixed component $C$ of $G|A$, there are at least $d$ edges with exactly one endpoint in $C$. Thus \begin{equation}\label{expansion:1} |A| \leq \frac{d(n-k)}{2}, \end{equation} The monomial corresponding to the graph $G|A$ corresponds to the point $C(A)$ with the coordinates $(n-k,|A|-n+k)$, hence the tangent of the angle $\alpha(A)$ formed by the lines $A_nB_n$ and $A_nC(A)$ is given by $$ \tan\alpha(A)=\frac{|A|-n+k}{n-k}. $$ To prove the theorem, it suffices to show that $\tan\alpha(S)\leq\tan\alpha(A)$, which is equivalent to $$ (dn/2-n+1)(n-k)\geq(|A|-n+k)(n-1). $$ Using the upper bound (\ref{expansion:1}) on $|A|$ the above is implied by $$ (dn/2-n+1)(n-k)\geq((d/2-1)(n-k))(n-1), $$ which reduces to $0 \geq -d/2$ after cancellations. \qed We remark that random $d$-regular graphs are a.a.s. $d$-edge connected \cite{Bollobas}. \begin{corollary}\label{random:newton:triangle} The conclusion of Theorem \ref{rank:Newton:triangle} holds for random regular graphs with probability tending to $1$ as $n\to \infty$. \end{corollary} %%% \section{Newton polygon of the rank polynomial for general graphs} \label{sec:Newton:rank:general} In this section we describe the Newton polygon of the rank polynomial for general graphs. The key relevant notion turns out to be the so-called {\em $k$-edge-connectivity}, defined in \cite{BC} and also \cite{Gol80,Gol81}. Let $G$ be a connected graph with $n$ vertices. For $k\leq n$, the \emph{$k$-edge-connectivity} $\conn_k(G)$ is defined to be the minimal number of edges that need to be removed from $G$ to separate $G$ into $k$ connected components. We remark that the notation in \cite{BC} is slightly different from ours: $\lambda_i$ in \cite{BC} equals to our $\conn_{i+1}$; our notation is consistent with the notation in \cite{ZHLS}. Consider the vertical line $\{r=const\}\subseteq\Z^2$; we would like to determine the largest $s$ such that the point $(r,s)$ lies in $\Pi(R_G)$. Let $A\subseteq E(G)$, and let $x^{r(G|A)}y^{s(G|A)}$ be the corresponding monomial in $R_G$. We have $r(G|A)=n-k(G|A)$ (from \ref{rank:polynomial:coefficients}), so fixing $r$ is equivalent to fixing the number $k=k(G|A)$ of the connected components of the graph $(G|A)$. For a fixed $r$, we would like to find the largest possible $s=s(G|A)$. We remark that $r(G|A)+s(G|A)=|A|$, so finding the largest $s$ is equivalent to finding the largest $|A|$ such that removing $E\setminus A$ from the graph $G$ disconnects it into $k$ connected components. By the definition of $k$-edge-connectivity, we have $m-|A|=\conn_k(G)$ and therefore $|A|=m-\conn_k(G)$. We summarize the above discussion. \begin{theorem}\label{Newton:polygon:rank} Let $G$ be a connected graph with $n$ vertices and $m$ edges, and let $\Pi=\Pi(R_G)$ denote the Newton polygon of the rank polynomial $R_G$. \begin{itemize} \item[(a)] The lower part of the boundary $\bd\Pi$ contains the horizontal line segment connecting the points $(0,0)$ and $(n-1,0)$; \item[(b)] The right part of the boundary $\bd\Pi$ contains the vertical line segment connecting the points $(n-1,0)$ and $(n-1,m-n+1)$; \item[(c)] The upper part of the boundary $\bd\Pi$ coincides with the (``upper'') convex hull of the set of points $$ \{(n-k,m-\conn_k(G)):1\leq k\leq n\}, $$ where $\conn_k(G)$ denotes the $k$-edge-connectivity of $G$. \end{itemize} \end{theorem} It is clear from \eqref{rank:polynomial:def} that if the graph $G_2$ is obtained from the graph $G_1$ by adding several new edges ($G_1\subseteq G_2$), then any monomial appearing in $R_{G_1}$ also appears in $R_{G_2}$, since any subset $A$ of $E(G_1)$ is also a subset of $E(G_2)$. It follows that $\Pi(R_{G_1})\subseteq\Pi(R_{G_2})$. It was shown in \cite[Corollary 2]{BC} that $\conn_k(K_n)=(k-1)(2n-k)/2$. Accordingly, for any graph $G$ on $n$ vertices, $\Pi(R_G)$ lies below the ``upper'' convex hull of the set $$ \{(n-k,n(n-1)/2-(k-1)(2n-k)/2):1\leq k\leq n\}. $$ Below, we summarize some of the known results about $\conn_k(G)$. It was shown in \cite[Theorem 1]{BC} that for $1\leq k1$, we have \begin{equation}\label{edge:connectivity:lower} \conn_l(G)\geq \frac{l\cdot\conn_2(G)}{2}. \end{equation} We next discuss the values of $\conn_k(G)$ for small $k$ and small $n-k$. Clearly, $\lambda_1(G)=0$ for connected graphs; $\conn_2(G)$ is the edge connectivity of $G$. Clearly, $\conn_2(G)\leq \delta(G)$, the minimal degree of $G$. Next, $\conn_n(G)=m$ for connected graphs. For simple graphs $G$, if $A\subseteq E$ contains at least $2$ edges, then $G|A$ has at most $(n-2)$ components, so $\conn_{n-1}(G)=m-1$, hence the point $(1,1)\in\Pi(R_G)$. Also, if $G$ has girth $3$ (contains triangles), then $\conn_{n-2}(G)=m-3$, hence the point $(2,3)\in\Pi(R_G)$. %Section added by Calum - general results on how to metrize weak convergence \section{Weak Convergence of Probability Measures} Many of the results throughout the remainder of the paper involve analyzing the the coefficients of rank polynomials of various sequences of graphs. Often times, these graphs will be generated randomly, thus randomizing their coefficients. As a result, much of the analysis throughout the proceeding sections involves understanding the convergence of random variables. For convenience, we have presented a short review of some notions from probability theory to help the reader process these results. These results are standard, so their proofs are omitted. Let $(S,d)$ be a metric space. If $(\mb{P}_k)_{k \ge 1}$ is a sequence of probability measures on $S$, then we say that $(\mb{P}_k)_{k \ge 1}$ \textit{converges weakly} to probability measure $\mb{P}$, provided $$ \int f \, d\mb{P}_{k} \xrightarrow{} \int f \, d\mb{P} $$ as $k \rightarrow \infty$, for all $f \in C_{b}(S)$; the space of bounded continuous functions on $S$. This definition induces a topology on $\Pr(S,d)$, the space of all probability measures on $S$ (we shorten this to $\Pr(S)$ when the context is clear). It turns out that this topology is metrizable, provided $S$ is separable. We now introduce a number of metrics which characterize this topology. Suppose that $\mathcal{S}$ is the sigma algebra induced by the topology on $S$. Let $\mb{P}$ and $\mb{Q}$ be probability measures on $S$. If $A$ is a subset of $S$ and $\ep \ge 0$, then we denote $$ A^{ \ep} := \{ s \in S \, : \, \, d(s,A) < \ep \}. $$ With this notation, we define a map $\pi: \Pr(S) \times \Pr(S) \rightarrow [0,1]$, where $$ \pi (\mb{P},\mb{Q}) := \inf \{ \ep \ge 0 \, : \,\, \mb{P}(A) \le \mb{Q}(A^{\ep}) + \ep \; and \; \mb{Q}(A) \le \mb{P}(A^{\ep}) + \ep,\ \text{for all} \, A \in \mathcal{S} \}, $$ for the probability measures $\mb{P}$ and $\mb{Q}$. The map $\pi$ is symmetric, and functions as a metric on the space $\Pr(S)$. It is known as the Levy-Prokhorov metric, and characterizes weak convergence of probability measures. \begin{theorem} Let $(\mb{P}_k)_{k \ge 1}$ be a sequence of probability measures on $S$. If $S$ is separable and $\mb{P}$ is a probability measure on $S$, then the following are equivalent: \begin{enumerate} \item $\mb{P}_k$ tends to $\mb{P}$ weakly. \item $\pi ( \mb{P}_k, \mb{P})$ tends to zero. \end{enumerate} \end{theorem} \begin{remark} If $s_{0}$ is a fixed point of $S$, we say that $\mb{P}_{k}$ converges to the constant $s_{0}$, provided $\mb{P}_{k}$ converges to the distribution $\delta_{s_0}$. We occasionally abuse this notation and write $\pi( \mb{P}_k, s_{0} )$, instead of $\pi( \mb{P}_k, \delta_{s_{0}} )$. \end{remark} If we consider the space $\Pr(S)$ together with this metric $\pi$, then we can recover topological properties of $\Pr(S)$ from $S$. \begin{theorem}\label{thm:metrizability} Let $S$ be a metric space. We observe the following equivalences: \begin{enumerate} \item $S$ is separable if and only if $\Pr(S)$ is separable. \item $S$ is compact if and only if $\Pr(S)$ is compact. \end{enumerate} \end{theorem} Alternatively, if we assume that the metric $d$ is bounded, then we can define the Wasserstein distance between $\mb{P},\mb{Q} \in \Pr(S)$. To do so, we first define, $$ M( \mb{P}, \mb{Q}) = \{ \mu \, : \, \mu \; \text{is a law on $S \times S$ with marginals $\mb{P}$ and $\mb{Q}$}\}. $$ We then define $W(\mb{P},\mb{Q})$ as, $$ \inf \{\int d(x,y) \, d\mu(x,y) \, : \, \mu \in M(\mb{P},\mb{Q}) \}. $$ If $S$ is a separable metric space, then $W$ forms a metric on $\Pr(S)$. Moreover, since $d$ was assumed to be bounded, we have the following result: \begin{proposition} Suppose $(S,d)$ is a seperable metric space with finite diameter $\widetilde{d}:= \sup_{x,y}d(x,y)$. We observe the following inequalities: \begin{enumerate} \item $W(\mb{P},\mb{Q}) \le (1+ \widetilde{d}) \pi ( \mb{P},\mb{Q})$ \item $\pi (\mb{P},\mb{Q})^{2} \le W( \mb{P}, \mb{Q})$ \end{enumerate} for all $\mb{P}$ and $\mb{Q}$ in $Pr(S)$. \end{proposition} Thus, $W$ provides another way of metrizing weak convergence. We shall consider both metrics throughout the paper. If one of the distributions that we work with is a point mass, then we can improve upon the above results. \begin{proposition}\label{prop:metric_relations} Suppose $\mb{P}$ is a distribution on $S$. If $s_0$ is a fixed point of $S$, then the following inequalities hold: \begin{enumerate} \item $\pi(\mb{P}, \delta_{s_0}) = \inf\{ \ep >0 : \mb{P}( D_{\ep}(s_0)) \ge 1 - \ep \}$, \item $W(\mb{P},\delta_{s_0}) = \int_{S} d(s,s_0) \, d\mb{P}(s)$, \end{enumerate} where $D_{\ep}(s_0)$ is the disc of radius $\ep$ about $s_{0}$, with respect to the metric $d$. Moreover, we have that, \begin{enumerate} \item $W(\mb{P},\delta_{s_0}) \le (1+\widetilde{d}- \pi(\mb{P},\delta_{s_0}))\pi(\mb{P},\delta_{s_0})$, \item $\pi(\mb{P},\delta_{s_0})^2 \le W(\mb{P},\delta_{s_0})$. \end{enumerate} where $\widetilde{d}$ is the diameter of $S$. \end{proposition} This proposition implies a simple way to characterize when a sequence of probability measures converges to a point mass. \begin{corollary}\label{cor:metric_relations} Let $(\mb{P}_{k})_{k\ge1}$ be a sequence of probability measures on $S$, and suppose $s_{0} \in S$. We have that $\mb{P}_{k}$ converges weakly to the distribution $\delta_{s_0}$, if and only if for each $\ep > 0$, $\mb{P}_{k}(D_{\ep}(s_0))$ tends to one as $k$ tends to infinity. \end{corollary} We shall often deal with random elements in addition to laws on the abstract metric space $(S,d)$. If $(\Omega, \scr{B}, \mb{P})$ is a probability space, then we say that $X: \Omega \rightarrow S$ is a \textit{random element of $S$}, provided $X$ is measurable. If the elements of a concrete space $S$ have a more descriptive title, then we use it to replace the word \textit{element} in this definition. For example, if $S$ were a collection of graphs, then we would refer to $X$ as a \textit{random graph}. Finally, we define the law of $X$, denoted $\scr{L}(X)$, as the probability measure on $S$, where $$ \scr{L}(X)(C):=\mb{P}(X \in C)=\mb{P}(X^{-1}(C)) $$ for each $C \in \mathcal{S}$. If $(X_{k})_{k\ge1}$ is a sequence of random elements of $S$, then we say that $X_{k}$ \textit{converges weakly} to the random element $X$ of $S$, provided $(\scr{L}(X_{k}))_{k\ge1}$ converges weakly to $\scr{L}(X)$. This definition does not require all the random elements to exist on the same probability space, though this will often be the case throughout the paper. %%%%% \section{Benjamini-Schramm convergence and the coefficient measures} Fix an integer $\mathcal{D} \ge 0$, and define $\mathcal{RG}_{\mathcal{D}}$ to be the set of all rooted undirected graphs, which are connected and have maximum degree at most $\mathcal{D}$. Formally, the elements of $\mathcal{RG}_{\mathcal{D}}$ are collections of graphs, where any two members of a fixed grouping have an isomorphism between them (this map must be root-preserving). We shall avoid using this terminology however, and instead deal directly with rooted graphs. If $(G, o)$ and $(G',o')$ are elements of $\mathcal{RG}_{\mathcal{D}}$, where $o$ and $o'$ are the roots of $G$ and $G'$ respectively, then we may define a distance between these rooted graphs. If $R \in \mb{N}_0$, we denote $B_{R}( (G,o))$ to be the subgraph of radius $R$ around the root $o$ of $G$. We typcially refer to this subgraph as the \textit{$R$-neighbourhood} of $o$. By convention, we assign $o$ to be the root of this subgraph. Let $q[ (G,o), (G',o')] := \sup\{ R \in \mb{N}_{0} | B_{R}((G,o)) \simeq B_{R}( (G',o')) \}$. If $(G,o)$ and $(G',o')$ are isomorphic, we set this value to positive infinity. We then define the metric $d$ as, \begin{equation}\label{eqn:rooted_graph_metric} d[ (G,o), (G',o')] := 2^{-q[ (G,o), (G',o')]} \end{equation} for $(G,o)$ and $(G',o')$ in $\mathcal{RG}_{\mathcal{D}}$. Notice that $\mathcal{RG}_{\mathcal{D}}$ is easily seen to be separable. Moreover, it is compact, and has the property that basic open balls are closed. These facts help us characterize weak convergence of laws on $\mathcal{RG}_{\mathcal{D}}$. Suppose that $(\lambda_k)_{k\ge 1}$ is a sequence of probability measures on $\mathcal{RG}_{\mathcal{D}}$. If $\ep \ge 0$, and $(G,o)$ is a rooted graph in $\mathcal{RG}_{\mathcal{D}}$, then we denote $D_{\ep}((G,o))$ as the rooted graphs in $\mathcal{RG}_{\mathcal{D}}$, with distance from $(G,o)$ at most $\ep$. \begin{theorem} Suppose that $\lambda$ is a distribution on $\mathcal{RG}_{\mathcal{D}}$. Then $\lambda_k$ converges weakly to $\mb{\lambda}$, if and only if for each $(G,o) \in \mathcal{RG}_{\mathcal{D}}$ and $\ep \ge 0$, $\lambda_{k}(D_{\ep}((G,o))) \xrightarrow{} \lambda(D_{\ep}((G,o)))$ as $k \xrightarrow{} \infty$. \end{theorem} Alternatively, if $R\in \mb{N}_{0}$ and $g$ is a finite rooted graph, then we can denote the event $C(g,R)$, to be the rooted graphs in $\mathcal{RG}_{\mathcal{D}}$ whose $R$-neighourhoods are isomorphic to the $R$-neighbourhood of $g$. \begin{corollary} $(\lambda_k)_{k\ge1}$ converges weakly to $\mb{\lambda}$, if and only if for each finite $g \in \mathcal{RG}_{\mathcal{D}}$ and $R \in \mb{N}_{0}$, $\lambda_{k}( C(g,R) ) \xrightarrow{} \lambda( C(g,R) )$ as $k \rightarrow \infty$. \end{corollary} While the above theorems characterize convergence of distributions of rooted graphs, we can encode non-rooted graphs as random elements of $\mathcal{RG}_{\mathcal{D}}$ to yield similar results. If $G$ is a finite graph of degree at most $\mathcal{D}$, then we can use it to build a random element of $\mathcal{RG}_{\mathcal{D}}$. This is done by specifying a probability space $(\Omega, \scr{B},\mb{P})$, and a random vertex $\alpha:\Omega \rightarrow V(G)$, such that $\alpha$ is uniformly distributed on $V(G)$. Observe then that $(G,\alpha)$ is a random element of $\mathcal{RG}_{\mathcal{D}}$, where $(G,\alpha)(\omega):=(G,\alpha(\omega))$ for each $\omega \in \Omega$. If $(G_k)_{k\ge1}$ is a sequence of finite graphs for which $|V(G_k)|\xrightarrow{} \infty$ as $k \xrightarrow{} \infty$, then we may construct a uniformly random root $\alpha_{k}$ for each graph $G_{k}$. We then say that $(G_k)_{k\ge1}$ is \textit{Benjamini-Schramm convergent}, provided $(G_k,\alpha_{k})_{k\ge1}$ converges weakly in $\mathcal{RG}_{\mathcal{D}}$. Rather, as $k \rightarrow \infty$, $\scr{L}(G_{k},\alpha_{k})$ converges to some law $\lambda$ on $\mathcal{RG}_{\mathcal{D}}$. Using the above corollary, we can characterize when Benjamini-Schramm convergence of the graph sequence $(G_{k})_{k\ge1}$ occurs. It will be convenient to assume that there is a probability space $(\Omega, \scr{B}, \mb{P})$ acting as the domain of each uniformly random root $\alpha_{k}$. This may be assumed without loss of generality, as we can always construct a probability space which functions in this way, given a sequence of random roots $(\alpha_{k})_{k\ge1}$. If $g \in \mathcal{RG}_{\mathcal{D}}$, and $R\in \mb{N}_{0}$, let us denote $B_R(G_k,\alpha_k)$ as the $R$-neighbourhood of $\alpha_k$ in $G_k$. We are concerned with the event when $\alpha_k$ has it's $R$-neighbourhood in $G_k$ isomorphic to the $R$-neighbourhood of $g$; that is, when $B_R(G_k,\alpha_k) \simeq B_R(g)$. We denote the probability of this event by $\mb{P}(B_R(G_k,\alpha_k) \simeq B_R(g))$. Formally, we have that, $$ \mb{P}(B_R(G_k,\alpha_k) \simeq B_R(g)) = \scr{L}(G_k,\alpha_k)(C(g,R)), $$ where $C(g,R)$ is the set of all graphs in $\mathcal{RG}_{\mathcal{D}}$, whose $R$-neighbourhoods are isomorphic to $g$. Using the compactness of $\mathcal{RG}_{\mathcal{D}}$, together with the above results, we have the following lemma: \begin{lemma} $(G_k)_{k\ge1}$ is \textit{Benjamini-Schramm convergent} if and only if $$ (\mb{P}(B_R(G_k,\alpha_k) \simeq B_R(g)))_{k\ge1} $$ converges for all finite $g \in \mathcal{RG}_{\mathcal{D}}$ and $R \in \mb{N}_{0}$. \end{lemma} We may generalize these results to sequences of finite random graphs as well. Let us suppose that $\mathcal{G}$ is a finite random graph on $n$-vertices with maximum degree at most $\mathcal{D}$. Rather, if $\scr{G}_{\mathcal{D}}^{n}$ is the set of all $n$-vertex graphs with maximum degree at most $\mathcal{D}$, then there is a probability space $(\Omega_{1},\scr{B}_{1},\mb{P}_{1})$, such that $\mathcal{G}: \Omega_{1} \rightarrow \scr{G}_{\mathcal{D}}^{n}$. As before, we wish to encode $\mathcal{G}$ as a random rooted graph, so we must devise a means to select a root for $\mathcal{G}$. If we assume that the random graph $\mathcal{G}$ always has the vertex set $[n]:=\{1,\ldots,n\}$, then we can build a random root for $\mathcal{G}$, by specifying an additional probability space $(\Omega_{2},\scr{B}_{2},\mb{P}_{2})$, and a map $\alpha:\Omega_{2} \rightarrow [n]$. We may once again assume that $\alpha$ is uniformly distributed on the set $[n]$. If we define $(\Omega, \scr{B},\mb{P})$ as the product space of the previous two probability spaces, then we may extend both $\mathcal{G}$ and $\alpha$ to $\Omega$ naturally. It is clear that these random elements will be \textit{independent} in this construction. That is, the selection of the root $\alpha$ is independent of whichever graph $\mathcal{G}$ takes on. We may then define the random rooted graph $(\mathcal{G},\alpha): \Omega_{1}\times \Omega_{2} \rightarrow \mathcal{RG}_{\mathcal{D}}$, where $$ (\mathcal{G},\alpha)(\omega_{1},\omega_{2}):=(\mathcal{G}(\omega_{1}),\alpha(\omega_{2})), $$ for $(\omega_{1},\omega_{2}) \in \Omega$. Of course, we are often in a situation where we are given a sequence of finite random graphs, $(\mathcal{G}_k)_{k\ge1}$, each with maximum degree at most $\mathcal{D}$, and on the vertices $[n_{k}]$ for $k \ge1$. If we know that $n_k \rightarrow \infty$ as $k$ tends to infinity, then we may define Benjamini-Schramm convergence for this sequence. In order to do so, let us assume that $\alpha_{k}$ exists on the same probability space as $\mathcal{G}_k$, and is distributed on $[n_k]$ uniformly at random. Moreover, assume that $\mathcal{G}_k$ and $\alpha_{k}$ are independent for each $k \ge1$. We thus have a sequence of random rooted graphs $(\mathcal{G}_{k},\alpha_k)_{k\ge1}$, whose weak convergence we can check. If $(\scr{L}(\mathcal{G}_{k},\alpha_k))_{k\ge1}$ converges weakly to a law $\lambda$ on $\mathcal{RG}_{\mathcal{D}}$, then we say that $(\mathcal{G}_{k})_{k \ge1}$ is \textit{Benjamini-Schramm convergent to $\lambda$}. As\,in\,the\,case\,of\,sequences\,of deterministic graphs,\,we can characterize when Benjamini-Schramm convergence occurs. It will be convenient to assume that there is an underlying probability space $(\Omega, \scr{B}, \mb{P})$, acting as the domain of each random rooted graph $(\mathcal{G}_{k},\alpha_k)$ for $k\ge1$. Such a probability space can of course be constructed, so we can assume this property without loss of generality. We now consider an integer $R\in \mb{N}_0$, and a fixed rooted graph $g \in \mathcal{RG}_{\mathcal{D}}$, where $g$ is of finite size. Suppose that $B_R(\mathcal{G}_k,\alpha_k)$ is the $R$-neighbourhood of $\alpha_k$ in $\mathcal{G}_k$. We are interested in the event in which $B_R(\mathcal{G}_k,\alpha_k) \simeq B_R(g)$. That is, when the $R$-neighbourhood of $\alpha_k$ in $\mathcal{G}_k$ is isomorphic to the $R$-neighbourhood of $g$. As above, the probability of this event is denoted by $\mb{P}(B_R(\mathcal{G}_k,\alpha_k) \simeq B_R(g))$. Formally, $$ \mb{P}(B_R(\mathcal{G}_k,\alpha_k) \simeq B_R(g)) =\scr{L}(\mathcal{G}_k,\alpha_k)(C(g,R)), $$ for all $k\ge 1$, where $C(g,R)$ is as above. Observe the following convergence criterion: \begin{lemma}\label{lem:convergence_relations} $(\mathcal{G}_k)_{k\ge1}$ is \textit{Benjamini-Schramm convergent}, if and only if $$ (\mb{P}(B_R(\mathcal{G}_k,\alpha_k) \simeq B_R(g)) )_{k\ge1} $$ converges for all finite $g \in \mathcal{RG}_{\mathcal{D}}$ and $R \in \mb{N}_{0}$. \end{lemma} \label{BS:coefficients} Now that we have reviewed Benjamini-Schramm convergence, we define a probability measure that describes the {\em relative size} of the coefficients of the rank polynomial of a graph $G$. We refer to this construction as {\em the coefficient measure} of $G$. Recall that the coefficients $\rho_{rs}$ of the rank polynomial $R_G$ were defined in equation \ref{rank:polynomial:coefficients}. The monomials of $R_G$ are in bijection with subsets of $E(G)$, where $|E(G)|=m$, hence \begin{equation} \sum_{r,s}\rho_{rs}=2^m. \end{equation} \medskip Also, for any $A\subseteq E(G)$ we have $r(G|A)\leq n-1$, and $s(G|A)\leq |A|\leq m$; where $G|A$ is the subgraph of $G$ with edge set $A$. It seems natural to consider a probability measure associated to $R_G$, defined as follows: \begin{equation}\label{measure:rank:defn} \mu_G\ :=\ \frac{1}{2^{m}}\sum_{r,s}\rho_{rs}\cdot\delta(r/n,s/m), \end{equation} By the previous remarks, $\mu_G$ is a probability measure supported on $[0,1]^2$. If we fix a point $s_{0}:=(x_0,y_0) \in [0,1]^{2}$, and take $\ep >0$, then $$ \mu_{G}(D_{\ep}(x_0,y_0))= \frac{|\{A \subseteq E(G): (r(G|A),s(G|A)) \in D_{\ep}(n\cdot x_{0}, m \cdot y_{0})\}|}{2^{m}}, $$ where the disc $D_{\ep}(\cdot)$ is defined with respect to the $\ell_{\infty}$-norm on $\mb{R}^{2}$. Moreover, by Corollary \ref{cor:metric_relations}, we know that if $\pi^{(1)}$ is the Levy-Prokhorov metric on $\Pr([0,1]^{2}, \ell_{\infty})$, then, $$ \pi^{(1)}(\mu_{G},\delta_{s_0})= \inf\{ \eta >0: \mu_{G}(D_{\eta}(s_{0})) \ge 1 - \eta \}. $$ Thus, $\mu_{G}$ is \textit{close} to the point mass $\delta_{s_0}$, provided \textit{most} of its edge subgraphs have rank and corank around $n\cdot x_{0}$ and $m \cdot y_{0}$ respectively. More precisely, if a subset of edges $\mathcal{A}$ of $G$ is chosen uniformly at random (as a random element from some probability space $(\Omega, \scr{B}, \mb{P})$), then $$ \mb{P}( (r(G|\mathcal{A})/n,s(G|\mathcal{A})/m) \in D_{\ep}(s_0)) \ge 1 - \ep, $$ if and only if, $$ \pi^{(1)}(\mu_{G},\delta_{s_0}) \le \ep. $$ In particular, if we are given a sequence of graphs $(G_k)_{k \ge1}$, for which an edge subset $\mathcal{A}_{k}$ of $G_{k}$ is sampled uniformly at random for each $k \ge1$, then we may characterize when $(\mu_{G_k})_{k \ge1}$ converges weakly to the point mass $\delta_{s_0}$. The above observations allow us to conclude the following lemma: \begin{lemma}\label{lem:rank_measure_convergence_criteria} Let $(G_{k})_{k \ge 1}$ be a sequence of graphs, and assume that there is a common probability space $(\Omega, \scr{B}, \mb{P})$, such that $\mathcal{A}_{k}$ is a random subset of edges of $G_{k}$, whose distribution is uniformly random for each $k \ge 1$. There exists a point $s_{0} \in [0,1]^{2}$, such that $(\mu_{G_{k}})_{k \ge 1}$ converges weakly to $\delta_{s_0}$, if and only if $$ \pi^{(1)}(\mu_{G_{k}}, \delta_{s_0}) \rightarrow 0 \; \text{as} \; k \rightarrow \infty. $$ If $s_{0}=(x_0,y_0)$, then this occurs, if and only if \begin{enumerate} \item $r(G|\mathcal{A}_{k})/|V(G_{k})| \rightarrow x_{0}$ as $k \rightarrow \infty$, and \item $s(G|\mathcal{A}_{k})/|E(G_{k})| \rightarrow y_{0}$ as $k \rightarrow \infty$, \end{enumerate} where we wish for weak convergence in each case. \end{lemma} %%% Let us now consider a sequence of graphs, $(G_k)_{k\ge1}$, satisfying $|V(G_k)|\to\infty$, and which is Benjamini-Schramm convergent to a law $\lambda$ on $\mathcal{RG}_{\mathcal{D}}$. In the remainder of the paper, we study the behavior of the coefficients of rank polynomials of Benjamini-Schramm convergent sequences of graphs. In order to do so, we study the weak convergence of the sequence of coefficient measures $(\mu_{G_k})_{k\ge1}$. First, we show that these coefficient measures converge. In order to prove this result, we must first prove a technical lemma. If $(G_k)_{k\ge1}$ is a sequence of finite graphs, then we can form a sequence of random graphs, $(\mathcal{G}_k)_{k\ge1}$, as follows: For each $k\ge1$, \begin{enumerate} \item Choose $\mathcal{A}_k \subseteq E(G_k)$ independently and uniformly at random. \item Set $\mathcal{G}_k$ to be $G_{k}|\mathcal{A}_k$; the subgraph of $G_k$ with edge set $\mathcal{A}_k$. \end{enumerate} \medskip We observe that $\mathcal{G}_k$ is a random graph on $|V(G_k)|$ many vertices. Moreover, it's maximal degree is guaranteed to be less than or equal to that of $G_k$. \begin{lemma}\label{lem:edge_subgraphs_convergence} If $(G_k)_{k\ge1}$ is a Benjamini-Schramm convergent sequence of graphs, then $(G_k|\mathcal{A}_k)_{k\ge1}$ is a Benjamini-Schramm convergent sequence of random graphs. \end{lemma} \begin{proof} Let $R \in \mb{N}_0$, and suppose that $g \in \mathcal{RG}_{\mathcal{D}}$ is a finite rooted graph. Recall that $\mb{P}(B_R(G_k|\mathcal{A}_k, \alpha_k) \simeq B_R(g) )$ denotes the probability that the random root $\alpha_k$ of $G_k|\mathcal{A}_k$ has it's $R$-neigbourhood isomorphic to $B_R(g)$. By Lemma \ref{lem:convergence_relations}, in order to show that Benjamini-Schramm convergence occurs, it is enough to prove that $\mb{P}(B_R(G_k|\mathcal{A}_k, \alpha_k) \simeq B_R(g))$ converges, for any choice of $R$ and $g$. Let us define $\mathcal{RG}_{\mathcal{D}}^R$ to be the rooted graphs of $\mathcal{RG}_{\mathcal{D}}$, with radius at most $R$. It is clear that $\mathcal{RG}_{\mathcal{D}}^R$ is of finite size. Moreover, we observe that if we can check that $\mb{P}(B_R(G_k|\mathcal{A}_k, \alpha_k) \simeq g)$ converges for all $g \in \mathcal{RG}_{\mathcal{D}}^R$, then the proof will be done. If we condition on what the $R$-neighbourhood of $\alpha_k$ looks like in $G_k$, then it is easy to compute the probability that $B_R(G_k|\mathcal{A}_k,\alpha_k)$ is isomorphic to $g$. In particular, we have that, \begin{equation*} \mb{P}(B_R(G_k|\mathcal{A}_k, \alpha_k) \simeq g \, | \, B_R(G_k, \alpha_k) \simeq g_0) = \frac{|\{ A\subseteq E(g_0) \, : \, B_R(g_{0}|A)\simeq g \}|}{2^{|E(g_0)|}} \end{equation*} for all $g_0 \in \mathcal{RG}_{\mathcal{D}}^R$. Thus, using these conditional probabilities, \begin{equation*} \mb{P}(B_R(G_k|\mathcal{A}_k, \alpha_k) \simeq g) = \sum_{g_0 \in \mathcal{RG}_{\mathcal{D}}^R} \frac{|\{ A\subseteq E(g_0) \, : \, B_R(g_{0}|A)\simeq g \}|}{2^{|E(g_0)|}} \, \mb{P}(B_R(G_k,\alpha_k) \simeq g_0) \end{equation*} for all $k\ge1$. Now, we know that $\mb{P}(B_R(G_k,\alpha_k) \simeq g_0)$ converges for each $g_0 \in \mathcal{RG}_{\mathcal{D}}^R$. Moreover, as $\mathcal{RG}_{\mathcal{D}}^R$ is of finite size, we have that, $$ \begin{aligned} \; & \lim_{k\xrightarrow{} \infty}\mb{P}(B_R(G_k|\mathcal{A}_k, \alpha_k) \simeq g) = \\ \; & \sum_{g_0 \in \mathcal{RG}_{\mathcal{D}}^R} \frac{|\{ A\subseteq E(g_0) \, : \, B_R(g_{0}|A)\simeq g \}|}{2^{|E(g_0)|}} \, \lim_{k\xrightarrow{} \infty} \mb{P}(B_R(G_k,\alpha_k) \simeq g_0). \end{aligned} $$ In particular, this tells us that the limit on the left hand side exists. As this is true for any $g \in \mathcal{RG}_{\mathcal{D}}^R$, the result holds. \end{proof} We are now ready to prove the main theorem of the section. This result is proven for sequences of deterministic graphs, whose roots are chosen uniformly at random. \begin{theorem}\label{BS:conv} Let $(G_i)_{i\ge1}$ be a Benjamini-Schramm convergent sequence of connected graphs, whose limiting distribution is $\lambda$. It follows that there exists a point $s_{0} \in [0,1]^{2}$, dependent only on $\lambda$, for which $(\mu_{G_i})_{i\ge1}$ converges weakly to $\delta_{s_0}$. \end{theorem} \begin{proof} We first assume that there exists an underlying probability space, $(\Omega, \scr{B}, \mb{P})$, acting as the domain of all the random elements we consider throughout the proof. In particular, let us assume that $\mathcal{A}_i$ is a subset of $E(G_i)$ chosen uniformly at random, and $\alpha_{i}$ is a root of $G_{i}$ chosen independently of $\mathcal{A}_i$ for each $i \ge 1$. We may also consider the number of connected components of $G_{i}| \mathcal{A}_{i}$, which we denote by $k(G|\mathcal{A}_{i})$ for $i \ge 1$. As the subset of edges $\mathcal{A}_{i}$ is chosen randomly, $k(G|\mathcal{A}_{i})$ is of course a random variable. Moreover, using the definitions of rank and corank, Lemma \ref{lem:rank_measure_convergence_criteria} implies that we need only show the weak convergence of $\frac{\abs{V(G_i)}-k(G_i|\mathcal{A}_i)}{\abs{V(G_i)}}$ and $\frac{\abs{\mathcal{A}_i}-\abs{V(G_i)}+k(G_i|\mathcal{A}_i)}{\abs{E(G_i)}}$ to complete the proof. We first observe that there is a fixed integer $\mathcal{D}$ acting as an upper bound on the maximum degree of each graph $G_i$, for $i \ge 1$. Moreover, as a result of the definition of Benjamini-Schramm convergence, the average degree of $G_i$ converges to some constant $d$. Next, let us consider the weak convergence of $\frac{\abs{\mathcal{A}_i}}{\abs{E(G_i)}}$. For each $i\ge1$, $\abs{\mathcal{A}_i}$ is a binomial random variable of mean $\frac{\abs{E(G_i)}}{2}$ and variance $\frac{\abs{E(G_i)}}{2}$. Thus, $\frac{\abs{\mathcal{A}_i}}{\abs{E(G_i)}}$ has mean $\frac{1}{2}$ and variance $\frac{1}{4\abs{E(G_i)}}$. Since the $G_i$ are connected, $\abs{E(G_i)}\to\infty$. Thus, the mean is constant and the variance tends to $0$ and so we have weak convergence of $\frac{\abs{\mathcal{A}_i}}{\abs{E(G_i)}}$ to $\frac{1}{2}$. We shall now prove that the random variable $\frac{k(G_i|\mathcal{A}_i)}{\abs{V(G_i)}}$ has a limit. We again use the technique of showing that the expected value converges while the variance tends to $0$. For a vertex $v$ of an arbitrary graph $H$, let $c(H,v)$ be 1 over the size of the component containing $v$ in $H$. In this case, $k(H)=\sum_{v\in V(H)}c(H,v).$ For each positive integer $R$ and graph $H$, define $k_R(H)$ to be the number of components of size less than $R$ in $H$. If we let $c_R(H,v)=c(H,v)\, \chi\left(c(H,v)>\frac{1}{R}\right)$, then we have $k_R(H)=\sum_{v\in V(H)}c_R(H,v)$. In particular, this implies \begin{equation}\label{e:kr} k(H)-\frac{|V(H)|}{R} \leq k_R(H) \leq k(H). \end{equation} Our goal will be to first show that for each $R \in \mb{N}_{0}$, $ \mb{E} \, k_{R}(G_{i}| \mathcal{A}_{i})$ converges as $i \rightarrow \infty$. It will be convenient to denote $\mathcal{G}_{i}:= G_{i} | \mathcal{A}_{i}$ for each $i \ge 1$. In this notation, $( \mathcal{G}_{i})_{i \ge 1}$ is of course a sequence of random graphs. If we consider the random root $\alpha_{i}$ of $\mathcal{G}_{i}$, then $c_{R}( \mathcal{G}_{i}, \alpha_{i})$ is a random variable for each $i \ge 1$. Observe that, $$ \mb{E} \, c_{R}( \mathcal{G}_i, \alpha_i) = \sum_{g' \in \mathcal{RG}_{\mathcal{D}}^{n}} c_{R}(g') \, \mb{P}( (\mathcal{G}_{i}, \alpha_i) \simeq g'), $$ for each $i \ge1$, where $\mathcal{RG}_{\mathcal{D}}^{n}$ is the set of all connected rooted graphs with radius at most $n$, and with maximum degree at most $\mathcal{D}$. On the other hand, it is clear that for each $g' \in \mathcal{RG}_{\mathcal{D}}^{n}$, $$ c_{R}(g')=c_{R}(B_{R}(g')), $$ as the function $c_{R}(\cdot)$ is zero, provided its rooted graph input has a component larger than $R$. As a result, the above sum simplifies to the following equation: \begin{equation}\label{eqn:BS_convergence_application} \mb{E} \, c_{R}( \mathcal{G}_i, \alpha_i) = \sum_{g \in \mathcal{RG}_{\mathcal{D}}^{R}} c_{R}(g) \, \mb{P}( B_{R}( \mathcal{G}_i, \alpha_i) \simeq g), \end{equation} \medskip for each $i \ge1$, where $\mathcal{RG}_{\mathcal{D}}^{R}$ is the set of all connected rooted graphs with radius at most $R$, and maximum degree at most $\mathcal{D}$. If we once again consider the random variable $k_{R}(\mathcal{G}_i)$, then it is clear that, $$ \frac{k_{R}(\mathcal{G}_{i})}{|V(G_i)|} = \frac{1}{|V(G_i)|} \sum_{v \in V(G_i)} c_{R}( \mathcal{G}_i, v). $$ However, the right-hand side of this equation is related to the conditional expectation of $c_{R}( \mathcal{G}_i, \alpha_i)$, given $\mathcal{A}_i$. In particular, $$ \mb{E}( c_{R}(\mathcal{G}_i, \alpha_i) | \mathcal{A}_i)= \frac{1}{|V(G_i)|} \sum_{v \in V(G_i)} c_{R}( \mathcal{G}_i, v). $$ Thus, taking expectations, \begin{align*} \mb{E}\, \left( \frac{k_{R}(\mathcal{G}_{i})}{|V(G_i)|}\right) &= \mb{E}\left( \frac{1}{|V(G_i)|} \sum_{v \in V(G_i)} c_{R}( \mathcal{G}_i, v) \right) \\ &= \mb{E}( \mb{E}( c_{R}(\mathcal{G}_i, \alpha_i) | \mathcal{A}_i)) \\ &= \mb{E} \, c_{R}( \mathcal{G}_i, \alpha_i), \end{align*} where the final line is a standard property of conditional expectations. As a result of this relation, together with equation \ref{eqn:BS_convergence_application}, $$ \mb{E} \, \left( \frac{k_{R}(\mathcal{G}_{i})}{|V(G_i)|} \right) = \sum_{g \in \mathcal{RG}_{\mathcal{D}}^{R}} c_{R}(g) \, \mb{P}( B_{R}( \mathcal{G}_i, \alpha_i) \simeq g). $$ We know that by Lemma \ref{lem:edge_subgraphs_convergence}, $(\mathcal{G}_{i})_{i \ge 1}$ is Benjamini-Schramm convergent, since the sequence $(G_i)_{i \ge 1}$ is. Thus, $\mb{P}( B_{R}( \mathcal{G}_i, \alpha_i) \simeq g)$ converges as $i \rightarrow \infty$, for each $g \in \mathcal{RG}_{D}^{R}$, as a result of Lemma \ref{lem:convergence_relations}. As the function $c_{R}(\cdot)$ is bounded and the sum on the right-hand side is finite, the limit \begin{equation}\label{eqn:BS_beta} \lim_{i \rightarrow \infty} \, \sum_{g \in \mathcal{RG}_{\mathcal{D}}^{R}} c_{R}(g) \, \mb{P}( B_{R}( \mathcal{G}_i, \alpha_i) \simeq g) \end{equation} must exist. It follows that for each $R \ge 1$, $\mb{E} \, \left( \frac{k_{R}(\mathcal{G}_{i})}{|V(G_i)|} \right)$ converges as $i \rightarrow \infty$. Let us denote this limit by $\beta_R$ for each $R \ge 1$. We shall now see how this implies the limit $\lim_{i \rightarrow \infty} \mb{E} \left( \frac{k(\mathcal{G}_{i})}{|V(G_i)|} \right) $ exists. Observe that because of equation (\ref{e:kr}), we have $$ \left|\mathbb{E}\left(\frac{k_R(G_i|\mathcal{A}_i)}{\abs{V(G_i)}}\right) - \mathbb{E}\left(\frac{k(G_i|\mathcal{A}_i)}{\abs{V(G_i)}}\right) \right| \leq \frac{1}{R}, $$ for each $R \ge 1$ and all $i \ge 1$. It follows that there exists a limit $\beta$ of $\mathbb{E}\left(\frac{k(G_i|A_i)}{\abs{V(G_i)}}\right)$, which is witnessed as $i \rightarrow \infty$. Moreover, $\beta_{R}$ converges to this limit $\beta$ as $R \rightarrow \infty$. We now need only show that $\mathrm{Var}\left(\frac{k(G_i|\mathcal{A}_i)}{\abs{V(G_i)}}\right)$ tends to 0. Fix $\epsilon>0$. We use the same $c$ and $c_R$ as above. However, since no confusion is likely to arise, we will omit the $G_i|\mathcal{A}_i$. We will also simply write $V$ for $V(G_i)$. Note that $c_R(v)\leq 1$ and $c(v)-c_R(v)<1/R$ for all vertices $v$. \begin{align*} \frac{\mathrm{Var}\left(\sum_{v\in V}c(v)\right)}{\abs{V(G)}^2}&= \frac{\mathrm{Var}\left(\sum_{v\in V}(c_R(v)+(c(v)-c_R(v)))\right)}{\abs{V(G)}^2}\\ &=\frac{\mathrm{Var}\left(\sum_{v\in V}c_R(v)\right)}{\abs{V(G)}^2}+ \frac{\mathrm{Var}\left(\sum_{v\in V}(c(v)-c_R(v))\right)}{\abs{V(G)}^2}\\ &\qquad+\frac{\mathrm{Cov}\left(\sum_{v\in V}c_R(v),\sum_{v\in V}(c_R(v)-c(v))\right)}{\abs{V(G)}^2}\\ &\leq \frac{\mathrm{Var}\left(\sum_{v\in V}c_R(v)\right)}{\abs{V(G)}^2}+ \frac{E\left[\left(\sum_{v\in V}(c(v)-c_R(v))\right)^2\right]}{\abs{V(G)}^2}\\&\qquad+ \frac{E\left[\sum_{v\in V}c_R(v)\cdot \sum_{v\in V}(c_R(v)-c(v))\right]}{\abs{V(G)}^2}\\ &\leq \frac{\mathrm{Var}\left(\sum_{v\in V}c_R(v)\right)}{\abs{V(G)}^2}+ \frac{\abs{V(G)}^2/R^2}{\abs{V(G)}^2}+\frac{\abs{V(G)}^2/R}{\abs{V(G)}^2}\\ &\leq \frac{\mathrm{Var}\left(\sum_{v\in V}c_R(v)\right)}{\abs{V(G)}^2}+\frac{2}{R} \end{align*} Choose $R$ large enough that $\frac{2}{R}<\epsilon$. The variable $c_R(v)$ is independent of $c_R(w)$ for all but $O(\abs{V(G)})$ pairs of vertices $(v,w)$. This is because there are $O(\abs{V(G)})$ pairs of vertices within distance $R$ of each other. The variance of $c_R(v)$ and the covariance of $(c_R(v),c_R(w))$ are both bounded above by 1. Thus $$ \frac{\mathrm{Var}\left(\sum_{v\in V}c_R(v)\right)}{\abs{V(G)}^2}=\frac{O(\abs{V(G)})}{\abs{V(G)}^2}=o(1) $$ and so $\displaystyle\frac{\mathrm{Var}\left(\sum_{v\in V}c_R(v)\right)}{\abs{V(G)}^2}\to 0$. Since $\abs{V(G_i)}\to\infty$ we have $$ \lim_{i\to \infty}\frac{\mathrm{Var}\left(\sum_{v\in V}c(v)\right)}{\abs{V(G)}^2}<\epsilon $$ for all $\epsilon>0$, and so $\mathrm{Var}\left(\frac{k(G_i|\mathcal{A}_i)}{\abs{V(G_i)}}\right)\to 0$. Thus, the expectation converges and the variance goes to $0$, and so $\frac{k(G_i|\mathcal{A}_i)}{\abs{V(G_i)}}\to \beta$ weakly. Putting all of these results together, we have that $\frac{r(G_i|\mathcal{A}_i)}{\abs{V(G_i)}}\to 1-\beta$ and $\frac{s(G_i|\mathcal{A}_i}{\abs{E(G_i)}}\to\frac{1}{2}-\frac{1}{2d}+\frac{\beta}{2d}$ weakly. \end{proof} In general, it may not be easy to find $\beta$. However, Section \ref{sec:generating:function} does this in the case of random regular graphs. This introduces a slight complication. The theorem is stated in the case of a sequence of deterministic Benjamini-Schramm convergent graphs. However, random regular graphs, and many other interesting Benjamini-Schramm convergent sequences, are sequences of random graphs. In this case, instead of having a sequence $(G_k)_{k\ge1}$ of graphs, one has a sequence $(\mathcal{G}_k)_{k\ge1}$ of random graphs of size $n_k$ for each $k\ge 1$. The bounded degree constraint here means that there is a constant $\mathcal{D}$, such that $\mathcal{G}_{k}$ deterministically has maximum degree at most $\mathcal{D}$ for all $k\ge1$. Our goal now will be to generalize the above theorem for certain Benjamini-Schramm convergent sequences of random graphs. We first observe that if we are given a random graph $\mathcal{G}$, the coefficient measure $\mu_{\mathcal{G}}$ is itself a random coefficient measure. In particular, if the random graph $\mathcal{G}$ exists on the probability space $(\Omega, \scr{B},\mb{P})$, then $$ \mu_{\mathcal{G}}(\omega):=\mu_{\mathcal{G}(\omega)}, $$ where $\omega \in \Omega$, and $\mu_{\mathcal{G}(\omega)}$ is the coefficient measure defined for the graph $\mathcal{G}(\omega)$. If we are given a point $s_{0} \in [0,1]^{2}$, then we may consider the distance between $\mu_{\mathcal{G}}$ and $\delta_{s_0}$, with respect to the Levy-Prokhorov metric $\pi^{(1)}$ on $\Pr([0,1]^{2})$; the space of all distributions on $[0,1]^{2}$. If we denote this distance by $\pi^{(1)}(\mu_{\mathcal{G}},\delta_{s_0})$, then this is of course a random variable, whose behaviour indicates how similar $\mu_{\mathcal{G}}$ is to $\delta_{s_0}$. If we are given a sequence of random graphs $(\mathcal{G}_{k})_{k\ge1}$, then we wish to show that for large $k$, this quantity is close to zero, \textit{most} of the time. Formally, if we assume that the random graphs $(\mathcal{G}_{k})_{k\ge1}$ exist on a common probability space, then we wish to find a point $s_{0} \in [0,1]^{2}$, such that for each $\ep > 0$, \begin{equation}\label{eqn:random_measure_convergence} \mb{P}(\pi^{(1)}(\mu_{\mathcal{G}_{k}},\delta_{s_0}) \ge \ep) \rightarrow 0 \end{equation} as $k \rightarrow \infty$. It is clear that this property directly generalizes weak convergence of coefficient measures of deterministic graphs. Moreover, we shall later verify that if we equip the space $\Pr([0,1]^{2})$ with the Levy-Prokhorov metric $\pi^{(1)}$, then the distribution $\scr{L}(\mu_{\mathcal{G}_k})$ on $\Pr([0,1]^{2})$, converges weakly to the constant $\delta_{s_0}$ of $\Pr([0,1]^{2})$, provided this property is satisfied. It turns out that property \ref{eqn:random_measure_convergence} does not hold for all Benjamani-Schramm convergent sequences of random graphs. For example, let $\mathcal{G}_k$ be a cycle of length $k$ with probability $\frac{1}{2}$ and $k$ isolated points otherwise. This sequence is easily verified to be Benjamini-Schramm convergent. On the other hand, the random coefficient measures of this sequence do not tend to a point mass; there are two distinct point masses in $\Pr([0,1]^{2})$ for which the random measures are often close to. We therefore need an additional constraint on the sequence of random graphs to ensure that this property holds. To this end, we introduce the concept of \emph{uniform} Benjamini-Schramm convergence. A sequence of random graphs in $\mathcal{RG}_{\mathcal{D}}$, denoted $(\mathcal{G}_k)_{k\ge1}$, is said to be uniformly Benjamini-Schramm convergent to a distribution $\lambda$ on $\mathcal{RG}_{\mathcal{D}}$, provided the following condition holds: If $(G_{k})_{k\ge1}$ is a sequence of graphs, for which $G_{k} \in \supp(\mathcal{G}_{k})$ for all $k\ge1$, then $(G_{k})_{k \ge1}$ is Benjamini-Schramm convergent to $\lambda$. This definition is considerably stronger than Benjamini-Schramm convergence of random graphs, and will be shown to imply property \ref{eqn:random_measure_convergence}. However, we can do slightly better. We will call a sequence of random graphs \emph{almost uniform} if for every $k\ge 1$, there is a set $U_k \in \supp(\mathcal{G}_k)$ such that, \begin{enumerate}[(i)] \item $\mb{P}(\mathcal{G}_k \in U_k) \xrightarrow{} 1$, as $k \rightarrow \infty$. \item There exists a distribution $\lambda$ on $\mathcal{RG}_{\mathcal{D}}$, for which if $(G_k)_{k\ge1}$ has $G_k \in U_k$ for all $k \ge1$, then $(G_k)_{k\ge1}$ is Benjamini-Schramm convergent to $\lambda$. \end{enumerate} We will call the $U_k$ set a \emph{uniform part} of the $\mathcal{G}_k$. This definition clearly excludes the counter example described above. We shall see how the random coefficient measures of such a sequence also satisfy property \ref{eqn:random_measure_convergence}, and thus tend to a delta function weakly. %%%%% For completeness, we first show that almost uniform Benjamini-Schramm convergence is in fact stronger than standard Benjamini-Schramm convergence. A proof of this relation isn't immediately obvious, so we review some properties of \textit{conditional distributions} of random elements before presenting the argument. Given a finite random graph $\mathcal{G}$, together with an independently chosen uniformly random root $\alpha$, let us assume that these random elements exist on the same probability space, $(\Omega, \scr{B},\mb{P})$. In this way, $(\mathcal{G},\alpha)$ is a random rooted graph of $\mathcal{RG}_{\mathcal{D}}$, whose distribution we can examine. In particular, if we know which graph $\mathcal{G}$ takes on, say $\mathcal{G}=G$, then we can consider the distribution of $(G,\alpha)$ (where $\alpha$ remains random). Formally speaking, this involves computing the \textit{conditional distribution of $(\mathcal{G},\alpha)$ given $\mathcal{G}$}, which we denote by $\mb{Q}_{(\mathcal{G},\alpha)|\mathcal{G}}$. If $\mathcal{S}$ is the sigma algebra on $\mathcal{RG}_{\mathcal{D}}$, then $\mb{Q}_{(\mathcal{G},\alpha)|\mathcal{G}}$, is a (measurable) map from $\Omega \times \mathcal{S}$ into $[0,1]$; that is, $\mb{Q}_{(\mathcal{G},\alpha)|\mathcal{G}}: \Omega \times \mathcal{S} \rightarrow [0,1]$. This conditional distribution has a number of useful properties. In particular, for each $\omega \in \Omega$, $\mb{Q}_{(\mathcal{G},\alpha)| \mathcal{G}}(\omega, \cdot)$ is a distribution on $\mathcal{RG}_{\mathcal{D}}$. Moreover, if $C \subseteq \mathcal{RG}_{\mathcal{D}}$ is measurable, then we can consider the \textit{conditional probability of the event}: $(\mathcal{G},\alpha) \in C$; denoted by $\mb{P}((\mathcal{G},\alpha) \in C| \mathcal{G})$. This is a measurable map from $\Omega$ into $[0,1]$, for which the following equation holds: $$ \mb{P}((\mathcal{G},\alpha) \in C| \mathcal{G})(\omega)=\mb{Q}_{(\mathcal{G},\alpha)|\mathcal{G}}(\omega,C), $$ for all $\omega \in \Omega$. Using the properties of conditional probabilities, this implies $$ \mb{P}((\mathcal{G},\alpha) \in C)=\int_{\omega \in \Omega} \, \mb{Q}_{(\mathcal{G},\alpha)|\mathcal{G}}(\omega,C) \, d\mb{P}(\omega). $$ Finally, the independence of $\mathcal{G}$ and $\alpha$ implies that for each $\omega_{0} \in \Omega$, $$ \mb{P}((\mathcal{G},\alpha) \in C| \mathcal{G})(\omega_0)= \mb{P}( (\mathcal{G}(\omega_0), \alpha) \in C), $$ where the graph $\mathcal{G}(\omega_0)$ is deterministic in the right-hand side equation, and the root $\alpha$ remains uniformly randomly generated. We shall use these properties in the proof of the proposition below. \begin{proposition}\label{prop:uniform_benjamini_schramm} If $(\mathcal{G}_k)_{k\ge1}$ is almost uniformly Benjamini-Schramm convergent, then it is also Benjamini-Schramm convergent in the usual sense. Moreover, the limiting distribution on $\mathcal{RG}_{\mathcal{D}}$ is the same in both cases. \end{proposition} \begin{proof} It will be convenient to assume that there is a probability space, $(\Omega,\scr{B},\mb{P})$, acting as the domain of each $(\mathcal{G}_{k}, \alpha_k)$ for $k \ge1$. As the sequence of random graphs is almost uniformly convergent, we are guaranteed the existence of subsets $(U_k)_{k \ge1}$, with the following properties: \begin{enumerate}[(i)] \item $U_k$ is contained in the support of $\mathcal{G}_k$ for all $k\ge1$. \item $\mb{P}(\mathcal{G}_k \in U_k) \xrightarrow{} 1$, as $k \xrightarrow{} \infty$. \item There exists a distribution $\lambda$ on $\mathcal{RG}_{\mathcal{D}}$, for which if $(G_k)_{k\ge1}$ has $G_k \in U_k$ for all $k \ge1$, then $(G_k)_{k\ge1}$ is Benjamini-Schramm convergent to $\lambda$. \end{enumerate} For each $k \ge 1$, we may consider the conditional distribution of $(\mathcal{G}_k,\alpha_k)$ given $\mathcal{G}_k$, denoted by $\mb{Q}_{(\mathcal{G}_k,\alpha_k)|\mathcal{G}_k}$. Formally, we have that $\mb{Q}_{(\mathcal{G}_k,\alpha_k)|\mathcal{G}_k}: \Omega \times \mathcal{S} \rightarrow [0,1]$, where $\mathcal{S}$ is the sigma algebra on $\mathcal{RG}_{\mathcal{D}}$. As a result of the observations preceding the above proposition, we know that for each subset $C \subseteq \mathcal{RG}_{\mathcal{D}}$, \begin{equation}\label{eqn:conditional_distribution_relation} \mb{Q}_{(\mathcal{G}_k,\alpha_k)|\mathcal{G}_k}(\omega_{0},C)=\mb{P}((\mathcal{G}_{k}(\omega_{0}),\alpha_{k})\in C), \end{equation} where $\omega_{0} \in \Omega$ is fixed, thus making $\mathcal{G}_{k}(\omega_0)$ a deterministic graph. The root $\alpha_{k}$ remains a uniformly random element of $[n_{k}]$. For convenience, let us define $\Lambda_{k}(\omega)$ as the probability measure $\mb{Q}_{(\mathcal{G}_k,\alpha_k)|\mathcal{G}_k}(\omega,\cdot)$, for each $\omega \in \Omega$. In this notation, $\Lambda_{k}$ is a random element of $\Pr(\mathcal{RG}_{\mathcal{D}})$. If we recall the Levy-Prokhorov metric $\pi$ on $\Pr(\mathcal{RG}_{D})$, then the quantity $\pi( \Lambda_{k}, \lambda)$ is itself a random variable for each $k\ge1$. We shall first show that for each $\ep>0$, $\mb{P}( \pi(\Lambda_{k}, \lambda) \ge \ep) \rightarrow{} 0$ as $k \rightarrow{} \infty$. In order to prove this claim, let us assume otherwise. It follows that there exists $\ep_{0}, \eta_{0} >0$, and a subsequence $(k(r))_{r\ge1}$, such that, $$ \mb{P}( \pi( \Lambda_{k(r)}, \lambda) \ge \ep_{0} ) \ge \eta_{0} $$ for all $r \ge 1$. We also observe that there exists some $k_{0} \ge1$, such that for all $k \ge k_{0}$, $$ \mb{P}( \mathcal{G}_{k} \in U_{k} ) \ge 1 - \eta_{0}. $$ Using the union bound, it follows that there exists some $r_{0} \ge1$, such that $$ \mb{P}( \mathcal{G}_{k(r)} \in U_{k(r)} \; \text{and} \; \pi( \Lambda_{k(r)}, \lambda) \ge \ep_{0}) >0, $$ for all $r \ge r_{0}$. By the probabilistic method, there is a point $\omega^{*} \in \Omega$, such that \begin{enumerate} \item $\mathcal{G}_{k}(\omega^{*})$ is in $U_k$ for all but finitely many $k$, \smallskip \item $\pi( \Lambda_{k}(\omega^{*}), \lambda) \ge \ep_{0}$ for infinitely many $k$. \end{enumerate} In light of property $(1)$, we know that $(\mathcal{G}_{k}(\omega^*))_{k\ge1}$ must be Benjamini-Schramm convergent to $\lambda$, as consequence of the uniform convergence of $(\mathcal{G}_{k})_{k\ge1}$. In other words, $\scr{L}(\mathcal{G}_{k}(\omega^{*}),\alpha_k)$ converges to $\lambda$, as $k \rightarrow \infty$. On the other hand, we know that, $$ \Lambda_{k}(\omega^{*}) = \scr{L}(\mathcal{G}_{k}(\omega^{*}),\alpha_{k}) $$ for each $k \ge1$, as a result of equation \ref{eqn:conditional_distribution_relation}. Thus, $\pi(\Lambda_{k}(\omega^{*}),\lambda) \rightarrow 0$ as $k \rightarrow \infty$. This contradicts property $(2)$, so the claim must hold. We now know that for each $\ep >0$, we have that $\mb{P}( \pi(\Lambda_{k}, \lambda) \ge \ep) \xrightarrow{} 0$ as $k \rightarrow \infty$. Our goal now is to show that $\pi( \scr{L}(\mathcal{G}_k,\alpha_k), \lambda)$ converges to zero. This will complete the proof, as the metric $\pi$ characterizes weak convergence of distributions on $\mathcal{RG}_{\mathcal{D}}$. Observe that we may relate $\scr{L}(\mathcal{G}_k,\alpha_k)$ to $\Lambda_{k}$ in the following way: For each $C \subseteq \mathcal{RG}_{\mathcal{D}}$, \begin{align*} \mb{P}((\mathcal{G}_k,\alpha_k) \in C) &= \int_{\omega \in \Omega} \, \mb{Q}_{(\mathcal{G}_k,\alpha_k)|\mathcal{G}_k}(\omega,C) \, d\mb{P}(\omega) \\ &= \int_{\omega \in \Omega}\, \Lambda_{k}(\omega)(C) \, d\mb{P}(\omega). \end{align*} Let us now fix $\ep > 0$. For each $k \ge 1$, we partition the space $\Omega$ into $(\Omega_{1}^{k}, \Omega_{2}^{k})$, where $$ \Omega_{1}^{k}:=\{\omega \in \Omega: \pi(\Lambda_{k}(\omega), \lambda) < \ep \}, $$ and $\Omega_{2}^{k}:= \Omega \setminus \Omega_{1}^{k}$. Since the metric $\pi$ is bounded above by $1$, the above equations imply that, \begin{align*} \mb{P}((\mathcal{G}_k,\alpha_{k}) \in C) &= \int_{\omega_{1} \in \Omega_{1}^{k}} \Lambda_{k}(\omega_{1})(C) \, d\mb{P}(\omega_{1})+ \int_{\omega_{2} \in \Omega_{2}^{k} } \Lambda_{k}(\omega_{2})(C) \, d\mb{P}(\omega_{2}) \\ &\le (\lambda(C^\ep) + \ep) \, \mb{P}( \pi(\Lambda_{k}, \lambda) < \ep) + \mb{P}( \pi(\Lambda_{k},\lambda) \ge \ep), \end{align*} for each measureable set $C \subseteq \mathcal{RG}_{\mathcal{D}}$. On the other hand, if $\eta >0$, then there exists $k_{1}\ge1$, such that $\mb{P}( \pi(\Lambda_{k}, \lambda) \ge \ep) \le \eta$ for all for $k \ge k_{1}$. Thus, for each $k \ge k_{1}$, we have that, $$ \mb{P}((\mathcal{G}_k,\alpha_{k}) \in C) \le (\lambda(C^\ep) + \ep) + \eta, $$ for all $C \subseteq \mathcal{RG}_{\mathcal{D}}$. This implies that, $$ \pi( \scr{L}(\mathcal{G}_{k},\alpha_{k}), \lambda) \le \ep + \eta, $$ for all $k \ge k_1$, by definition of the metric $\pi$. As $\eta, \ep > 0$, were arbitrary, this implies that $\pi( \scr{L}(\mathcal{G}_{k},\alpha_{k}), \lambda)$ converges to zero as $k \rightarrow \infty$. It follows that $(\mathcal{G}_k)_{k\ge1}$ is Benjamini-Schramm convergent to the distribution $\lambda$, thus completing the proof. \end{proof} While it is clear almost uniform Benjamini-Schramm convergence is strictly stronger than regular Benjamini-Schramm convergence, there is a partial converse to the above proposition. Unlike before, this claim requires information regarding the limiting distribution of the sequence of random graphs. \begin{proposition}\label{prop:convergence_to_fixed_graph} Suppose that we are given a Benjamini-Schramm convergent sequence of random graphs, say $(\mathcal{G}_{k})_{k\ge1}$, which converges to the distribution $\lambda$ on $\mathcal{RG}_{\mathcal{D}}$. If we assume that $\lambda$ is of the form $\delta_{\Gamma}$ for some rooted graph $\Gamma \in \mathcal{RG}_{\mathcal{D}}$, then this sequence is almost uniformly Benjamini-Schramm convergent to the fixed graph $\Gamma$. \end{proposition} \begin{proof} Let us assume that the sequence of random graphs $(\mathcal{G}_{k})_{k\ge1}$ exist on a common probability $(\Omega, \scr{B},\mb{P})$. We may consider the metric $d$ defined on the space $\mathcal{RG}_{\mathcal{D}}$ (see equation \ref{eqn:rooted_graph_metric}), together with the Levy-Prokhorov metric $\pi$ defined on $\Pr(\mathcal{RG}_{\mathcal{D}},d)$. If the random graphs $(\mathcal{G}_{k})_{k \ge1}$ are Benjamini-Schramm convergent to a fixed rooted graph $\Gamma$, then we know that for each $k \ge1$, $$ \pi( \scr{L}(\mathcal{G}_k,\alpha_k), \delta_{\Gamma})= \inf\{\eta >0: \mb{P}((\mathcal{G}_k,\alpha_k) \in D_{\eta}(\Gamma)) \ge 1 - \eta\} $$ by Lemma \ref{prop:metric_relations}. This observation, together with the definition of $d$, guarantees the existence of a sequence of positive integers, $(R_{k})_{k\ge1}$, for which \begin{enumerate}\label{eqn:convergence_to_fixed_graph} \item $\mb{P}(B_{R_k}(\mathcal{G}_k,\alpha_k) \simeq B_{R_k}(\Gamma)) \rightarrow 1$ as $k \rightarrow \infty$, and \item $R_{k} \rightarrow \infty$ as $k \rightarrow \infty$. \end{enumerate} For each $k \ge 1$, we may consider the conditional probability of the event $B_{R_k}(\mathcal{G}_{k},\alpha_{k}) \simeq B_{R_k}(\Gamma)$, given $\mathcal{G}_{k}$. This is a (measurable) map from $\Omega$ into $[0,1]$, denoted $\mb{P}(B_{R_k}(\mathcal{G}_{k},\alpha_{k}) \simeq B_{R_k}(\Gamma)| \mathcal{G}_{k})$, which satisfies the following property: $$ \mb{P}(B_{R_k}(\mathcal{G}_k,\alpha_k) \simeq B_{R_k}(\Gamma)) = \int_{\omega \in \Omega} \mb{P}(B_{R_k}(\mathcal{G}_{k},\alpha_{k}) \simeq B_{R_k}(\Gamma)| \mathcal{G}_{k})(\omega) \, d\mb{P}(\omega), $$ For convenience, let us define the function $f_{k}: \Omega \rightarrow [0,1]$, where $$ f_{k}(\omega):=\mb{P}(B_{R_k}(\mathcal{G}_{k},\alpha_{k}) \simeq B_{R_k}(\Gamma)| \mathcal{G}_{k})(\omega) $$ for each $\omega \in \Omega$. We observe that, $$ \| f_{k}-1 \|_{1} \rightarrow 0 $$ when $k \rightarrow \infty$, as a result of the preceding equations. On the other hand, the $\ell_{1}$-convergence of the functions $(f_{k})_{k \ge 1}$ guarantees their weak convergence as well. That is, there exists a sequence of positive reals $(\ep_{k})_{k\ge1}$, for which \begin{enumerate} \item $\mb{P}( \{ \omega \in \Omega: |f_{k}(\omega)-1| \ge \ep_{k} \}) \le \ep_{k}$ for all $k \ge 1$, and \item $\ep_{k} \rightarrow 0$ as $k \rightarrow \infty$. \end{enumerate} Let us now define the subset $W_{k} \subseteq \Omega$, where $$ W_{k}:=\{ \omega \in \Omega: |f_{k}(\omega)-1| \ge \ep_{k} \}, $$ for each $k \ge 1$. If we now fix $\omega_{0} \in \Omega$ and $k\ge1$, then we may consider the distribution of $(\mathcal{G}_{k}(\omega_{0}),\alpha_{k}))$, where the graph $\mathcal{G}_{k}(\omega_0)$ is fixed, and $\alpha_{k}$ remains a uniformly random root of $\mathcal{G}_{k}(\omega_{0})$. We observe that $$ \mb{P}(B_{R_k}(\mathcal{G}_{k}(\omega_0),\alpha_{k}) \simeq B_{R_k}(\Gamma)) = \mb{P}(B_{R_k}(\mathcal{G}_{k},\alpha_{k}) \simeq B_{R_k}(\Gamma)| \mathcal{G}_{k})(\omega_0). $$ If we additionally assume that $\omega_{0} \in W_{k}$, then $$ \mb{P}(B_{R_k}(\mathcal{G}_{k}(\omega_0),\alpha_{k}) \simeq B_{R_k}(\Gamma)) \ge 1 - \ep_{k}. $$ Combining this equation together with Lemma \ref{prop:metric_relations} and the definition of the metric $d$, implies that $$ \pi( \scr{L}(\mathcal{G}_{k}(\omega), \alpha_{k}), \delta_{\Gamma}) \le \max\{ \ep_{k}, \frac{1}{2^{R_{k}}}\}, $$ for each $\omega \in W_{k}$. Let us now define $U_{k}:= \mathcal{G}_{k}(W_{k})$ for each $k \ge 1$. It is clear that the sets, $(U_{k})_{k \ge 1}$, satisfy the following properties: \begin{enumerate} \item If $k\ge1$, then for each $G_{k} \in U_{k}$, $\pi(\scr{L}(G_{k}, \alpha_k), \delta_{\Gamma}) \le \max\{ \ep_{k}, \frac{1}{2^{R_{k}}}\}$. \item $\mb{P}( \mathcal{G}_{k} \in U_{k}) \rightarrow \infty$ as $k \rightarrow \infty$. \end{enumerate} As the metric $\pi$ characterizes weak convergence of distributions on $\mathcal{RG}_{\mathcal{D}}$, we know that these properties ensure the almost uniform Benjamini-Schramm convergence of $(\mathcal{G}_{k})_{k \ge1}$ to the fixed graph $\Gamma$. This completes the proof. \end{proof} We now verify that almost uniform Benjamini-Schramm convergence is enough to guarantee property \ref{eqn:random_measure_convergence}. As before, we denote $\Pr([0,1]^{2})$ as the set of probability measures on the unit square, and $\pi^{(1)}$ as the Levy-Prokhorov metric on this space. \begin{theorem}\label{thm:almost_uniform_convergence} Let $(\mathcal{G}_k)_{k\ge1}$ be an almost uniformly Benjamini-Schramm convergent sequence of random graphs. There exists some $s_0$ in $[0,1]^2$, such that for each $\ep > 0$, $$ \mb{P}( \pi^{(1)}( \mu_{\mathcal{G}_k}, \delta_{s_0}) \ge \ep ) \rightarrow 0 $$ as $k \rightarrow \infty$. \end{theorem} \begin{proof} The proof of this theorem uses similar ideas to that of Proposition \ref{prop:uniform_benjamini_schramm}. We once again assume that the sequence $(\mathcal{G}_k)_{k\ge1}$ exists on the probability space $(\Omega, \scr{B},\mb{P})$. As the sequence of random graphs is almost uniformly convergent, we are guaranteed the existence of subsets $(U_k)_{k \ge1}$, with the following properties: \begin{enumerate}[(i)] \item $U_k$ is contained in the support of $\mathcal{G}_k$ for all $k\ge1$. \item $\mb{P}(\mathcal{G}_k \in U_k) \xrightarrow{} 1$, as $k \xrightarrow{} \infty$. \item There exists a distribution $\lambda$ on $\mathcal{RG}_{\mathcal{D}}$, for which if $(G_k)_{k\ge1}$ has $G_k \in U_k$ for all $k \ge1$, then $(G_k)_{k\ge1}$ is Benjamini-Schramm convergent to $\lambda$. \end{enumerate} Let $(G_k)_{k\ge1}$ be any sequence of graphs satisfying the third property. We observe that by Theorem \ref{BS:conv}, there is some $s_0$ in $[0,1]^2$, depending only on $\lambda$, such that $(\mu_{G_k})_{k \ge1}$ is convergent to $\delta_{s_0}$. We wish to show that the statement of the theorem holds for this particular choice of $s_0$. Suppose there is some $\ep_{0} > 0$, for which this is \textit{not} the case. This implies that there exists a subsequence, $(k(r))_{r\ge1}$, and $\eta_{0} > 0$ such that, $$ \mb{P}(\pi^{(1)}( \mu_{\mathcal{G}_{k(r)} }, \delta_{s_0})) \ge \ep_{0}) \ge \eta_{0} $$ for all $r\ge1$. Let us choose $k_0\ge 1$, such that for all $k \ge k_0$, we have that $\mb{P}(\mathcal{G}_k \in U_k) > 1 - \eta_{0}$. We can then find some $r_0 \ge 1$ satisfying, $$ \mb{P}(\mathcal{G}_{k(r)} \in U_{k(r)} \; \text{and} \; \pi^{(1)}( \mu_{\mathcal{G}_{k(r)} }, \delta_{s_0} ) \ge \ep) > 0 $$ for all $r \ge r_0$. Using the probabilistic method, we are guaranteed the existence of some $\omega^{*} \in \Omega$ for which, if $G_{k}^{*}:=\mathcal{G}_{k}(\omega^{*})$ for each $k \ge1$, then \begin{enumerate} \item $G_{k}^{*} \in U_k$ for all but finitely many $k\ge1$, \item $\pi^{(1)}( \mu_{G_{k}^*},\delta_{s_0}) \ge \ep$ for infinitely many $k\ge1$. \end{enumerate} We may trivally alter $(G_{k}^{*})_{k\ge1}$ in such a way that property $(1)$ holds for all $k \ge1$, without affecting property $(2)$. This yields a sequence of graphs, for which $(\mu_{G_{k}^{*}})_{k\ge 1}$ does \textit{not} converge to $\delta_{s_0}$. On the other hand, we know that $G_k^{*} \in U_k$ for all $k \ge 1$, so $(G_k^{*})_{k\ge1}$ must be Benjamini-Schramm convergent to $\lambda$ by property $(iii)$. Thus, according to Theorem \ref{BS:conv}, $\mu_{G_{k}^{*}}$ should converge to $\delta_{s_0}$ as $k \rightarrow \infty$. This yields a contradiction, so the statement of the theorem must hold for all $\ep >0$. \end{proof} We conclude this section with some additional results on the behaviour of certain coefficient measures. In particular, we show that if $(\mathcal{G}_{k})_{k\ge1}$ is a sequence of almost uniformly convergent random graphs, then Theorem \ref{thm:almost_uniform_convergence} implies a particular weak convergence of their random coefficient measures, $(\mu_{\mathcal{G}_k})_{k\ge1}$. Let us suppose once more that the sequence of random graphs, $(\mathcal{G}_{k})_{k\ge1}$, exists on a common probability space $(\Omega,\scr{B},\mb{P})$. As we previously saw, each random coefficient measure $\mu_{\mathcal{G}_k}$ is a map from $\Omega$ into the metric space $(\Pr([0,1]^{2}), \pi^{(1)})$. This implies that the law of $\mu_{\mathcal{G}_k}$, denoted $\scr{L}(\mu_{\mathcal{G}_k})$, is a distribution on $(\Pr([0,1]^{2}),\pi^{(1)})$ for each $k \ge1$. Using our previous notation, the set of all distributions on $(\Pr([0,1]^{2}),\pi^{(1)})$ is denoted by $\Pr( \Pr([0,1]^2), \pi^{(1)})$. We shorten this to $\Pr^{(2)}( [0,1]^2)$ for convenience. By definition, $\scr{L}(\mu_{\mathcal{G}_k}) \in \Pr^{(2)}( [0,1]^2)$ for each $k\ge1$. Moreover, a constant in this space is a fixed distribution on $[0,1]^{2}$ (an element of $\Pr([0,1]^{2})$). Our goal is to show that there exists a point $s_{0} \in [0,1]^{2}$, such that $\scr{L}(\mu_{\mathcal{G}_{k}})$ converges weakly to the constant $\delta_{s_0}$ as $k \rightarrow \infty$. While we could prove this claim by working directly with continuous bounded functions on $(\Pr([0,1]^{2}),\pi^{(1)})$, it is easier to recognize that $(\Pr([0,1]^{2}),\pi^{(1)})$ is separable, and so the weak convergence of elements of $\Pr^{(2)}( [0,1]^2)$ is metrizable by Theorem \ref{thm:metrizability}. In particular, we may use the Levy-Prokhorov metric for distributions on $\Pr([0,1]^{2})$, denoted $\pi^{(2)}$, towards these ends. \begin{corollary}\label{cor:almost_uniform_implies_weak_convergence} Let $(\mathcal{G}_{k})_{k \ge1}$ be a sequence of almost uniformly Benjamini-Schramm random graphs. There exists some $s_{0} \in [0,1]^{2}$, such that $(\mu_{\mathcal{G}_k})_{k\ge1}$ converges weakly to the constant $ \delta_{s_0}$. \end{corollary} \begin{proof} Let $\ep >0$. As consequence of Theorem \ref{thm:almost_uniform_convergence}, we know that, $$ \mb{P}( \pi^{(1)}( \mu_{\mathcal{G}_k}, \delta_{s_0}) \ge \ep) \rightarrow 0, $$ as $k \xrightarrow{} \infty$, for some $s_{0} \in [0,1]^{2}$. Now, $\scr{L}(\mu_{\mathcal{G}_k})$ is a probability measure on $( \Pr( [0,1]^2), \pi^{(1)})$ for all $k \ge 1$, and $\delta_{s_0}$ is a fixed element of $\Pr( [0,1]^2)$. Thus, by Corollary \ref{cor:metric_relations}, we know that $(\scr{L}(\mu_{\mathcal{G}_k}))_{k\ge1}$ converges weakly to the constant $\delta_{s_0}$. In the language of random elements, $(\mu_{\mathcal{G}_k})_{k\ge1}$ converges weakly to the constant $\delta_{s_0}$, thus completing the proof. \end{proof} The final two corollaries assume the same properties of the sequence $(\mathcal{G}_{k})_{k \ge1}$ as in Corollary \ref{cor:almost_uniform_implies_weak_convergence}. \begin{corollary} There exists a positive sequence, $(\ep_{k})_{k\ge1}$, such that, \begin{enumerate} \item $\mb{P}( \pi^{(1)}( \mu_{\mathcal{G}_{k} },\delta_{s_0}) ) \ge \ep_k ) \le \ep_k$ \item $\pi^{(2)}(\scr{L}(\mu_{\mathcal{G}_{k}}), \delta_{s_0}) = \ep_k$ \end{enumerate} for all $k \ge 1$. Moreover, $\ep_k$ tends to zero as $k \rightarrow \infty$. \end{corollary} \begin{proof} For each $k \ge 1$, set $\ep_k := \pi^{(2)}(\scr{L}(\mu_{\mathcal{G}_{k}}), \delta_{s_0})$. Since $(\scr{L}(\mu_{\mathcal{G}_k}))_{k \ge1}$ converges weakly to the constant $\delta_{s_0}$, we know that $\ep_k \xrightarrow{} 0$, as $k \xrightarrow{} \infty$. By Proposition \ref{prop:metric_relations}, it follows that $$ \pi^{(2)}(\scr{L}(\mu_{\mathcal{G}_{k} }), \delta_{s_0} ) = \inf\{ \eta > 0 \, | \, \mb{P}( \pi^{(1)}( \mu_{\mathcal{G}_k}, \delta_{s_0}) \ge \eta) \le \eta \} $$ for each $k \ge1$. Moreover, as the probability measure $\scr{L}(\mu_{\mathcal{G}_{k}})$ is discrete for all $k \ge 1$, we can always witness this infimum. The result thus holds. \end{proof} We remark that we can also consider the Wasserstein metric on $\Pr^{(2)}([0,1]^2)$. We shall denote this metric by $W^{(2)}$. \begin{corollary} We have that, $$ \ep_k^2 \le W^{(2)}(\scr{L}(\mu_{\mathcal{G}_k}),\delta_{s_0}) \le (2 - \ep_k) \ep_k $$ for all $k \ge 1$. \end{corollary} \begin{proof} The statement is immediate from Proposition \ref{prop:metric_relations} \end{proof} \begin{remark} The quantity, $W^{(2)}(\scr{L}(\mu_{\mathcal{G}_k}),\delta_{s_0})$, encodes the average distance between $\mu_{ \mathcal{G}_k}$ and $\delta_{s_0}$, with respect to metric $\pi^{(1)}$. This seems like a natural metric to use if we wish to study the rate at which coefficient measures converge for various graph sequences. \end{remark} \section{Generating functions for the number of components in random subgraphs of random regular graphs} \label{sec:generating:function} An example of Benjamini-Schramm convergent sequences of random graphs is that of random regular graphs. In this section we will show that they are almost uniformly convergent and thus apply Theorem \ref{thm:almost_uniform_convergence} to them. We then use generating functions to determine the location of the delta function to which the coefficient measures are tending. For this section, let $G(n,d)$ denote the set of all $d$-regular graphs on $n$ vertices. \begin{lemma}\label{nbhd} For any integer radius $R$, $\epsilon>0$ and constant degree $d$, there is an $N$ such that for $n\geq N$ and $\mathcal{G}$ selected uniformly at random from $G(n,D)$, the probability that more than $n\epsilon$ vertices of $G$ will have a cycle contained in their ball of radius $R$ is at most $\epsilon$. \end{lemma} \begin{proof} First of all, we know that for any vertex $v$ of a $d$-regular graph $\mathcal{G}$, $\abs{B_{R}(\mathcal{G},v)}\leq \sum_{t=0}^{R}d^t\leq d^{R+1}$ since this would be the size of a tree with this degree rooted at $v$. Hence, $B_{R}(\mathcal{G},v)$ cannot contain cycles of length more than $d^{R+1}$ and we may ignore such long cycles. The number of cycles of a given length in a random regular graph of size $n$ is asymptotically Poisson with finite mean and variance. Let $C_l(G)$ be the number of cycles of length at most $l$ in $G$. The sum of Poisson random variables has finite mean and variance so $C_{l}(\mathcal{G}_n)$, where each $\mathcal{G}_n$ is uniformly random from $G(n,d)$, can be controlled with Markov's inequality. Let $l=d^{R+1}$. Then there is an $M$ such that $\lim_{n\to \infty}\P(C_{l}(\mathcal{G}_n)>M)<\frac{\epsilon}{2}$. Hence there is an $N_1$ such that for all $n>N_1$, $\P(C_{l}(\mathcal{G}_n)>M)<\epsilon$. Suppose now $C_l(\mathcal{G})\leq M$. Then there are at most $lM$ vertices in cycles shorter than $l$. If $B_{R}(\mathcal{G},v)$ contains an entire cycle, then it must contain an element of a cycle of length at most $l$. This is the same as saying that $v\in B_{R}(\mathcal{G},w)$ where $w$ is in a cycle of length at most $l$. Since there are at most $lM$ such $w$ and a ball of radius $R$ contains at most $l$ vertices, there are at most $l^2M$ vertices whose ball of radius $R$ contains an entire cycle. Moreover, $l$ and $M$ do not depend on $n$, so we can choose $N_2$ large enough that $N_2\epsilon>l^2 M$. Thus, $N=\max(N_1,N_2)$ satisfies the statement of the lemma. \end{proof} This lemma clearly implies that $G(n,d)$ with the uniform distribution is Benjamini-Schramm convergent to an infinite $d$-regular tree. As the limiting distribution is a fixed graph, we are guaranteed almost uniform Benjamini-Schramm convergence as well, by Proposition \ref{prop:convergence_to_fixed_graph}. We may thus apply Theorem \ref{thm:almost_uniform_convergence} to conclude that the random coefficient measures of this sequence tend to a point mass. A closer examination of the proof of Theorem \ref{BS:conv} tells us where we should expect this point mass be be centered. Clearly, the average degree will be the constant degree $d$. The tricky part is to find the value of $\beta$. For this, recall how $\beta$ is the limit of equation \ref{eqn:BS_beta} as $R \rightarrow \infty$, as seen in the proof of Theorem \ref{BS:conv}. As the limiting probability of having a tree neighbourhood is 1 for any radius $R \ge1$, it suffices to find the expected inverse of component size of the root of a $d$-regular infinite tree, where each edge is removed (independently) with probability $\frac{1}{2}$. This expectation will be precisely be equal to $\beta$. For convenience, let us now set $k:=d-1$. \begin{definition}\label{def:generating:function} Randomly select a subset of the edges of an infinite rooted $(k+1)$-regular tree by randomly and independently including each edge with probability $1/2$. Let $g(x)=\sum_{j=1}^{\infty}a_jx^j$ be the function such that for small $j$, $a_j$ is the probability that the component of the root has size $j$. Let $f$ be an analogous generating function except for the infinite tree where the root only has $k$ children. \end{definition} The following are standard results on Galton-Watson trees. We include the proofs for completeness. First, we obtain a recurrence relation for $f$ by adding a layer at the root. The new root can have from $0$ to $k$ children. Each of these will have a certain number of descendants with probabilities given by coefficients of $f$. Furthermore, we have added one vertex to our tree. Thus we have \begin{equation}\label{e:frecursion} f(x)=x\frac{(1+f(x))^k}{2^k}. \end{equation} Similarly, $$ g(x)=x\frac{(1+f(x))^{k+1}}{2^{k+1}}=\frac{1}{2}(1+f(x))f(x). $$ \begin{lemma} The expected value of $1$ over size of the component of the root in a random subset of a an infinite $(k+1)$-regular tree is $\frac{1}{2}\left(f(1)-\frac{k-1}{2}f(1)^2\right)$. When $k=2$, $f(1)=1$ and when $k\geq 3$, $f(1)$ is the unique solution to $2^kp=(1+p)^k$ in the interval $(0,1)$. \end{lemma} \begin{proof} If $g$ has power series $\sum_{j=1}^{\infty}a_jx^j$, then the expected number of components is $n\sum_{j=1}^{\infty}\frac{1}{j}a_j$. Multiplying the terms by $x^j$ yields the power series for \begin{equation}\label{def:K} K(x)=\int_{0}^{x}\frac{g(t)}{t}dt \end{equation} To compute this, implicitly differentiate the recurrence relation for $f$ and simplify by the same relation. \begin{align*} f'(x)&=\frac{(1+f(x))^k}{2^k}+kxf'(x)\frac{(1+f(x))^{k-1}}{2^k}\\ f'(x)&=\frac{f(x)}{x}+kf'(x)\frac{f(x)}{1+f(x)}\\ f'(x)\left(1-k\frac{f(x)}{1+f(x)}\right)&=\frac{f(x)}{x}\\ f'(x)\left(1+f(x)-kf(x)\right)&=\frac{(1+f(x))f(x)}{x}\\ \frac{d}{dx}\left(f(x)-\frac{k-1}{2}(f(x))^2\right)&=2\frac{g(x)}{x} \end{align*} Thus, by the fundamental theorem of calculus, and since $f(0)=0$, \begin{equation}\label{K:formula} K(x)=\frac{1}{2}\left(f(x)-\frac{k-1}{2}(f(x))^2\right) \end{equation} Thus the expected number of components is \[\frac{1}{2}\left(f(1)-\frac{k-1}{2}f(1)^2\right)\] We now compute $p=f(1)$. This is the total probability that a component of the root of the $(k+1)$-regular tree will have finite size. Thus it lies in the interval $[0,1]$. It solves the equation $2^kp=(1+p)^k$. For $k=2$, the only solution is $p=1$. For $k\geq 3$, we claim there are two solutions in the interval. Indeed, $\frac{d}{dp}\left((1+p)^k-2^kp\right)=k(1+p)^{k-1}-2^k$ which is an increasing function when $p\geq 0$. When $p=0$, the derivative evaluates to $k-2^k<0$. When $p=1$, it evaluates to $k2^{k-1}-2^k>0$. Thus the derivative has precisely one root in $(0,1)$. By Rolle's theorem, this means that $(1+p)^k-2^kp$ has at most 2 roots in $[0,1]$. It has one root at $p=1$ which it approaches from below. $(1+0)^k-2^k\cdot0=1>0$ and so by the intermediate value theorem on $[0,1+\epsilon]$, $(1+p)^k-2^kp$ has at least one root in $(0,1)$. Combining this upper bound from Rolle's theorem, we have that there is precisely one $p\in(0,1)$ satisfying $(p+1)^k=2^kp$. The coefficients of $f$ are non-negative, and so $f$ is increasing. Also $f(0)=0$ and $f$ is continuous. By (\ref{e:frecursion}), $f(1)$ must be one of the roots. I claim it is the smaller of the two roots. Indeed, suppose it were not, then by the intermediate value theorem there is an $x\in (0,1)$ such that $f(x)$ is the smaller root. Thus we have $f(x)=x\frac{(1+f(x))^k}{2^k}$ and $(1+f(x))^k=2^kf(x)$. Substituting the second equation into the first yields $f(x)=xf(x)$. However, this is a contradiction since $x<1$ and $f(x)>0$, proving the claim. This incidentally means that, with positive probability, the random tree is infinite when $k\geq 3$. \end{proof} Recall that the degree of the graph is $k+1$. The generating functions $f(x)$ and $g(x)$ were defined in \ref{def:generating:function}. \begin{definition}\label{def:beta} We thus have $\beta=\beta(k+1)$ given by the formula $\beta=K(1)$, where the function $K(x)$ was defined in \ref{def:K} and computed in \ref{K:formula}. \end{definition} The values of $\beta$ are given in a table below: \[\begin{array}{c|c|c} k & p & \beta\\ \hline 2 & 1 & \frac{1}{4}\\ \hline 3 & \sqrt{5}-2 & \frac{5\sqrt{5}-11}{2}\\ \hline 4 & \approx 0.087378 &\approx 0.03796 \end{array}\] We may then apply Theorem \ref{thm:almost_uniform_convergence}, and the proof of Theorem \ref{BS:conv} to obtain convergence to a specific delta function. \begin{corollary} Let $\mathcal{G}_n \in G(n,d)$ be chosen uniformly at random. The sequence of random coefficient measures $(\mu_{\mathcal{G}_n})_{n\ge1}$ defined in equation \ref{measure:rank:defn}, converge weakly as $n\to\infty$ to the $\delta$-measure $$ \delta\left(1-\beta,\frac{2(\beta-1)}{d}+\frac{1}{2}\right), $$ where $\beta=\beta(d),d=k+1$ was defined in Definition \ref{def:beta}. \end{corollary} %%%%%% %%%% \section{Further questions} The questions considered in this paper can be formulated for different classes of graphs. It seems interesting to consider planar graphs; for example, every knot can be represented using its planar projections, giving rise to $4$-regular planar graphs. However, regular planar graphs are quite different from random regular graphs; in particular, as $|E(G)|< 3|V(G)|$ for every non-null planar graph $G$ $d$-regular planar graphs only exist for $d \leq 5.$ Also, random $3$-regular planar graphs are typically {\em not} $3$-connected. The probability that a random $3$-regular planar graph is $3$-connected is exponentially small in the number of vertices; we refer to \cite[Thm 6.4.1]{Kang} for precise asymptotics of that probability. Similar results hold for $d>3$. Accordingly, Theorem \ref{rank:Newton:triangle} does not apply for random planar regular graphs. Also, the number of spanning trees in random regular planar graphs grows slower \cite{JR,Lyons} than in general regular graphs \cite{McKay}. It would be interesting to study the limiting shapes of the Newton polygons, and the limiting distribution of the coefficient measures for random planar regular graphs (and more generally for random planar graphs of bounded degree). It seems interesting to extend our results to the Tutte polynomial. (The Tutte polynomial of graph $G$ can be defined from the rank polynomial by $$T_G(x,y)=(x-1)^{-n+1}R_G(x-1,y-1).$$ It also seems very interesting to explore in more detail the restrictions of the $2$-variable polynomials considered in this paper to some specific curves; and to study the distribution of the corresponding zeros, e.g. of the chromatic polynomials, or of Alexander polynomial of a random knot, considered in \cite{Rivin16}. We remark that the {\em expected value} of $T_G$ for subgraphs obtained by randomly deleting edges from $G$ were considered in \cite[Thm 6.3]{Welsh}. It seems interesting to study the limiting distribution of zeros of $R_G$ (or, equivalently, $T_G$), considered as subsets of $\reals^2$ and $\C^2$. This question is further explored in \cite{JLMRT}. We remark that the convergence of root measures for the rank and Tutte polynomials (as measures defined on $\reals$ or $\C$) was discussed in several papers, including \cite{CsFr} and \cite{Sokal}. %%% \begin{thebibliography}{1} \bibitem[Big1]{biggs} N. Biggs. {\em Algebraic Graph Theory}. Cambridge Mathematical Library. Cambridge University Press, Cambridge, Second Edition, 1993. %\bibitem[Big2]{biggs2} N. Biggs. {\em Algebraic potential theory on graphs.} Bull. London Math. Soc. 29(6) (1997), 641--682. %\bibitem[BDS]{BDS} N.L. Biggs, R.M. Damerell, D.A. Sands. {\em Recursive families of graphs.} J. Combin. Theory B 12 (1972), 123--131. \bibitem[BC]{BC} F.T. Boesch and S. Chen. {\em A generalization of line connectivity and optimally invulnerable graphs.} SIAM Jour. Appl. Math. 34, No. 4 (1978), 657--665. \bibitem[Bol]{Bollobas} B. Bollob\'{a}s. {\em Random Graphs} Cambridge studies in advanced mathematics. Cambridge University Press, Cambridge, Second Edition, 2001. %\bibitem[BCKL]{BCKL} C. Borgs, J.. Chayes, J. Kahn, and L. Lov\'asz, {\em Left and right convergence of graphs with bounded degree.} Random Structures \& Algorithms 42 (2013), 1--28. %\bibitem[CS]{CS} S-C. Chang and R. Shrock. {\em Tutte polynomials and related asymptotic limiting functions for recursive families of graphs.} Adv. in Appl. Math. 32 (2004), 44--87. %\bibitem[Chung]{chung} F.R.K. Chung. Spectral Graph Theory. CBMS Regional Regional Conference Series in Mathematics, 92. AMS, 1997. %\bibitem[C-V]{CostelloVu} K. Costello and V. Vu. {\em The rank of random graphs.} Random Structures and Algorithms, 33(3) (2008), 269--285. \bibitem[CsFr]{CsFr} P. Csikv\'ari and P. E. Frenkel. {\em Benjamini--Schramm continuity of root moments of graph polynomials.} European Journal of Combinatorics 52, Part B (2016), 302--320. \bibitem[G-R]{GR} C.D. Godsil and G. Royle. {\em Algebraic Graph Theory.} Springer, 2013. \bibitem[Gol80]{Gol80} D. L. Goldsmith, On the second order edge-connectivity of a graph, Congressus Numerantium 29 (1980), 479--484. \bibitem[Gol81]{Gol81} D.L. Goldsmith, On the nth order edge-connectivity of a graph, Congressus Numerantium 32 (1981), 375--382. %\bibitem[Gros]{grossman} J. Grossman, D. Kulkarni, M. Devadatta, I. Schochetman. {\em Algebraic graph theory without orientation.} Proceedings of the 3rd ILAS Conference (Pensacola, FL, 1993). Linear Algebra Appl. 212/213 (1994), 289--307. \bibitem[JR]{JR} D. Jakobson and I. Rivin. {\em Extremal metrics on graphs I}, Forum Math. 14(1), (2002), 147--163. \bibitem[JLMRT]{JLMRT} D. Jakobson, T. Langsetmo, M. Medeiros Charbonneau, I. Rivin and L. Turner. {\em Rank and Bollobas-Riordan Polynomials: Coefficient Measures and Zeros.} In preparation. \bibitem[Kan]{Kang} M. Kang. {\em Random Planar Structures and Random Graph Processes.} Habilitationsschrift, Humboldt-Universit\"at zu Berlin, 2007. \url{http://edoc.hu-berlin.de/habilitationen/kang-mihyun-2007-07-20/PDF/kang.pdf} %\bibitem[Kun]{Kung} J. Kung. {\em Preface: Old and New Perspectives on the Tutte Polynomial.} Annals of Combinatorics 12 (2008), 133--137. %\bibitem[LFH]{LFH} Y. Liao, A. Fang and Y. Hou. {\em The Tutte polynomial of an infinite family of outerplanar, small-world and self-similar graphs.} Physica A 392 (2013), 4584--4593. \bibitem[Ly]{Lyons} R. Lyons. {\em Asymptotic Enumeration of Spanning Trees.} Combinatorics, Probability and Computing 14 (2005), 491--522. %\bibitem[Man]{Mani} A. Mani. {\em On some Tutte polynomial sequences in the square lattice.} Journal of Combinatorial Theory, Series B 102 (2012) 436--453. \bibitem[McK]{McKay} B. McKay. {\em Spanning trees in regular graphs.} European J. Combin. 4 (1983), no. 2, 149--160. %\bibitem[Pal]{Palmer} E. M. Palmer. {\em On the spanning tree packing number of a graph: a survey.} Discrete Mathematics 230 (2001) 13--21. %\bibitem[Riv14]{Rivin14} I. Rivin. {\em Spectral Experiments+} Experimental Mathematics, Volume 25, Issue 4, (2016), 379--388. \bibitem[Riv16]{Rivin16} I. Rivin. {\em Random space and plane curves.} arXiv:1607.05239 %\bibitem[RT]{RT} I. Rivin and L. Turner. {\em Tutte Polynomials for Random Regular %Graphs: Experiments.} With an Appendix by M. Medeiros Charbonneau, I. Rivin and %L. Turner. In preparation. \bibitem[Sok]{Sokal} A. Sokal. {\em Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions.} Combin. Probab. Comput., 10 (1) (2001), pp. 41--77. %\bibitem[Tut]{Tutte} W. T. Tutte. {\em On dichromatic polynomials.} Jour. of Comb. Theory 2 (1967), 301--320. \bibitem[Wel]{Welsh} D. Welsh. {\em The Tutte Polynomial.} Random Structures and Algorithms, (1999), 210--228. %\bibitem[Wor]{Wormald} N.C. Wormald. {\em The asymptotic connectivity of labelled regular graphs.} J. Combin. Theory Ser. B 31 (1981), 156--167. \bibitem[ZHLS]{ZHLS} L. Zhang, K. Hennayake, H.-J. Lai and Y. Shao. {\em A lower bound on the $l$-edge connectivity and optimal graphs.} Jour. of Combinatorial Mathematics and Combinatorial Computing 66 (2008), 79--95. \end{thebibliography} \end{document}