LMS-EPSRC | Eventually Almost Everywhere

Continuing the LMS-EPSRC summer school on Random Graphs, Geometry and Asymptotic Structure, we’ve now had three of the five lectures by Mathew Penrose on Geometric Random Graphs.

The basic idea is that instead of viewing a graph entirely abstractly, we now place the vertices in the plane, or some other real space. In many network situations, we would expect connectivity to depend somehow on distance. Agents or sites which are close together might be considered more likely to have the sort of relationship indicated by being connected with an edge. In the model discussed in this course, this dependence is deterministic. We have some parameter r, and once we have chosen the location of all the vertices, we connect a pair of vertices if the distance between them is less than r.

For the purposes of this, we work in a compact space [0,1]^d, and we are interested in the limit as the number of vertices n grows to infinity. To avoid the graph getting too connected, as in the standard random graph model, we take r to be a decreasing function of n. Anyway, we place the n points into the unit hypercube uniformly at random, and then the edges are specified by the adjacency rule above. In general, because r_n will be o(1), we won’t have to worry too much above boundary effects. The number of vertices within r_n of the boundary of the cube will be o(1). For some results, this is a genuine problem, when it may be easier to work on the torus.

In G(n,p), the order of np in the limit determines the qualitative structure of the graph. This is the expected degree of a given fixed vertex. In this geometric model, the relevant parameter is $nr_n^d$ , where d is the dimension of the hypercube. If this parameter tends to 0, we say the graph is sparse, and dense if it tends to infinity. The intermediate case is called a thermodynamic limit. Note that the definition of sparse here is slightly different from G(n,p).

Much of the content of the first three lectures has been verifying that the distributions of various quantities in the graph, for example the total number of edges, are asymptotically Poisson. Although sometimes arguments are applicable over a broad spectrum, we also sometimes have to use different calculations for different scaling windows. For example, it is possible to show convergence to a Poisson distribution for the number of edges in the sparse case, from which we get an asymptotic normal approximation almost for free. In the denser regimes, the argument is somewhat more technical, with some substantial moment calculations.

A useful tool in these calculations are some bounds derived via Stein’s method for sums of ‘almost independent’ random variables. For example, the presence or non-presence of an edge between two pairs of vertices are independent in this setting if the pairs are disjoint, and the dependence is still only mild if they share a vertex. An effective description is via a so-called dependency graph, where we view the random variables as the vertices of a graph, with an edge between them if there is some dependence. This description doesn’t have any power in itself, but it does provide a concise notation for what would otherwise be very complicated, and we are able to show versions of (Binomials converge to Poisson) and CLT via these that are exactly as required for this purpose.

In particular, we are able to show that if $E_n$ is the total number of edges, under a broad set of scaling regimes, if $\lambda_n$ is the expected total number of edges, then $d_{TV}(E_n,\mathrm{Po}(\lambda_n))\rightarrow 0$ , as n grows. This convergence in total variation distance is as strong a result as one could hope for, and when the sequence of $\lambda_n$ is O(1), we can derive a normal approximation as well.

At this point it is worth discussing an alternative specification of the model. Recall that for a standard homogenous random graph, we have the choice of G(n,m) and G(n,p) as definitions. G(n,m) is the finer measure, and G(n,p) can be viewed as a weighted mix of G(n,m). We can’t replicate this directly in the geometric setting because the edges and non-edges are a deterministic function of the vertex locations. What we can randomise is the number of vertices. Since we are placing the vertices uniformly at random, it makes sense to consider as an alternative a Poisson Point Process with intensity n. The number of vertices we get overall will be distributed as Po(n), which is concentrated near n, in the same manner as G(n,c/n).

As in G(n,p), this is a less basic model because it is a mixture of the fixed-vertex models. Let’s see if how we would go about extending the total variation convergence result to this slightly different setting without requiring a more general version of the Poisson Approximation Lemma. To avoid having to define everything again, we add a ‘ to indicate that we are talking about the Poisson Point Process case. Writing d(.,.) for total variation distance, the result we have is:

$\lim_{n\rightarrow\infty} d(E_n,\mathrm{Po}(\lambda_n))=0.$

We want to show that

$\lim_{n\rightarrow\infty}d(E_n',\mathrm{Po}(\lambda_n'))=0,$

