Critical percolation in high dimensions

University Of Washington, Seattle WA

Investigators

Abstract

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.