Long Paths and Expanders

Posted on by
Reply

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.

Related articles

The Chinese Restaurant Process

Posted on by
1

A couple of months ago I wrote a post about Polya’s Urn, the simplest example of self-reinforcing process. Recall that we have a bag containing black and white balls, and sequentially we draw a ball then replace it together with an additional ball of the same colour. The process is self-reinforcing in the sense that if there is a surplus of black balls, the dynamics will reinforce this by adding more black balls than white balls. Alternatively, you can think of a natural limit process when the number of balls is large, for which any distribution is an invariant distribution. We have seen models such as the Preferential Attachment dynamics for network creation, where the degrees of vertices clearly have this self-reinforcing property. New vertices are more likely to join to existing vertices with large degrees.

One difference between the Polya Urn and some of the models we might be interested in for applications is that for the urn model, the number of classes (in this context colours of balls) is fixed. In many applications, we will want to allow new classes to appear. In the process which follows, we will allow this, and the new classes will have initial size equal to 1, so will be at a disadvantage for the self-reinforcing dynamics. Nonetheless, some will show up in a meaningful way in the limit. It is worth emphasising that Polya’s Urn gave us the Dirichlet distribution in the limit, and this can be thought of as a partition of [0,1]. These more general processes will give us a more interesting family of partitions, called the Poisson-Dirichlet distributions. These will turn up in a wide variety of contexts, and this is perhaps the friendliest way to introduce them.

The model is this. We start with a single diner who sits at the first table. Then whenever the (n+1)th diner arrives, they join a table with k diners already with probability k/n+1, and they start a new table with probability 1/n+1.

(Aside: I’m not exactly sure how this relates to a Chinese restaurant? It seems more reminiscent of a university dining hall during freshers’ week, but I guess that would be a less catchy name for a model.)

Anyway, the interest in this description lies not in organising seating arrangements. Consider choosing uniformly at random from the set of permutations on [n+1]. Suppose x maps to n+1 and n+1 maps to y. Consider taking the permutation of [n] formed by instead mapping x to y and ignoring n+1. This has the uniform distribution on the set of permutations of [n]. By reversing this procedure, we can construct a uniform permutation of [n+1] from a uniform permutation of [n]. When you do this as a process for n growing, observe that the orbits correspond exactly to tables in the Chinese Restaurant Process. If we wanted the CRP to give all the information about the permutation, we could specify the ordering round each table, by saying that with probability 1/n+1 the new diner sits to the left of any given existing diner.

As a starting point for why this is a useful description of the uniform permutation distribution, observe that the size of the component containing the element 1 evolves as a Polya Urn with initial vector (1,1). The second 1 in the initial vector corresponds to the possibility of starting a new table, which is maintained at every stage. This tells us immediately that as n grows to infinity, the proportion of elements in the same cycle as 1 in the uniform permutation converges in distribution to U[0,1]. The construction also allows for an easy proof that the expected number of cycles is roughly log n for large n, since on each pass of the process, the probability that there is a new cycle formed is 1/k.

In this case, the partition induced on [n] by the process is clearly exchangeable given our permutation description. However, this will turn out to hold in greater generality. Note also,, that conditional on the size of the cycle containing 1, the sizes of the remaining cycles are given by a uniform permutation on a smaller number of elements. So the limiting result holds jointly in the first k cycle sizes for all k. More precisely, if (N_1,N_2,\ldots) are the cycle sizes ordered by least element, then the frequencies converge to:

(U_1,(1-U_1)U_2,(1-U_1)(1-U_2)U_3,\ldots),

where the Us are independent U[0,1] RVs. This is known as a stick-breaking procedure, where at each step we break off some proportion of the stick according to a fixed distribution, and assemble the pieces into a partition.

We generalise this process to get a two-parameter version. The standard notation for the parameters is (\alpha,\theta). Then we amend the dynamics. We now have to take into account how many tables are occupied when the (n+1)th diner arrives. If k tables are occupied, and the ith table has n_i diners, then the new one will join this table with probability \frac{n_i-\alpha}{n+\theta}, and will start a new table otherwise, so with probability \frac{\theta+k\alpha}{n+\theta}. The original process therefore corresponds to parameters (0,1).

First we examine which parameters are possible. If \alpha<0, and m|\alpha|<\theta<(m+1)|\alpha|, then with high probability the (m+1)th table will eventually be occupied, whereafter the probability of forming a further table will be negative. So we have to demand instead that \theta is an integer multiple of -\alpha. Then the number of tables is bounded by this multiple, so for large n, the probability of joining one of the k (fixed) tables is roughly \frac{n_i}{n}, so this should behave roughly like the standard Polya Urn. And indeed, the induced frequencies do converge to the Dirichlet distribution with k equal parameters.

Obviously \alpha cannot be greater than 1, otherwise the probability of the second diner joining the first table is negative. If it is equal to 1, then every diner starts a new table, which isn’t very interesting. So we care about \alpha\in[0,1), and for the probability of the second diner starting a new table to be non-negative we require \theta>-\alpha.

It turns out that the partitions induced by this process are exchangeable also. We also have a stick-breaking construction, although now the broken proportions are not IID, but distributed as

U_i\sim \mathrm{Beta}(1-\alpha,\theta+i\alpha),

with the same notation otherwise. It turns out that under mild assumptions, these are all the infinite exchangeable random partitions with this stick-breaking property.

My initial struggle with this process was to understand what roles (\alpha,\theta) played in a more precise way. It turns out this is best explained through the limit of the partition, but Pitman’s Exercise 3.2.2 does at least give an idea of how such a process with parameters (1/2,0) might naturally arise as a version of an urn model.

3.2.2. Let an urn initially contain two balls of different colours. Draw 1 is a simple draw from the urn with replacement. Thereafter, balls are drawn from the urn, with replacement of the ball drawn, and addition of two more balls as follows. If the ball drawn is of a colour never drawn before, it is replaced together with two additional balls of two distinct new colours, different to the colours of balls already in the urn. Whereas if the ball drawn is of a colour that has been drawn before, it is replaced together with two balls of its own colour.

Let n_1 be the number of times a ball of the colour of the first ball drawn (and replaced) is drawn. Let $n_2,n_3,\ldots$ be the number of times balls of each other colour are drawn. Suppose after n draws, we have drawn k colours. (There will be other colours in the bag not yet drawn.) Then, for each drawn colour i, there are 2n_i-1 balls of that colour in the bag, giving 2n-k in total. But there should be 2n balls in total, so there are k other balls. Then the probability that we see a new colour is k/2n, and the probability that we see colour i again is $\latex \frac{2n_i-1}{2n}=\frac{n_i-1/2}{n}$, which exactly corresponds to the dynamics for PD(1/2,0).

The other question I was puzzled by initially is where does the dust come from in the limit? Recall that in an infinite exchangeable partition, the sum of the frequencies does not need to be 1. The difference between this sum and 1 gives the probability that an element is in a block by itself. Obviously, when the number of tables is bounded (as when \alpha<0) this is not an issue, but for positive \alpha, this won’t hold. So we need to account for these singletons. The temptation is to imagine that these correspond to tables which are started but never joined. But this use of ‘never’ is not ideal. For each k, the k-th table will eventually include arbitrarily large numbers of diners. But for any finite n, there will likely be some proportion of people dining alone, some in pairs, and so on. So the sum of all of these proportions in the limit gives this dust.