which we can decompose in terms of expectations in the original model by conditioning on $N_n$

$\leq \lim_{n\rightarrow\infty}\mathbb{E}\Big[\mathbb{E}[d(E_{N_n},\mathrm{Po}(\lambda_n')) | N_n]\Big],$

where the outer expectation is over N. The observation here, is that the number of points given by the Poisson process induces a measure on distributions, the overwhelming majority of which look quite like Poisson distributions with parameter n. The reason we have a less than sign is that we are applying the triangle inequality in the sum giving total variation distance:

$d(X,Y)=\sum_{k\geq 0}|\mathbb{P}(X=k)-\mathbb{P}(Y=k)|.$

From this, we use the triangle inequality again:

$\lim_{n\rightarrow\infty} \mathbb{E}\Big[\mathbb{E}[d(E_{N_n},\mathrm{Po}(\lambda_{N_n})) | N_n]\Big]$

$+\lim_{n\rightarrow\infty}\mathbb{E}\Big[\mathbb{E}[d(\mathrm{Po}(\lambda_{N_n}),\mathrm{Po}(\lambda_n')) | N_n]\Big].$

Then, by a large deviations argument, we have that for any $\epsilon>0$ , $\mathbb{P}(|N_n-n|\geq \epsilon n)\rightarrow 0$ exponentially in n. Also, total variation distance is, by definition, bounded above by 1. In the first term, the inner conditioning on N_n is irrelevant, and we have that $E_{N_n}$ converges to the Poisson distribution for any fixed $N_n\in (n(1-\epsilon),n(1+\epsilon))$ . Furthermore, we showed in the proof of the non-PPP result that this convergence is uniform in this interval. (This is not surprising – the upper bound is some well-behaved polynomial in 1/n.) So with probability $1- e^{-\Theta(n)}$ N_n is in the region where this convergence happens, and elsewhere, the expected TV distance is bounded below 1, so the overall expectation tends to 0. With a similar LD argument, for the second term it suffices to prove that when $\lambda\rightarrow\mu$ , we must have $d(\mathrm{Po}(\lambda),\mathrm{Po}(\mu))\rightarrow 0$ . This is ‘obviously’ true. Formally, it is probably easiest to couple the distributions $\mathrm{Bin}(n,\lambda/n),\mathrm{Bin}(n,\mu/n)$ in the obvious way, and carry the convergence of TV distance as the parameter varies through the convergence in n.

That all sounded a little bit painful, but is really just the obvious thing to do with each term – it’s only the language that’s long-winded!

Anyway, I’m looking forward to seeing how the course develops. In particular, when you split the space into small blocks, the connectivity properties resemble those of (site) percolation, so I wonder whether there will be concrete parallels. Also, after reading about some recent results concerning the metric structure of the critical components in the standard random graph process, it will be interesting to see how these compare to the limit of a random graph process which comes equipped with metric structure for free!

I’m in Birmingham this week for the LMS-EPSRC summer school on Random Graphs, Geometry and Asymptotic Structure. The event consists of three five-hour mini-courses, a plenary lecture, leaving plenty of time for problem sheet and discussion. I thought it would be worth trying to say a couple of interesting things each day – I do not know whether this will succeed, but I might as well try.

Today, a few thoughts on the first two lectures of Michael Krivelevich’s course on Long Paths and Hamiltonicity in Random Graphs. The aim is to develop tools to investigate the threshold for the presence of a Hamiltonian cycle in G(n,p). In this first part of the course, we were mainly thinking about long paths.

One tool we used a lot was the Depth-First Search algorithm. This is very similar to the exploration process I’ve talked about before. Essentially, here we consider trying to explore the graph in a depth-first way, but instead of viewing all the edges incident to a vertex we have just arrived at, we only look to see whether there is an edge out of the new vertex. If there is, we explore it, then come back eventually to look for more. It really comes down to a difference in the information we are storing. In this DFS, we store the vertices which we haven’t finished exploring, which is the set of vertices on the explored path between the root and the current vertex. So the size of this set evolves like the contour process. In particular, we can read off the sizes of paths from this description. These dynamics are useful in particular because we know there are no edges between the set of vertices we have finished exploring, and the ones we have yet to explore. The stack of ‘processing’ vertices must glue everything else together.

We can translate one of the arguments back into the language for the old exploration process. Recall the increments of the exploration process are $\mathrm{Bin}(\alpha n,\frac{c}{n}) -1$ once we have explored $\alpha n$ vertices. We don’t need to worry about the -1 bit for now. Observe that because we are exploring in a depth-first way, if a subsequence of the Binomial variables of length k are all positive, this corresponds to a path of length (k-1).

So to prove, for example, that the longest path in a subcritical random graph is O(log n), it suffices to prove that there are O(log n) consecutive positive entries in the sequence of n binomial entries. Since the distribution changes continuously, it is convenient to prove that there are O(log n) consecutive positive entries in the first $\epsilon n$ binomial entries. The probability that any of these entries is positive is bounded below by some p, so it suffices to consider instead a sequence of Bernoulli RVs with parameter p. So if we never have clog n consecutive, this gives control of the sequence of geometric random variables corresponding to the gaps between 0s in the sequence. Precisely, these are Geom(q), and we must have $\frac{\epsilon n}{c\log n}$ of them independently being less than clog n. We have to chase a few constants, and use the fact that if $f(n)\rightarrow\infty, \frac{g(n)}{f(n)}\rightarrow\infty$ , then

$(1-\frac{1}{f(n)})^{g(n)}\rightarrow 0,$

by comparison with the standard asymptotic result for $e^{-x}$. In any case, we get that this probability tends to 0 if we choose c small enough, and so with high probability there is a path of length clog n.

This is interesting, because we knew already that the largest component in a subcritical random graph had size O(log n). But we also knew that all the components were trees, or ‘almost trees’, and were uniformly chosen from the set of trees (or trees + an edge or two) with appropriate size. And the largest path in a UST on n vertices is $O(n^{1/2})$ with high probability. So we learn that there are enough components of size $\geq c\log n$ that it is actually very probable that one of them will have the unlikely property of being much more path-like than a typical tree.

Krivelevich also showed a pleasant elementary proof of the result that a supercritical random graph has a path of length O(n), using a similar idea.

The other definition of major interest was an expander graph. Often when doing calculations about neighbourhoods of sets of vertices, we run into the problem that the neighbourhoods may overlap, and so we cannot get the total outer neighbourhood (or outer boundary) just by summing over the individual neighbourhood sizes. In an expander graph, we demand that all small sets of vertices have neighbourhood at least as large as some constant multiple of the set size, essentially giving us a bound on the above problem. Concretely, G is a $(k,\alpha)$ -expander is for any set of vertices $|U|\leq k, |N(U)|\geq \alpha |U|$ .

There’s a very nice argument using Posa’s lemma, where we consider all the possible ways to rearrange the vertices in some longest path into a different longest path, and then focus on the endpoints of all these paths. With this so-called rotation-extension technique, we can show that a (k,2)-expander has a path of length at least 3k-1.

There are structural similarities between expander graphs and regular graphs, so it seems natural that there will be some interesting spectral properties. I don’t know much about this, but perhaps it will come up later in the week. But, returning to the random graph long path problem, it now suffices to show subcritical G(n,p) is a (clog n,2)-expander for some c. Expander properties are in some sense the opposite of clustering properties, and independence of a RG inhibit most clustering properties (as discussed in much greater detail in some of the posts about network models). Unfortunately, this doesn’t actually work, as in a subcritical graph, the typical expansion coefficient, even of a small set will be c, for G(n,c/n), which is not large enough. However, if you chose the constants carefully, such an argument should work for c>2, so long as you chose k=an, with a small enough that the probability of a vertex elsewhere in the graph being joined to (at least) two of the k vertices in the set, was small compared with (c-2).

REFERENCES

The course notes are not available, though chapter 3 from these 2010 notes by the same lecturer are related and interesting.

How much is the stacks project graph like a random graph? (quomodocumque.wordpress.com)
Welcome to Random Graphs and Complex Networks, T-79.7003 (randomgraphsaalto.wordpress.com)
Some old and new problems in combinatorics and geometry (gilkalai.wordpress.com)
The Binomial Distribution (squstat.wordpress.com)
Karger min cut problem (teacode.wordpress.com)
recent work on social networks and politics (orgtheory.wordpress.com)

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Tag Archives: LMS-EPSRC

Characterisations of Geometric Random Graphs

Long Paths and Expanders

Related articles