Random walks on random graphs have in recent decades been studied from a number of different perspectives. Many of these have arisen in the physical sciences or computer science, where a suitably representative random walk on a random graph can offer an insight into the transport properties of a disordered medium or a complex network. The models proposed to understand these systems are often simple to define mathematically, but nonetheless have, in several particularly important cases, been shown to lead to a rich array of behaviour, which is sometimes rather counterintuitive. Although the situation in some of these fundamental examples is becoming increasingly well understood, the random walks on the random graphs in question continue to present deep challenges for mathematicians. This is particularly the case for random walks on random graphs in critical regimes, where a 'fractal' structure often makes the objects that arise difficult to analyse. The proposed research aims to tackle a number of key problems in this area.
To begin with, in studying the dynamical properties of random graphs, there is a particular focus at the moment on determining the effect of an external field, that is, a bias that makes a random walk on the graph more likely to jump in a particular direction on each step. Indeed, some notable results have been proved in this area. For instance, it has been shown for certain supercritical models that the dead-ends of the random environment create traps which become stronger as the bias is increased, so that when the bias is set above a certain critical value, the speed of the biased random walk is zero. This is a striking contrast to the case of a random walk on a regular lattice, where it is easily shown that the speed increases monotonically with the bias strength. In critical regimes, one would expect more extreme trapping behaviour - not only because the dead-ends are typically larger, but also because the asymptotic shapes of the sparse paths in the graph will themselves have an impact on the rate of escape of a biased random walk. Describing these effects will be the first aim of this project.
Secondly, a natural property of a random walk on a finite graph to study is its cover time, that is, the number of steps it takes until the random walk has visited every vertex of the graph. As well as being a focus of attention for probabilists and combinatorialists, this quantity is of interest to theoretical computer scientists seeking to answer such questions as: 'How long should a randomised algorithm be run until it has explored the entire state space?'. It has recently been shown that there is a precise link between the expected cover time and a mathematical structure called the 'Gaussian free field' that, for certain sequences of graphs, has given a great insight into the asymptotic growth rate of cover times. However, many critical graphs do not fall into the class of graphs where these Gaussian free field estimates will yield optimal results, including in particular the critical version of the 'Erdos-Renyi random graph', which is a fundamental building block in theories of complex networks. This project will seek to provide alternative techniques for dealing with these cases
Finally, in order to further understand random walks on random graphs, it can be extremely informative to study the properties of their diffusion scaling limits. In the case when the random graph falls into a critical regime, it is routinely the case that these diffusions will have complex random fractal state-spaces, and behave anomalously - typically, sub-diffusively. The third part of this project will involve identifying 'new' types of behaviour that arise as a result of the interplay between the random processes considered and the irregularity of the media they traverse.
|