Session I.3 - Graph Theory and Combinatorics
Monday, June 12, 15:00 ~ 15:30
On percolation in locally dependent random graphs
Victor Falgas-Ravry
Umeå University, Sweden - This email address is being protected from spambots. You need JavaScript enabled to view it.
Consider a random subgraph of the square integer lattice $\mathbb{Z}^2$ obtained by including each edge independently at random with probability $p$, and omitting it otherwise. The Harris--Kesten theorem states that if $p\leq 1/2$, then almost surely all connected components in this random graph model are finite, while if $p \gt 1/2$ then almost surely the model percolates and there exists a unique infinite connected component.
But now what if we introduced some local dependencies between the edges? More precisely, suppose each edge still has a probability $p$ of being included in our random subgraph, but its state (present/absent) may depend on the states of nearby edges. To what extent can we exploit such local dependencies to delay the emergence of an infinite component?
In this talk I will discuss this question, which first arose in work of Balister, Bollobás and Walters in 2005, as well as some recent progress around it.
Joint work with A. Nicholas Day (Umeå University, Sweden), Robert Hancock (Heidelberg Universität, Germany) and Vincent Pfenninger (University of Birmingham, UK).