Generalising Polya’s Urn in another direction, if I have time, I might write something about a model which I recently read about on arXiv where the classes are vertices of a graph, and there is dependence between them based on the presence of edges. This might also be a good moment to explain some other generalisations and stochastic approximation methods used to treat them.

REFERENCES

This post is almost entirely a paraphrase of Sections 3.1 and 3.2 from Pitman’s Combinatorial Stochastic Processes, available online here.

Related articles
Enhanced by Zemanta

Random Interlacements

Posted on by
Reply

In this post, I want to talk about another recently-introduced model that’s generating a lot of interest in probability theory, Sznitman’s model of random interlacements. We also want to see, at least heuristically, how this relates to more familiar models.

We fix our attention on a lattice, which we assume to be \mathbb Z ^d. We are interested in the union of an infinite collection of simple random walks on the lattice. The most sensible thing to consider is not a collection of random walks from at a random set of starting points, but rather a family of trajectories, that is a doubly-infinite random walk defined on times (-\infty,\infty). We will want this family to have some obvious properties, such as translation invariance, in order to make analysis possible and ideally obtain some 0-1 laws. The natural thing to do is then to choose the trajectories through a Poisson Point Process. The tricky part will be finding an intensity measure that has all the properties we want, and gives trajectories that genuinely do look like SRWs, and, most importantly, have a union that is neither too sparse nor too dense. For example, it wouldn’t be very interesting if with high probability every point appeared in the union…

For reasons we will mention shortly, we are interested in the complement of the union of the trajectories. We call this the vacant set. We will find an intensity which we can freely scale by some parameter u\in\mathbb{R}^+, which will give us a threshold for the complement to contain an infinite component. This is in the same sense as the phase transition for Bernoulli percolation. That is, there is a critical value u^* say, such that for u<u^* the vacant set contains an infinite component (or percolates) almost surely, and almost surely it does not when u>u^*. A later result of Teixeira shows that, as in percolation, this infinite component is unique.

Let us first recall why it is not interesting to consider this process for d=1 or 2. On \mathbb{Z}, with high probability a single SRW hits every integer point trivially, since it visits arbitrarily large and arbitrarily small integers. For d=2, the SRW is recurrent, and so consists of a countably infinite sequence of excursions from (0,0). Note that the probability that an excursion from 0 hits some point (x,y) is non-zero, as it is at least 2^{-2(|x|+|y|)} for example. Therefore, with high probability the SRW hits (x,y), and so whp it hits every point.

Therefore it is only for d=>3 that we start seeing interesting effects. It is worth mentioning at this point some of the problems that motivated considering this model. First is the disconnection time of a discrete cylinder by a simple walk. For example, Sznitman considers the random walk on \mathbb{Z}\times (\mathbb{Z}/N\mathbb{Z})^d. Obviously, it is more interesting to consider how long it takes a (1-dimensional in the natural sense) path to disconnect a d=>3 dimensional set than a 2-dimensional one, as the latter is given just by the first time the path self-intersects.

More generally, we might be interested in random walks up to some time an order of magnitude smaller than the cover time. Recall the cover time is the time to hit each point of the set. For example, for the random walk on the d-dimensional torus (\mathbb{Z}/N\mathbb{Z})^d the cover time (as discussed in Markov Chains and Mixing Times posts) is N^d \log N, but the log N represents in some sense only the ‘final few’ vertices. So we should ask what the set of unhit vertices looks like at time N^d. And it turns out that for large N, the structure of this vacant set is related to the vacant set in the random interlacement model, in a local sense.

Anyway, the main question to ask is: what should the intensity measure be?

We patch it together locally. Start with the observation that transience of the random walk means almost surely a trajectory spends only finitely many steps in a fixed finite set K. So we index all the trajectories which hit K by the first time they hit K. Given that a trajectory hits K, it is clear what the conditional distribution of this hitting point should be. Recall that SRW on Z^d is reversible, so we consider the SRW backwards from this hitting then. Then the probability that the hitting point is x (on the boundary of K) is proportional to the probability that a SRW started from x goes to infinity without hitting K again. So once we’ve settled on the distribution of the hitting point x, it is clear how to construct all the trajectories through K. We pick x on the boundary of K according to this distribution, and take the union of an SRW starting from x conditioned not to hit K again, and an SRW starting from x with no conditioning. These correspond to the trajectory before and after the hitting time, respectively.

In fact, it turns out that this is enough. Suppose we demand that the probability that the hitting point is x is equal to the probability that a SRW started from x goes to infinity without hitting K again (rather than merely proportional to). Sznitman proves that there is a unique measure on the set of trajectories that restricts to this measure for every choice of K. Furthermore, the Poisson Point Process with the globally-defined intensity, unsurprisingly restricts to a PPP with the intensity specific to K.

We have not so far said anything about trajectories which miss this set K. Note that under any sensible intensity with the translation-invariance property, the intensity measure of the trajectories which hit K must be positive, since we can cover \mathbb{Z}^d with countably many copies of K. So the number of trajectories hitting K is a Poisson random variable.

Recall how we defined the probability that the hitting point of K was some point x on the boundary. The sum of these probability is called the capacity of K. It follows that this is the parameter of the Poisson random variable. Ie, the probability that no trajectory passes through K is:

\exp(-u\mathrm{cap}(K)),

recalling that u is the free parameter in the intensity. This is the most convenient framework through which to start analysing the probability that there is an infinite connected set which is hit by no trajectory.

We conclude by summarising Sznitman’s Remark 1.2, explaining why it is preferable to work with the space of trajectories rather than the space of paths. Note that if we are working with paths, and we want translation invariance, then this restricts to translation invariance of the distribution of starting points as well, so it is in fact a stronger condition. Note then that either the intensity of starting at 0 is zero, in which case there are no trajectories at all, or it is positive, in which case the set of starting points looks like Bernoulli site percolation.

However, the results about capacity would still hold if there were a measure that restricted satisfactorily. And so the capacity of K would still be the measure of paths hitting K, which would be at least the probability that the path was started in K. But by translation invariance, this grows linearly with |K|. But capacity grows at most as fast as the size of the set of boundary points of K, which will be an order of magnitude smaller when K is, for example, a large ball.

REFERENCES

This was mainly based on

Sznitman – Vacant Set of Random Interlacements and Percolation (0704.2560)

Also

Sznitman – Random Walks on Discrete Cylinders and Random Interlacements (0805.4516)

Teixeira – On the Uniqueness of the Infinite Cluster of the Vacant Set of Random Interlacements (0805.4106)

and some useful slides by the same author (teixeira.pdf)

Related articles

Preferential Attachment Models

Posted on by
6

I’ve just read a really interesting paper by Peter Morters and Maren Eckhoff that made me feel I should look up some of the background and write a quick post. I may get onto some of the results in the paper at the end of this post, but I want to start by saying a bit about the model itself. I’ve spoken about this briefly in a previous post about several descriptions of complex networks, but I think it’s worth having a second attempt.

We seek a model for random graphs that gives a distribution which exhibits some of the properties of the sort of complex networks seen in the real world. In particular, whereas the degree distribution is Poisson, and so concentrated with exponential tails for the Erdos-Renyi random graph, data indicates that a better model for most applications would have power law tails for this degree distribution.

