%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 k<j< n$, we have 
\begin{equation}\label{k-connectivity:1}
\conn_j\geq \frac{(j-1)(j-k+1)}{(j+1)(j-k-1)}\conn_{j-k}
\end{equation}
A special case is $\conn_j\geq \conn_{j-1}j(j-1)/[(j+1)(j-2)]$.  
Also, it was shown in \cite[Theorem 2]{BC} that if $G$ has minimum degree $\delta$, 
$1\leq k<n$ and $\conn_2(G)\geq\lfloor n/k\rfloor$, then $\conn_k(G)\geq\delta$.  
It was also shown in \cite[Corollary 4]{BC} that for a $d$-regular graph containing an 
$i$-clique $K_i$, for $d\geq in/(i+1)$ we have $\conn_{i+1}=di
-\frac{i(i-1)}{2}$.  
It was also shown in \cite[Theorem 2.5]{ZHLS} that for $n\geq l>1$, 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}







