It is proposed to study aspects of universality in critical percolation in various high- dimensional graphs. These graphs include lattices in dimension above six, Cayley graphs of finitely generated non-amenable groups and also finite graphs such as the complete graph, the Hamming hypercube and expanders. It is believed that critical percolation on these graphs is universal in the sense that the resulting percolated clusters exhibit the same mean-field discrete fractal geometry no matter what was the original underlying high-dimensional graph. This proposal highlights various problems in different settings and is aimed to obtain a better understanding of this phenomenon. Special attention is given to determining critical exponents and studying the behavior of the random walk on percolation clusters.
Percolation theory has its origin in an honest applied problem, namely, the study of flow through a disordered porous medium. In the model one randomly perturbs a lattice (or other symmetric graphs) and studies the structure and geometry of the resulting random graph. This theory is a rich source of fascinating, yet simple to state, problems. Furthermore, it is a fundamental tool in the exploding research area of "real" networks aimed to model the behavior of real-world complex networks such as the Internet graph, routing grids, neuron networks and even social networks. Many ideas in this line of research, such as power laws and scale-free phenomenon originate in percolation theory. This proposal studies several open problems and topics in this area, hoping to deliver new techniques and methods.
In this project high-dimensional percolation, random planar maps and other models of statistical physics were investigated. Several problems have been successfully studied and solved: A complete description of the phase transition for the giant component in critical hypercube percolation was obtained (answering a question of Borgs, Chayes, van der Hofstad, Slade and Spencer '06). In particular, it was shown that the scaling window for the emergence of the giant component scales like (volume)^{-1/3} and that this giant component is concentrated above the critical window. The 2001 recurrence conjecture (by Benjamini and Schramm '01) for uniform infinite planar triangulation was proved. In fact, a very general result was proved stating that any distributional limit of planar graphs such that the degree of the root has an exponential tail is recurrent. This is particularly useful in the setting of random planar maps where the assumption required holds quite naturally. The trace of the critical branching random walk in low dimensions (i.e., less than 6) was studied and was shown to have sublinear resistance in the distance (answering a question of Barlow, Jarai, Kumagai and Slade '06). This shows that the branching random walk exhibits two critical dimensions, namely, 6 and 4. A general framework for studying random and deterministic planar triangulation, their circle packing and random walks was obtained and used to prove many potential theoretic properties of random planar maps. In particular, it is shown that the Poisson boundary of deterministic hyperbolic triangulations of bounded degree, or any "random" hyperbolic triangulation can be identified with the geometric boundary provided by the celebrated Koebe's circle packing theorem.