Albert and Barabasi propose growing such a graph via a so-called preferential attachment scheme. We start with some small possibly empty graph, and add new vertices one at a time. For each new vertex, we add exactly M edges between the new vertex and the vertices already present. The choice of these M other vertices is given by weighting by the degree of the (pre-existing) vertices. That is, vertices with large degree are more likely to be joined to new vertices. This is obviously designed to replicate some of the behaviour seen in say the formation of the internet, where new sites are more likely to link to established and popular sites (Google, Youtube and so on) than a uniformly chosen site.

This model has a couple of problems. Firstly, it is not immediately obvious how to start it. Obviously we need M vertices present for the PA dynamics to start working. In fact, whether one starts with a empty graph or a complete graph on M vertices makes little difference to the large n behaviour. Trickier is the question of multiple edges, which may emerge if we define the PA dynamics in the natural way, that is for each of the M edges in turn. Overcoming this is likely to be annoying.

Bollobas and Riordan do indeed overcome this possible problems in a formal way, and prove that a version of this model does indeed have power law decay of the degree distribution, with exponent equal to 3. The model in the paper instead joins new vertex (n+1) to old vertex m with probability:

\frac{f(\text{in-degree of n})}{n},

where f is some function, which for now we assume has the form f(k)=\gamma k+\beta. Since the vertices are constructed one at a time, it is well-defined to orient these edges from new to old vertices, hence this notion of in-degree makes sense.

It was not obvious to me that this model was more general than the Bollobas/Riordan model, but we will explain this in a little while. First I want to explain why the Bollobas/Riordan model has power law tails, and how one goes about finding the exponent of this decay, since this was presented as obvious in most of the texts I read yet is definitely an important little calculation.

So let’s begin with the Bollobas/Riordan model. It makes sense to think of the process in terms of time t, so there are t – M vertices in the graph. But if t is large, this is essentially equal to t. We want to track the evolution of the degree of some fixed vertex v_i, the ith vertex to be formed. Say this degree is d(t) at time t. Then the total number of edges in the graph at time t is roughly tM. Therefore, the probability that a new vertex gets joined to vertex v is roughly \frac{Md}{2Mt}, where the M appears in the numerator because there are M fresh edges available. Note that we have ignored the possibility of trying to connect multiple edges from the new vertex to v, so this holds provided d is substantially smaller than t. With the boundary condition d(i)=M, this leads to the simple ODE

\dot{d}=\frac{d}{2t}\quad \Rightarrow\quad d=M(\frac{t}{i})^{1/2}.

To me at least it was not immediately clear why this implied that the tail of the degree distribution had exponent 3. The calculation works as follows. Let D be the degree of a vertex at large time t, chosen uniformly at random.

d_i\propto (\frac{t}{i})^{1/2}

\Rightarrow\quad \mathbb{P}(D\geq d)=\frac{1}{t}|\{i:(\frac{t}{i})^{1/2}\geq d\}|=\frac{1}{t}|\{i:i\leq \frac{t}{d^2}\}|=\frac{1}{d^2}

Now we consider the Eckhoff / Morters model. The main difference here is that instead of assuming that each new vertex comes with a fixed number of edges, instead the new vertex joins to each existing vertex independently with probability proportional to the degree of the existing vertex. More precisely, they assume that edges are directed from new vertices to old vertices, and then each new vertex n+1 is joined to vertex m<n+1 with probability \frac{f(\text{indegree of }m\text{ at time }n)}{n}\wedge 1, where f(k)=\gamma k +\beta, for \gamma\in[0,1), \beta>0.

I was stuck for a long time before I read carefully enough the assertion that \beta>0. Of course, if this doesn’t hold, then the graph won’t grow fast enough. For, since the function f is now linear, we can lift the statement about evolution of the degree of a vertex to a statement about the evolution of the total number of edges. Note that each edge contributes exactly one to the total number of in-degrees. So we obtain

\dot{E}=\frac{\gamma E}{t}\quad\Rightarrow E(t)\propto t^\gamma.

In particular, this is much less than t, so the majority of vertices have small degree. The answer is fairly clear in fact: since the preferential attachment mechanism depends only on in-degree, then if f(0)=0, since the in-degree of a new vertex will always be zero by construction, there is no way to get an additional edge to that vertex. So all the edges in the graph for large t will be incident to a vertex that had positive in-degree in the time 0 configuration. Hence we need \beta>0 for the model to be meaningful. Note that this means we effectively have a Erdos-Renyi type mechanism AND a preferential attachment evolution. As, for each new vertex, we add roughly \beta edges to existing vertices chosen uniformly at random (rather than by a PA method) and also some assigned via PA. A previous paper by Dereich and Morters shows that the asymptotic degree distribution has a power law tail with exponent

\tau:=\frac{\gamma+1}{\gamma}.

Note that \gamma=\frac12 gives the same exponent (3) as the Bollobas / Riordan model.

We can apply a similar ODE approximation as above to estimate the likely large time behaviour of the number of edges:

E'=\frac{\gamma E + \beta t}{t}.

So since E'\geq \beta, we have E\geq \beta t so defining F to be E(t)/t, we get:

tF'(t)=\beta-(1-\gamma)F(t)        (1)

Noting that F’ is positive when F< \frac{\beta}{1-\gamma} and negative when F>\frac{\beta}{1-\gamma} suggests that for large t, this is an equilibrium point for F and hence E(t)\approx \frac{\beta t}{1-\gamma}. Obviously, this is highly non-rigorous, as F’ can be very small and still satisfy the relation (1), so it is not clear that the ‘equilibrium’ for F is stable. Furthermore, one needs to check that the binomial variables that supply the randomness to this model are sufficiently concentrated that this approximation by expectation is reasonable.

Nonetheless, as a heuristic this is not completely unsatisfactory, and it leads to the conclusion that E(t) is a linear function of t, and so the distribution of the out-degrees for vertices formed at large times t is asymptotically Poisson, with parameter

\lambda =\frac{\beta\gamma}{1-\gamma}+\beta=\frac{\beta}{1-\gamma}.

Note that this is the same situation as in Erdos-Renyi. In particular, it shows that all the power tail behaviour comes from the in-degrees. In a way this is unsurprising, as these evolve in time, whereas the out-degree of vertex t does not change after time t. Dereich and Morters formalise this heuristic with martingale analysis.

The reason we are interested in this type of model is that it better reflects models seen in real life. Some of these networks are organic, and so there it is natural to consider some form of random destructive mechanism, for example lightning, that kills a vertex and all its edges. We have to compare this sort of mechanism, which chooses a vertex uniformly at random, against a targeted attack, which deletes the vertices with largest degree. Note that in Erdos-Renyi, the largest degree is not much larger than the size of the typical degree, because the degree distribution is asymptotically Poisson. We might imagine that this is not the case in some natural networks. For example, if one wanted to destroy the UK power network, it would make more sense to target a small number of sub-stations serving large cities, than, say, some individual houses. However, a random attack on a single vertex is unlikely to make much difference, since the most likely outcome by far is that we lose only a single house etc.

In Eckhoff / Morters’ model, the oldest vertices are by construction have roughly the largest degree, so it is clear what targeting the most significant \epsilon n vertices means. They then show that these vertices include all the vertices that give the power law behaviour. In particular, if you remove all of these vertices and, obviously, the edges incident to them, you are left with a graph with exponential tail in the asymptotic degree distribution, with largest degree on the order of log n. It was shown in a previous paper that this type of network is not vulnerable to random removal of nodes. Perhaps most interestingly, these authors now prove that after removing the most significant \epsilon n vertices, the network IS now vulnerable to random removal of nodes, leading to the conclusion that it is preferable to experience a random attack followed by a targeted attack than vice versa!

