skip to content

Scale-free percolation

Friday 20th March 2015 - 10:00 to 11:00
INI Seminar Room 1
Co-authors: Mia Deijfen (Stockholm University), Gerard Hooghiemstra (Delft University of Technology)

We propose and study a random graph model on the hypercubic lattice that interpolates between models of scale-free random graphs and long-range percolation. In our model, each vertex $x$ has a weight $W_x$, where the weights of different vertices are i.i.d.\ random variables. Given the weights, the edge between $x$ and $y$ is, independently of all other edges, occupied with probability $1-{\mathrm{e}}^{-\lambda W_xW_y/|x-y|^{\alpha}}$, where (a) $\lambda$ is the percolation parameter, (b) $|x-y|$ is the Euclidean distance between $x$ and $y$, and (c) $\alpha$ is a long-range parameter. The most interesting behavior can be observed when the random weights have a power-law distribution, i.e., when $\mathbb{P}(W_x>w)$ is regularly varying with exponent $1-\tau$ for some $\tau>1$. In this case, we see that the degrees are infinite a.s.\ when $\gamma =\alpha(\tau-1)/d \leq 1$ or $\alpha\leq d$, while the degrees have a power-law distribution with exponent $\gamma$ when $\gamma>1$. Our main results describe phase transitions in the positivity of the percolation critical value and in the graph distances in the percolation cluster as $\gamma$ varies. Our results interpolate between those proved in inhomogeneous random graphs, where a wealth of further results is known, and those in long-range percolation. We also discuss many open problems, inspired both by recent work on long-range percolation (i.e., $W_x=1$ for every $x$), and on inhomogeneous random graphs (i.e., the model on the complete graph of size $n$ and where $|x-y|=n$ for every $x\neq y$).

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons