# Sparse graph seqeunces and deterministic distribtuions.

In these notes on p. 12, a sparse sequence of graphs is defined as follows:

A graph sequence $(G_n)_{n \ge 1}$ is sparse if $\lim_{n \to \infty}P^{(n)}_k = p_k \;\;\; (k \ge 0)$, where $P^{(n)}_k$ is the proportion of vertices of degree $k$ in $G_n,$ and $p_k$ is some deterministic probability distribtuion.

I'm a bit confused about the deterministic distribution part. Is this a distribution that has support at only a single point? If so, does this imply that a sparse graph sequence is one whose degree distribution converges to that of a regular graph?

Can someone please shed some light on these ideas?

No, the distribution given by the values of $p_k$ does not have to be concentrated on a single point or satisfy any particular properties.
The reason for the word "deterministic" is that in general, we're going to apply this definition not to any fixed sequence of graphs, but to a sequence of random graphs: for each $n$, $G_n$ is a graph-valued random variable with some specified distribution. So $P_k^{(n)}$ is also a random variable, and $P_k^{(n)} \to p_k$ is supposed to mean that as $n \to \infty$, the distribution of $P_k^{(n)}$ converges to the deterministic value $p_k$.
For example, if we take $G_n$ to be the Erdős–Rényi random graph $\mathcal G_{n,1/n}$, then in the limit as $n \to \infty$, $P_k^{(n)} \to p_k = \frac{e^{-1}}{k!}$, which is a deterministic value, not a random variable. So this is a sparse sequence.
For a highly-contrived non-example, if we flip a coin for each $G_n$, and take it to be either the empty graph or a cycle on $n$ vertices with equal probability, then as $n \to \infty$, $P_0^{(n)}$ and $P_2^{(n)}$ each converge to $\operatorname{Bernoulli}(\frac12)$ random variables. This is not a deterministic value of $p_k$, so this is not a sparse sequence.
• The definition is a mix of establishing sparsity and establishing convergence. The sparsity comes from the fact that if the values $p_0, p_1, p_2, \dots$ actually represent a probability distribution (and therefore sum to $1$) then the typical vertex in $G_n$ has only constant degree, which makes for a very sparse graph. (More precisely, we could prove things like: "For any $\epsilon>0$ we have constants $N, k$ such that if $n>N$, then at least $(1-\epsilon)n$ vertices of $G_n$ have degree less than $k$.") – Misha Lavrov Mar 18 '17 at 2:43