In a future (possibly distant) post, I want to say some slightly more concrete things about how these processes link to combinatorial stochastic processes I understand slightly better, in particular urn models. I might also discuss the configuration model, an alternative approach to generating complex random networks.

Related articles

IMO 2013 – Part Four: Co-ordination and Close

Posted on by
Reply

Thursday 25th July

There is commotion at the adjacent (Netherlands?) table at breakfast when a large iguana steals a piece of bread then climbs onto a low-hanging branch to gloat over the spoils and relieve itself into their ceviche. Geoff and I also have some difficult encounters with the locals ahead today, as it is the first day of co-ordination.

This is the process by which the exam papers are marked. Geoff and I have looked at the UK students’ scripts, as have a team of local markers, called co-ordinators, who are split between the six questions. In an ideal world, all parties agree on the appropriate mark, so we can sign and head to the beach. In practice, however, the co-ordinators have very little reading time per solution, and are also responsible for ensuring the mark schemes are consistently applied.

Geoff has the 9am slot for Q4. Despite having prepared meticulous analysis of each UK student’s diagram dependency, we sign for 42/42 in a matter of seconds. Not such a baptism of fire after all. I am dealing with Q5 after lunch. They feel that Sahl has not finished the problem. I explain his argument in a slightly less minimalist fashion and they agree, getting the 41/42 we were looking for. We finish the day with Q1, which proves as straightforward as Q4.

Everyone is very pleased with progress so far, but also aware that tomorrow will be the tricky day, with the three hardest questions, including two which feature long combinatorial essays rather heavily. Geoff and I retire early to immerse ourselves in mathematics.

In the end I do spend a token amount of time asleep. Q6 is the main cause of my insomnia. Andrew has written a long argument that astonishingly combines both official solutions. Unfortunately he claims some results as trivial which the model answer devotes up to a page to proving, so we fear 6 is the best we can hope for, though explaining what is going on may take some time. Meanwhile Matei has come up with a very satisfying original argument, but has run out of time to finish it. In order to convince the co-ordinators that this will work, I cobble together the final steps and practice my speed-LaTeX while the sun rises.

Friday 26th July

First thing in the morning, and Geoff is trying to snare some partial marks on the hard geometry Q3. We feel Andrew deserves a point for some non-trivial progress in his rough work. The co-ordinators disagree and despite his entreaties we are forced to sign for a total of zero. The double combinatorics slog begins after lunch with Q2. We are able to get an extra mark for Gabriel bringing him to a total of 25 which will now surely be enough for a silver.

We are scheduled to be last to co-ordinate Q6, at 5.30pm. Aware that our arguments might take a while, and reluctant to hold up the machinations of the entire competition, we loiter and hope for an earlier slot. We end up with the problem captain for Q6 and the chief co-ordinator for all problems, so there would be no higher authority to resolve any disputes apart from an unprecedented (for the UK) appeal to the jury.

Daniel’s work turns out to be the main problem. He has not had much time, so has done the calculations for the increments of the inductive construction, and merely described how the induction itself works. The mark scheme looks very rigid, but appears to offer 4 marks for this, so I ask for that, and predictably the co-ordinators look surprised. We wrangle for a very long time indeed, but in the end I’m unable to convince them that despite the lack of proofs of the more technical part of the solution it is still worth at least 3. This extra mark would have earned Daniel a gold medal, so it is a shame, but he can perhaps draw some consolation from the fact that the regime was undoubtedly applied very fairly.

Matei and Andrew’s arguments also require lots of attention, and I am glad I prepared thoroughly, but in the end we get the 5 and 6 respectively that we wanted. They are now ensured strong gold medals. Geoff and I retire to the bar to toast what has been a record-breaking performance by the team, coming 9th overall, and top of the EU by some margin.

There follows the final jury meeting, where speeches are made by various team leaders, before the decision on the medal boundaries. There are no real controversies, and we end in good time to celebrate with our success and friends’ successes (not least a 15th place for Australia and top-ten individual score for AUS2 Alex Gunning) late into the night. I fear the supplies of Cachaca have been hit rather hard.

Saturday 27th July

The optional morning excursion to the nearby town of El Rodadero is generally spurned in favour of a lie-in and a final chance to enjoy the beach and the pool on the roof of my hotel. Since their well-deserved success may necessitate press releases and the like, the team are particularly encouraged to avoid obvious sunburn for the inevitable photos later.

The now-familiar convoy of buses gathers at dusk to transport the IMO to the nearby Quinta de San Pedro Alejandrino, site of Simon Bolivar’s impressive tomb, and location for the closing ceremony. First there are several speeches and performances from traditional singers and dancers. The mixing desk suffers some unfortunate problems, so the sound engineering for the ridiculously skilful young accordion player consists of a technician walking a single microphone from one side of the instrument to the other as the register changes.

The main event is the presentation of the medals. The UK students all do a good job of getting their Union Jacks in front of the competing flags from adjacent competitors. The space in front of the stage turns into a bit of a scrum of photographers. I turn out to be substantially bigger than the average South-East Asian mathematician, and so get some particularly suitable shots of our gold medallists.

During a further long sequence of dancing, everyone starts to drift away back towards the closing dinner at our Irotama hotel. It turns out that the British Maths Olympiad booklets have finally arrived at this late hour. Gabriel and his new friend from the Irish delegation do an excellent job of speedily distributing them amongst all the teams. After a slow start, the dance floor gradually fills while a table of deputy leaders watches on with a mixture of enthusiasm, concern and indifference. Some final goodbyes are said, others plan to chat the whole night away. This year’s IMO draws to a close.

Sunday 28th / Monday 29th July

We leave for picturesque Santa Marta airport after breakfast. It appears that some of the team have spent a non-zero time asleep. The short hop to Bogota is almost entirely made up of mathematicians, and there are plenty of paper pads and Rubik’s cubes out in the departure lounge (remembering of course that compasses can’t be taken in hand luggage).

A short change in Bogota is enlivened when the ever-suspicious Andrew Carlotti is summoned by the police. It turns out to be merely a random inspection… Geoff and I muse over plans for next year, and I learn that The Glass Bead Game is a very useful tool for getting to sleep much earlier than natural.

After a layover and much-needed triple espresso in Madrid, and an initial aborted landing at windy Heathrow, everyone is united with adoring parents and other fans. Despite Geoff’s best efforts, his dream of a flash-heavy welcome by the national press fails to come to fruition. We live in hope for next year.

IMO 2013 – Part Three: Opening Ceremony and Exams

Posted on by
Reply

Sunday 21st July

It turns out that the main entrance to the Hotel Irotama, the resort hosting the olympiad, is less than 100m from the entrance to the villas we’ve been staying. The jury remains out on whether that makes us the first team to arrive at an IMO on foot, not least because we are joined for this short but significant journey by the Australian and Israeli teams.

It’s another sticky and unpleasant day, but initial impressions are very favourable. The team have a pair of bungalows with dried leaves for roofs. Among other things, the air conditioning is working well! Lunch is available from beside the beach at a selection of restaurants, which have all been uniformised for the week. In any case, it is a pleasant reversal of the usual situation for the food to be high in quality and low in queueing time.

