0

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?

Community
  • 1
theQman
  • 1,097

1 Answers1

0

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.

Misha Lavrov
  • 142,276
  • This perfectly answers my question. Thank you! In my experience, these sort of little details tend to be rushed over in most texts on random graphs, making it difficult for me to learn. Is there some text or reference you would recommend? – theQman Mar 17 '17 at 23:41
  • I learned random graphs from an earlier version of https://www.math.cmu.edu/~af1p/BOOK.pdf but it was supplemented by actual teaching. So I don't know how well it holds up on its own, but having one more reference can't possibly hurt. – Misha Lavrov Mar 17 '17 at 23:51
  • Thanks for the reference. Now that I understand the contents of the definition, I think I am still missing the big picture: what exactly does this definition have to do with sparsity? – theQman Mar 18 '17 at 02:30
  • 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 02:43