Random walks on random graphs in critical regimes

近几十年来，人们从许多不同的角度研究了随机图上的随机游动。其中许多都出现在物理科学或计算机科学中，在这些领域，在随机图上具有适当代表性的随机游动可以提供对无序介质或复杂网络的传输特性的洞察。为理解这些系统而提出的模型通常在数学上很容易定义，但在几个特别重要的情况下，已被证明导致了一系列丰富的行为，这有时相当违反直觉。虽然这些基本例子中的一些情况正变得越来越好地理解，但所讨论的随机图上的随机游动继续给数学家带来深刻的挑战。在临界状态下的随机图形上的随机游动尤其如此，在这种情况下，“分形”结构往往使出现的对象难以分析。拟议的研究旨在解决这一领域的一些关键问题。首先，在研究随机图的动力学性质时，目前有一个特别的重点是确定外场的影响，即使图上的随机游动更有可能在每一步朝特定方向跳跃的偏差。事实上，在这一领域已经证明了一些值得注意的结果。例如，对于某些超临界模型，已经证明随机环境的死端会产生陷阱，随着偏差的增加而变得更强，因此当偏差设置在某个临界值以上时，有偏随机游走的速度为零。这与在规则晶格上随机行走的情况形成了鲜明的对比，在规则晶格上，很容易证明速度随着偏置强度的单调增加。在临界状态下，人们预计会有更极端的诱捕行为--不仅因为死胡同通常更大，还因为图中稀疏路径的渐近形状本身将对有偏随机游走的逃逸速度产生影响。描述这些影响将是本项目的第一个目标。第二，有限图上的随机游动的一个自然性质是它的覆盖时间，即直到随机游动访问完图的每个顶点所需的步数。这个数值不仅是概率学家和组合学家关注的焦点，也是理论计算机科学家感兴趣的问题，他们试图回答这样的问题：一个随机算法应该运行多长时间才能探索整个状态空间？最近的研究表明，在期望覆盖时间和被称为“高斯自由场”的数学结构之间存在着精确的联系，对于某些图序列，这种数学结构给出了覆盖时间的渐近增长率的一个很好的见解。然而，许多临界图并不属于这样一类图，在这种图中，这些高斯自由场估计将产生最优结果，特别是包括作为复杂网络理论的基本构件的“Erdos-Renyi随机图”的关键版本。最后，为了进一步理解随机图上的随机游动，研究它们的扩散尺度极限的性质是非常有用的。在随机图落入临界区域的情况下，通常情况下，这些扩散将具有复杂的随机分形状态空间，并且表现异常--典型地，次扩散。这个项目的第三部分将涉及识别由于所考虑的随机过程与它们所穿越的媒体的不规则性之间的相互作用而产生的“新”类型的行为。

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 casesFinally, 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.