The UK students are immediately keen to meet other teams, starting with some of English-speaking countries, and moving on to the United States. The non-verbal school of interaction continues as a massive multi-national cross between water polo and rugby emerges in the pool, visible from my 11th floor balcony. The view across the bay as the sun sets are spectacular, even if the wind and the low railings do make me question the wisdom of the hammock strings above the jacuzzi?

Monday 22nd July

Today’s main event is the opening ceremony, which is being held in Barranquilla, near where the team leaders are currently based. The boards in the lobby advertise a sensible plan partitioning the teams into equal-sized classes alphabetically. We are bound for bus 20 with the USA and the enigmatic “others”, though disaster strikes when it transpires the buses provided are not equal in size. An appropriately weighted partition emerges organically, and we are on the move. The two-hour drive offers some views of the closest Colombia’s Caribbean can get to a rugged coastline and bustling towns offering a welcome contrast to the constant glossiness of the resorts.

The Opening Ceremony features the usual sequence of speeches, children’s choirs, and the procession of the teams. Barranquilla is Colombia’s fourth-largest city, and the economic centre of this region. The carnival held there annually is the most famous in South America outside of Rio. Even though that was six months ago, it is a nice touch to invite a selection of the dancers, acrobats and musicians to accompany each of the teams round the sports hall where the ceremony is taking place.

Other teams have extravagant rituals planned for their brief moment of limelight, but the UK students opt for a more reserved approach, apart from choosing at the last minute to hoist Sahl onto various shoulders. Having safely dismounted near the end of their circuit, they receive a bold thumbs-up from Geoff who is sitting in the leaders’ area, segregated on the other side of the arena. Whether this is a token of encouragement for tomorrow’s paper, or a show of delight in the minimalist choreography remains to be seen.

The festivities drag on a bit longer than planned, and after four hours hunger levels are becoming fractious. I don’t really want to know how long the turkey sandwiches had been slow-cooking in the sun, but for once it is convenient to have a solid component of vegetarians in the UK team. After an entire day of sitting around, I propose a brisk walk along the shore after dinner. We are prevented from leaving the Irotama’s portion of beach by a member of hotel security. I have a Deputy Leader’s badge. He has a gun. We make do with the view of the stars and the flotilla of ships lining up for the Panama Canal.

Tuesday 23rd July

It’s the first day of the competition and understandably the team are a bit nervous at breakfast. We follow the organisers’ instructions to the letter, and arrive almost an hour early at the exam hall, located at a similar hotel further down the road. After a final check of compasses and so forth, the team sally forth to their respective rooms, and the deputies return to the hotel and take a quick swim while waiting for some copies of the paper to materialise.

As the delay grows, the number of deputies waiting outside the office reaches what feels like a critical mass. It will transpire that some members of the Syrian team, who had been delayed by visa complications, have just arrived, and arrangements are being made for them to sit the paper before it is generally released. Ivan is able briefly to astonish onlookers by quoting instantly a solution to Q2, before revealing that it is in fact his question. We have about an hour to think about the problems before meeting the students.

The UK team are generally pleased with the paper, with five students claiming the first two questions, and some tentative offerings on the final question. We have a succession of more formal individual debriefs while walking back to the Irotama down the beach. Some of their arguments for Q1 sound rather more complicated than required, but hopefully it will all make sense when Geoff and I get to see the scripts. In the meanwhile, the UK students head to the pool, trying as much as possible to avoid comparisons with other teams and other non-helpful forms of post-mortem.

Wednesday 24th July

We allow ourselves the luxury of an extra 20 minutes at breakfast but along with many teams are still absurdly early for the second day’s exam. Today’s security is much tighter, and the deputies are not allowed into the conference building, so content ourselves with exchanging the national olympiad booklets and competing for the few patches of shade available from the baking morning sun.

Back at the resort, there is again no sign of the problems, so I use the freshly-unlocked Irotama wifi to sort out a very last-minute change of tenancy agreement and speak further with Colombian customs. Apparently the tax on a case of frisbees is 150,000 Pesos (a slightly less impressive sounding £50). My expectations remain low. It will transpire, however, that missing the official deputies excursion might have been a good idea. Reports are floating around of a 2 hour video and a bus tour with no actual stops.

After the paper we meet the team, who all seem very upbeat. Everyone claims solutions to Qs 4 and 5, with all but Warren resisting the temptation to deploy some form of co-ordinate method on the geometry. Andrew also claims Q6, so all in all everyone is rather pleased, and looking forward to an afternoon free to enjoy all that’s on offer at the competition site free now that the pressure is off.

Geoff joins us in time for dinner bearing the first day’s examination scripts and plenty of gossip about activities at the leaders’ site. However, our task for the evening is not a social one. The second day’s scripts arrive at about 8pm, and then we retire to devise our plan of attack. It makes sense to tackle three questions each, so I have a look through the Q5 scripts, and all seems fine, with the Q2 and Q6 answers to be addressed tomorrow. By comparison with the grapevine, it does look as if the UK might have done rather well indeed!

IMO 2013 – Part Two: Ashes and Santa Marta

Posted on by
Reply

Thursday 18th July

The third practice exam again proceeds smoothly. The first problem is a nice exercise by John Conway, on classifying sets of points which obey some intersection property. There were various ways to misread the problem, of which some students took full advantage, and an almost limitless number of ways to classify the satisfactory configurations. As a result the marking, which I chose to do outside, took ages, though at least I had the company of a few passing green lizards and a brief visit from an eagle.

The resort where we are staying, and in fact where the IMO itself will be held, is actually about 10km outside Santa Marta itself, so we decide to venture in to explore the town once marking is complete. The historical centre, though modelled on a grid, is very Mediterranean, with narrow streets wending their way underneath exposed municipal wiring down to the seafront. We pause outside the Cathedral, where Mass is just starting. The dry heat clearly not enough to discourage a very full and colourful set of vestments.

On the way down to the sea we pass a park featuring yet another statue of the most famous man to live (and in fact die) in Santa Marta. Our guide Maria looks horrified as one of the students asks “Simon Who?” Dinner ends up al fresco, where we are treated to the accordion playing and fire-juggling in the town square. How does some one take up fire-juggling one wonders? Are there beginner kits with just lightbulbs on the end? Very few of the party receive the meal they think they ordered, but all are satisfied nonetheless. The convoy of taxis departs into the night. I am in the second one and it is clear that the driver has no idea where he is going, and his dedication to staying within sight of his leader is admirable if occasionally terrifying.

Friday 19th July

To mix things up, today each team has set an IMO-style paper for the other to attempt. The UK team then has to mark the Australian scripts during the afternoon and vice versa, before co-ordinating the results with Ivan the Australian deputy leader and myself. It’s always a profitable exercise to have to struggle with poorly worded solutions as perhaps it will encourage everyone to avoid such things in the actual exam. Questions which fall into the realm of the combinatorial essay are always particularly at risk of large blocks of waffling prose, and each Q2 produces exactly that. Hopefully the students found the exercise useful as well as time-consuming.

Meanwhile, it seems that the UKMT-branded frisbees we ordered to distribute as gifts at the IMO have been held up somewhere in the intricacies of Colombian customs. Initial attempts to speak on the phone are hindered by my non-existent Spanish, and even an attempt to spell out my email address is fraught with the challenges of differing vowel pronunciations. I fear we may have to resign ourselves to being the stingy delegation at this competition…

