In this talk we are going to talk about a percolation process which arises from a Poissonian ensemble of simple random walk loops in Z^d, for three dimensions or more. This is a dependent percolation process, states of vertices have correlations which decay polynomially in the distance between said vertices. Furthermore, strong decoupling inequalities such as those available for the gaussian free field or the random interlacements processes are believed to be false in the loop percolation case. We present a weaker inequality, which holds for the loop ensemble, and nevertheless allows one to prove several results for this model which were previously out of reach.

For a graph G=(V,E), a subset R of V is a resolving set if for every pair of distinct nodes v₁, v₂ in V there is a (distinguishing) node w in R, for which the distances d(w,v₁) and d(w,v₂) are not equal. An equivalent definition of a resolving set R is that in a two-player localization game, no matter which node v_* Player 1 selects, Player 2 can guess v_* only from the distance queries d(w_i,v_*) for w_i in R. The metric dimension (MD) is defined as the minimum cardinality of R; it can be thought of as the minimum number of prewritten distance queries Player 2 needs to guess any v_* in V. In this talk we consider the sequential version of the MD (called SMD), which can be defined using the same localization game, except now the queries can be adaptive. We are interested how much adaptivity can help to reduce the number of required queries in G(n,p) random graphs with p>>log(n)/n. In the first part of the talk, we review the previous results of Bollobas, Mitsche and Pralat (2012) on the MD of G(n,p), including the observation that unlike most graph properties, the MD is not monotonic in p, instead it follows zig-zag behavior. In the second part of the talk, we introduce the main tools that allow us to extend these results to the SMD, and quantify reduction of the SMD compared to the MD. We will discuss connections with source localization of epidemic processes, binary search on graphs and the birthday paradox.
This is joint work with Patrick Thiran.