Random Walks, Spanning Forests and Infinite Planar Maps Converge to LQG.

The behaviour of random processes on infinite structures presents significant challenges to mathematical analysis, yet understanding these dynamics is crucial for modelling complex systems ranging from network connectivity to the geometry of disordered materials. Recent work by Gwynne, Sung, et al., from the University of Chicago, investigates a specific instance of this problem, focusing on the behaviour of a continuous-time random walk that repeatedly encounters and reflects off an infinite boundary. Their research, detailed in the paper “Random walk reflected off of infinity, with applications to uniform spanning forests and supercritical Liouville quantum gravity”, establishes a connection between this reflected random walk and the construction of uniform spanning forests – probabilistic structures representing connectivity within a graph – and extends these findings to the study of infinite random planar maps exhibiting characteristics aligned with supercritical Liouville quantum gravity, a mathematical framework used to describe random surfaces. This work provides new insights into the properties of these complex systems and proposes conjectures regarding stochastic processes occurring within them.

Researchers currently investigate a variant of the continuous-time random walk, conducted on an infinite graph, and establish its transient nature, meaning the walk is not confined to a finite region. A reflection mechanism is introduced at a designated set, permitting infinite repetitions of the walk and influencing its long-term behaviour. Application of the Aldous-Broder algorithm to this reflected random walk demonstrably generates the free uniform spanning forest (FUSF) on the graph. A spanning forest is a graph connecting all vertices without necessarily forming cycles, and ‘free’ indicates each edge is selected independently with equal probability. The FUSF is a collection of such forests, each with a uniform probability of being selected. This confirms the algorithm’s reliability in generating a uniformly distributed spanning forest.

However, Wilson’s algorithm, another method for generating the FUSF, does so only conditional on the resulting forest being connected, meaning all vertices are reachable from each other. This represents a limitation compared to the broader applicability of the Aldous-Broder algorithm, which does not require connectivity. This distinction is crucial when analysing graphs where disconnected components are possible or even expected.

This theoretical framework extends to the study of random planar maps, which are infinite two-dimensional graphs possessing specific probabilistic properties. These maps belong to the universality class of supercritical Liouville Quantum Gravity (LQG), a mathematical model describing random surfaces with fractal dimensions. Characterised by an uncountable number of ends, these maps provide a rich setting for exploring the interplay between graph structure and geometric properties. Researchers define a modified Tutte embedding, a technique for representing a graph as a planar graph, tailored for these infinite maps. They conjecture that this embedding induces convergence towards the LQG model, potentially establishing a crucial link between discrete graph structures and continuous random surfaces. The work builds upon the foundations laid by Tutte (1963), who established key principles concerning graph embeddings and spanning trees, extending these concepts to the more complex setting of infinite graphs.

Researchers propose several conjectures regarding stochastic processes, such as the FUSF and critical percolation, occurring on these infinite random planar maps. Critical percolation describes the behaviour of a random network at the point where it transitions from being disconnected to connected. The aim is to characterise the qualitative behaviour of these processes and offer insights into the interplay between graph structure and probabilistic dynamics. This study draws upon the foundations laid by Smirnov (2010), Kenyon (2000), and Teixeira (2010) in the fields of statistical physics and mathematical physics, leveraging their insights to understand the behaviour of these stochastic processes on random planar maps. These researchers have previously established rigorous results concerning the scaling limits of planar maps and related statistical models.