I take advantage of a relatively free afternoon to sample the resort’s various pools and catch up on what’s been happening in the cricket. Our own version of the Ashes is taking place tomorrow, so hopefully the demolition happening at Lord’s is a good omen. Geoff and his brother are attempting to get the hashtag #otherashes trending. So far we have one tweet (by me) and a mention in the Guardian cricket feed. From tiny acorns…

Saturday 20th July

And so to the final practice exam of this pre-IMO camp, the Mathematical Ashes. I was a student in 2008 for the inaugural competition, the only time the UK has lost, and so in keeping with the cricket tradition the ceremonial funeral urn is filled with the ashes of UK mathematics, including a geometry question in my handwriting. (In fact, the pyre formed during an excursion after the IMO in Madrid got a bit out hand, and so it probably contains a comparable amount of Australian material.)

As for the other exams, we are using questions from last year’s IMO shortlist, that is, problems that were considered for inclusion by the jury, but not selected. The first two chosen are at the easier end of the IMO difficulty spectrum, while the third is really very awkward indeed. Post-exam, the teams compare notes and it seems that it will be tight, so Ivan and I divide up the questions, devise brief mark schemes and get going. Three hours later we feel happy with our conclusion: UNK 82, AUS 81. In reality, by far the most pleasing aspect is that both teams have demolished the two easier questions with such aplomb. This bodes very well for the IMO itself next week.

A wager is placed that less than 10 minutes will elapse between emailing Joseph Myers, custodian of the IMO Register and the BMOS website, and the results appearing on the latter. The placer of this wager turns out to be rather wise. We await a flood of hits on the OtherAshes blog. Meanwhile, we pay our final visit to the Santorini resort restaurant, who have accommodated our various dietary specifications and comical Spanish with elan. I order at random from the fish and seafood section and end up with a steak topped with guacamole. Definitely not complaining. Everyone heads back feeling understandably excited for the start of the main event tomorrow.

IMO 2013 – Part One: Travel and Training

Posted on by
1

Preamble

Six years ago in Rhodes, Tom Lovering and I started what has now become a strong tradition of preparing an unofficial report about maths competitions from the student perspective. It seems appropriate to attempt to continue this in my new role as the Deputy Leader of this year’s UK team at the IMO. And since I have excellent wifi and a (just about) active maths blog, there seems no reason not to do this in real time, at least to a first approximation. I’m sure fans all around the world will be glued to their screens.

I should briefly explain what the IMO is. The acronym stands for International Mathematical Olympiad, and it is a competition held every year in July, welcoming school students from over 100 countries. Tempting though it is to picture a drawn-out global version of the ‘mathletics’ scene at the end of Mean Girls, the reality is somewhat different. Each country sends six students, who sit two 4.5 hour exams, each with three questions, in roughly increasing order of difficulty. It does however remain the case that you get jackets if you make the finals, admittedly with polyester rather than leather sleeves. Medals are awarded to roughly half of the participants.

Each team has a leader, who arrives early to help set the paper, and also assesses their team’s scripts, presenting their marks for approval by a board of co-ordinators supplied by the host country. Each team also has a deputy leader, who stays with the team initially, then joins the leader for this marking process.

As well as the competitive side, the olympiad is a great opportunity to meet other young mathematicians from all around the world. Certainly I am still in touch with many of the people I met when I was lucky enough to compete in Vietnam and Madrid (2007, 2008 respectively). As the competition moves country every year, it’s also a great chance to see some exciting places. This year it is in Santa Marta on Colombia’s Caribbean coast, after Buenos Aires in 2012.

Anyway, on with the report.

Sunday 14th July

I spend the morning packing up my room as I am moving to a new flat pretty much directly after this trip. Everything seems a lot clearer after sorting out the IMO team uniform which has arrived just in time leaving my floor essentially invisible under a sea of boxes. The mini-crisis wherein they were all delivered without my knowledge to the Worcester College kitchens seems but a distant memory…

We are flying at a painfully early hour tomorrow morning, so it makes sense to spend the night at an airport hotel. Courtesy of the satnav, I learn the hard way that there are three Holiday Inns at Heathrow. Geoff, Bev and I are the first to arrive, and wait for the students, two of whom are arriving directly from Copenhagen, bearing prizes and stories from the analogous physics competition just finished there. Parents are reassured that the occasional email and postcard will be sent and we retire in preparation for tomorrow’s Odyssey.

Monday 15th July

Up at 4.30am for the first leg over to Madrid. With time for little other than a quick espresso, straight onto the transatlantic flight to Bogota. The ten hours afford plenty of time to catch up on reading some papers. Had a think about how these results about (uniform) random forests might affect our thoughts about frozen percolation, and took advantage of the increasing tedium to do a long rate function calculation I’d been putting off for ages. I think the answer is \frac{1}{2}(1-\frac{1}{\lambda}) – the question is somewhat more interesting…

Also relish the chance to spend several hours diving into Love in the Time of Cholera, having figured that this was almost certainly a once-in-a-lifetime opportunity to explore a Colombian novelist while in Colombia. So far, so good. In particular, much more interesting than One Hundred Years of Solitude, or perhaps my tastes have changed in the past few years?

We learn courtesy of Iberia that tuna, peach and olives do not make a good sandwich combination, and wonder whether they will be able to resist the temptation to follow every announcement with a synthesised rendition of the Concierto de Aranjuez. A slight delay changing at Bogota airport allows sufficient time for extra sushi and further progress through the example sheet solutions I’ve offered to \LaTeX before the short hop north to Santa Marta. Gabriel’s cynicism about the fate of our luggage turns out to be unfounded, but the two panama hats packed in my suitcase have not enjoyed the trip at all. The Santorini Hotel seems ill-prepared for a group arrival at 10.30pm, but eventually we obtain keys and pay. Shortly afterwards, we are able to unpay one of the bills that they have charged us twice within the space of five minutes. With everyone very grateful for the violent air conditioning, we head for much overdue sleep.

Tuesday 16th July

Up at dawn from the jetlag, but a useful moment to sort out the details for the first practice exam. This pre-IMO camp is a joint venture with the Australian team, and both sets of students are sitting an IMO style exam each morning. The villa we are occupying is somewhat sort on table space, but the three UK students perched on the kitchen bar with their scripts claim that it is fine. If IMO 2008 is anything to go by, where the desks for the competition were so steeply sloped that pens became more valuable as paperweights than as writing equipment, this might be useful practice.

While the students are getting on with the festivities, Bev and I explore various local food options, I study a couple of papers and explore the beach, though the humidity is rather cloying in the middle of the day. The UK team make confident noises about the exam, so I hope that marking the Q2 geometry won’t be too traumatic. Some complicated diagram dependencies render this hope in vain, but we finish up in time for a quick debrief before dinner. Meanwhile, the team have learned the hard way that Colombian plumbing does not hugely appreciate toilet paper…

Wednesday 17th July

I would normally struggle rather badly to find the motivation to go for a 7am run, but with a mile or so of relatively quiet beach on offer, it suddenly becomes a much more attractive proposition. As I return to the Santorini resort, the first waves of peddlers are arriving. One or two make a token attempt to sell me sunglasses, and a nice lady asks me how I got a particularly purple bruise, though I figure my Spanish is not sufficient to explain the idea of cricket right now.

Geoff bids us farewell and heads off to join the other team leaders at a top-secret location where they will begin the process of setting the paper. In theory it’s top-secret; in practice, it must be Barranquilla, the next city down the coast. The students power through another exam all morning, and pleasingly resist the temptation to make anything too complicated, so marking everything is relatively straightforward. Our stroll to dinner is accompanied by a small posse of feral dogs. I am reminded of the health guidance for this part of the world: “rabies is relatively low-risk, except for children, who are more likely to allow themselves to be licked in the face.”

Related articles

The Contour Process

Posted on by
2

As I explained in my previous post, I haven’t been reading around as much as I would generally like to recently. A few days in London staying with my parents and catching up with some friends has therefore been a good chance to get back into the habit of leafing through papers and Pitman’s book among other things.

This morning’s post should be a relatively short one. I’m going to define the contour process, a function of a (random or deterministic) tree, related to the exploration process which I have mentioned a few times previously. I will then use this to prove a simple but cute result equating in distribution the sizes of two different branching processes via a direct bijection.

The Contour Process

To start with, we have to have a root, and from that root we label the tree with a depth-first labelling. An example of this is given below. It is helpful at this stage to conceive this process as an explorer walking on the tree, and turning back on themselves only when there is no option to visit a vertex they haven’t already seen. So in the example tree shown, the depth-first exploration visits vertex V_2 exactly four times. Note that with this description, it is clear that the exploration traverses every edge exactly twice, and so the length of the sequence is 2n-1, where n is the number of vertices in the tree since obviously, we start and end at the root.

Another common interpretation of this depth-first exploration is to take some planar realisation of the tree. (Note trees are always planar – proof via induction after removing a leaf.) Then if you treat the tree as a hedge and starting at the root walk along, following the outer boundary with your right hand, this exactly recreates the process.

The height of a tree at a particular vertex is simply the graph distance between that vertex and the root. So when we move from one vertex to an adjacent vertex, the height must increase or decrease by 1.

The contour process is the sequence of heights seen along the depth-first exploration. It is therefore a sequence:

0=h_0,h_1,\ldots,h_{2n-1}=0,\quad h_i\geq 0,

and such that |h_{i+1}-h_i|=1.

Note that though the contour process uniquely determines the tree structure, the choice of depth-first labelling is a priori non-canonical. For example, in the display above, V_3 might have been explored before V_2. Normally this is resolved by taking the suitable vertex with the smallest label in the original tree to be next. It makes little difference to any analysis to choose the ordering of descendents of some vertex in a depth-first labelling randomly. Note that this explains why it is rather hard to recover Cayley’s theorem about the number of rooted trees on n vertices from this characterisation. Although the number of suitable contour functions is possible to calculate, we would require a complicated multiplicative correction for labelling if we wanted to recover the number of trees.

The only real observation about the uses of the contour process at this stage is that it is not in general a random walk with IID increments for a Galton-Watson branching process. This equivalence is what made the exploration process so useful. In particular, it made it straightforward, at least heuristically, to see why large trees might have a limit interpretation through Brownian excursions. If for example, the offspring distribution is bounded above, say by M, then the contour process certainly cannot be a random walk, as if we have visited a particular vertex exactly M+1 times, then it cannot have another descendent, and so we must return closer to the root at the next step.

I want to mention that in fact Aldous showed his results on scaling limits towards the Continuum Random Tree through the contour process rather than the exploration process. However, I don’t want to say any more about that right now.

A Neat Equivalence

What I do want to talk about is the following distribution on the positive integers. This comes up in Balazs Rath and Balint Toth’s work on forest-fires on the complete graph that I have been reading about recently. The role of this distribution is a conjectured equilibrium distribution for component size in a version of the Erdos-Renyi process where components are deleted (or ‘struck by lightning’) at a rate tuned so that giant components ‘just’ never emerge.

This distribution has the possibly useful property that it is the distribution of the total population size in a Galton-Watson process with Geom(1/2) offspring distribution. It is also the distribution of the total number of leaves in a critical binary branching process, where every vertex has either two descendents or zero descendents, each with probability 1/2. Note that both of these tree processes are critical, as the expected number of offspring is 1 in each case. This is a good start, as it suggests that the relevant equilibrium distribution should also have the power-law tail that is found in these critical branching processes. This would confirm that the forest-fire model exhibits self-organised criticality.

Anyway, as a sanity check, I tried to find a reason why, ignoring the forest-fires for now, these two distributions should be the same. One can argue using generating functions, but there is also the following nice bijective argument.

We focus first on the critical Geometric branching process. We examine its contour function. As explained above, the contour process is not in general a random walk with IID increments. However, for this particular case, it is. The geometric distribution should be viewed as the family of discrete memoryless distributions.

This is useful for the contour process. Note that if we are at vertex V for the (m+1)th time, that is we have already explored m of the edges out of V, then the probability that there is at least one further edge is 1/2, independently of the history of the exploration, as the offspring distribution is Geometric(1/2), which we can easily think of as adding edges one at a time based on independent fair coin tosses until we see a tail for example. The contour process for this random tree is therefore a simple symmetric random walk on Z. Note that this will hit -1 at some point, and the associated contour process is the RW up to the final time it hits 0 before hitting -1. We can check that this obeys the clear rule that with probability 1/2 the tree is a single vertex.

Now we consider the other model, the Galton-Watson process with critical binary branching mechanism. We should consider the exploration process. Recall that the increments in this process are given by the offspring distribution minus one. So this random sequence also behaves as a simple symmetric random walk on Z, again stopped when we hit -1.

To complete the bijective argument, we have to relate leaves in the binary process to vertices in the geometric one. A vertex is a leaf if it has no offspring, so the number of leaves is the number of times before the hitting time of -1 that the exploration process decreases by 1. (*)

Similarly for the contour process. Note that there is bijection between the set of vertices that aren’t the root and the set of edges. The contour process explores every edge exactly twice, once giving an increase of 1 and once giving a decrease of 1. So there is a bijection between the times that the contour process decreases by 1 and the non-root vertices. But the contour process was defined only up to the time we return to the root. This is fine if we know in advance how large the tree is, but we don’t know which return to the root is the final return to the root. So if we extend the random walk to the first time it hits -1, the portion up until the last increment is the contour process, and the final increment must be a decrease by 1, hence there is a bijection between the number of vertices in the Geom(1/2) G-W tree and the number of times that the contour process decreases by 1 before the hitting time of -1. Comparing with (*) gives the result.

Related articles

Recent Progress and Gromov-Hausdorff Convergence

Posted on by
1

For the past few weeks I’ve been working on the problem of Cycle-Induced Forest Fires, which I’ve referred to in passing in some recent posts. The aim has been to find a non-contrived process which exhibits self-organised criticality, that is, where the process displays critical characteristics (scaling laws, multiple components at the largest order of magnitude) forever. Note that this is in contrast to the conventional Erdos-Renyi graph process, which is only critical at a single time n/2.

The conjecture is that the largest component in equilibrium typically has size on a scale of n^2/3. An argument based on the equilibrium proportion of isolated vertices gives an upper bound on this exponent. The working argument I have for the lower bound at the moment can comfortably fit on the back of a napkin, with perhaps some context provided verbally. Of course, the current full text is very much larger than that, mainly because the napkin would feature assertions like “event A happens at time O(n^\beta)“; whereas the more formal argument has to go like:

“With high probability as n\rightarrow\infty, event A happens between times n^{\beta-\epsilon},n^{\beta+\epsilon}, for any suitably small \epsilon>0. Furthermore, the probability that A happens after this upper threshold decays exponentially with n for fixed \epsilon, and the probability that A happens before the lower threshold is at most n^{-\epsilon}. Finally, this is under the implicit assumption that there will be no fragmentations before event A, and this holds with probability 1-o(1) etc.”

It’s got to the point where I’ve exhausted the canonical set of symbols for small quantities: \epsilon,\delta,(\eta ?).

This has been a very long way of setting up what was going to be my main point, which is that at many points during undergraduate mathematics, colleagues (and occasionally to be honest, probably myself too) have complained that they “don’t want to have anything to do with analysis. They just want to focus on algebra / number theory / statistics / fluids…” Anyway, the point of this ramble was that I think I’ve realised that it is very hard to think about any sort of open problem without engaging with the sort of ideas that a few years ago I would have thought of (and possibly dismissed) as ‘analysis’.

Much of my working on this problem has been rather from first principles, so haven’t been thinking much about any neat less elementary theory recently.

Ok, so on with the actual post now.

Last month I talked about local limits of graphs, which describe convergence in distribution of (local) neighbourhood structure about a ‘typical’ vertex. This is the correct context in which to make claims like “components of G(n,\frac{\lambda}{n}) look like Galton-Watson trees with offspring distribution \text{Po}(\lambda)“.

Even from this example, we can see a couple of drawbacks and omissions from this limiting picture. In the sub-critical regime, this G-W tree will be almost surely finite, but the number of vertices in the graph is going to infinity. More concretely, the limit description only tells us about a single component. If we wanted to know about a second component, in this case, it would be roughly independent of the size of the first component, and with the same distribution, but if we wanted to know about all components, it would get much more complicated.

Similarly, this local limit description isn’t particularly satisfactory in the supercritical regime. When the component in question is finite, this description is correct, but with high probability we have a giant component, and so the ‘typical’ vertex is with some positive probability in the giant component. This is reflected by the fact that the G-W tree with supercritical offspring distribution is infinite with some positive probability. However, the giant component does not look like a \text{Po}(\lambda) G-W tree. As we exhaust O(n) vertices, the offspring distribution decreases, in expectation at least. In fact, without the assumption that the giant component is with high probability unique (so \frac{L_1}{n}=1-\mathbb{P}(|C(v)|<\infty), we can’t even deduce the expected size of the giant component from the local limit result.

This is all unsurprising. By definition a local limit describes the structure near some vertex. How near? Well, finitely near. It can be arbitrarily large, but still finite, so in particular, the change in the offspring distribution after O(n) vertices as mentioned above will not be covered.

So, if we want to learn more about the global structure of a large discrete object, we need to consider a different type of limit. In particular, the limit will not necessarily be a graph. Rather than try to define a priori a ‘continuum’ version of a graph, it is sensible to generalise from the idea that a graph is a discrete object and instead consider it as a metric space.

In this article, I don’t want to spend much time at all thinking about how to encode a finite graph as a metric space. We have a natural notion of graph distance between vertices, and it is not hard to extend this to points on edges. Alternatively, for sparse graphs, we have an encoding through various functions, which live in some (metric) function space.

However, in general, the graph will be a metric object itself, rather than necessarily a subset of a global metric space. We will be interested in convergence, so we need a suitable style of convergence of different metric spaces.

The natural candidate for this is the Gromov-Hausdorff metric, and the corresponding Gromov-Hausdorff convergence.

The Hausdorff distance between two subsets X, Y of a metric space is defined as follows. Informally, we say that d_H(X,Y)<\epsilon if any point of X is within distance \epsilon from some point of Y, in the sense of the original metric. Formally

d_H(X,Y):=\max \{\sup_{x\in X}\inf_{y\in Y}d(x,y), \sup_{y\in Y}\inf_{x\in X}d(x,y)\}.

It is not particularly illuminating to prove that this is in fact a metric. In fact, it isn’t a metric as the definition stands, but rather a pseudo-metric, which is exactly the same, only allowing d(X,Y)=0 when X and Y are not equal. Note that

d(X^\circ,\bar X)=0,

for any set X, so this gives an example, provided X is not both open and closed. Furthermore, if the underlying metric space is unbounded, then the Hausdorff distance between two sets might be infinite. For example in \mathbb{R},

d_H(\mathbb{R}_{<0},\mathbb{R}_{>0})=\infty.

We can overcome this pair of objections by restricting attention to closed, bounded sets. In practice, many spaces under consideration will be real in flavour, so it makes sense to define this for compact sets when appropriate.

But this still leaves the underlying problem, which is how to define a distance function on metric spaces. If two metric spaces X and Y were both subspaces of some larger metric space then it would be easy, as we now have the Hausdorff distance. So this is in fact how we proceed in general. We don’t need any knowledge of this covering space a priori, we can just choose the one which minimises the resulting Hausdorff distance. That is

d_{GH}(X,Y)=\inf\{d_H(\phi(X),\psi(Y))\},

where the infimum is taken over all metric spaces (E,d), and isometric embeddings \phi: X\rightarrow E, \psi: Y\rightarrow E.

The first observation is that this will again be a pseudometric unless we demand that X, Y be closed and bounded. The second is that this index set is not a set. Fortunately, this is quickly rectified. Instead consider all metrics on the disjoint union of sets X and Y, which is set, and contains the subset of those metrics which restrict to the correct metric on each of X and Y. It can be checked that this forms a true metric on the set of compact metric spaces up to isometry.

We have an alternative characterisation. Given compact sets X and Y, a correspondence between X and Y is a set of pairs in X\times Y, such that both projection maps are surjective. Ie for any x in X, there is some pair (x,y) in the correspondence. Let \mathcal{C}(X,Y) be the set of such correspondences. We then define the distortion of correspondence \mathcal{R} by:

\text{dis}(\mathcal{R}):=\sup\{|d_X(x_1,x_2)-d_2(y_1,y_2)|: (x_i,y_i)\in\mathcal{R}\}.

Then

d_{GH}(X,Y)=\frac{1}{2}\inf_{\mathcal{R}\in\mathcal{C}(X,Y)}\text{dis}(\mathcal{R}).

In particular, this gives another reason why we don’t have to worry about taking an infimum over a proper class.

Gromov-Hausdorff convergence then has the natural definition. Note that this does not respect topological equivalence, ie homeomorphism. For example,

\bar{B(0,\frac{1}{n})}\stackrel{GH}{\rightarrow} \{0\},

where the latter has the trivial metric. In particular, although all the closed balls are homeomorphic, the G-H limit is not.

A final remark is that the trees we might be looking at are not necessarily compact, so it is useful to have a notion of how this might be extended to non-compact spaces. The answer is to borrow the idea from local limits of considering large finite balls around a fixed central point. In the case of trees, this is particularly well-motivated, as it is often quite natural to have a canonical choice for the ‘root’.

Then with identified points p_n\in X_n, say (X_n,p_n)\rightarrow (X,p) if for any R>0 the R-ball around p_n in X_n converges to the R-ball around p in X. We adjust the definition of distortion to include the condition that the infimum be over correspondences for which (p_X,p_Y) is an element.

REFERENCES

This article was based on some lecture notes by Jean-Francois Le Gall from the Clay Institute Summer School which can be found on the author’s website here (about halfway down the page). This material is in chapter 3. I also used Nicolas Curien’s tutorials on this chapter to inform some of the examples. The resolution of the proper class problem was mentioned by several sources I examined. These notes by Jan Christina were among the best.

Related articles