We study random walks on the giant component of the ErdH{o}s-Renyi random graph ${cal G}(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order $log^2 n$. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(log n)$ and concentrates it (the cutoff phenomenon occurs): the typical mixing is at $( u {bf d})^{-1}log n pm (log n)^{1/2+o(1)}$, where $ u$ and ${bf d}$ are the speed of random walk and dimension of harmonic measure on a ${rm Poisson}(lambda)$-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.
We prove a conjecture raised by the work of Diaconis and Shahshahani (1981) about the mixing time of random walks on the permutation group induced by a given conjugacy class. To do this we exploit a connection with coalescence and fragmentation processes and control the Kantorovitch distance by using a variant of a coupling due to Oded Schramm. Recasting our proof in the language of Ricci curvature, our proof establishes the occurrence of a phase transition, which takes the following form in the case of random transpositions: at time $cn/2$, the curvature is asymptotically zero for $cle 1$ and is strictly positive for $c>1$.
We introduce particle systems in one or more dimensions in which particles perform branching Brownian motion and the population size is kept constant equal to $N > 1$, through the following selection mechanism: at all times only the $N$ fittest particles survive, while all the other particles are removed. Fitness is measured with respect to some given score function $s:R^d to R$. For some choices of the function $s$, it is proved that the cloud of particles travels at positive speed in some possibly random direction. In the case where $s$ is linear, we show under some assumptions on the initial configuration that the shape of the cloud scales like $log N$ in the direction parallel to motion but at least $c(log N)^{3/2}$ in the orthogonal direction for some $c > 0$. We conjecture that the exponent 3/2 is sharp. This result is equivalent to the following result of independent interest: in one-dimensional systems, the genealogical time is greater than $c(log N)^3$, thereby contributing a step towards the original predictions of Brunet and Derrida. We discuss several open problems and also explain how our results can be viewed as a rigorous justification of Weismanns arguments for the role of recombination in population genetics.
We introduce a Gibbs measure on nearest-neighbour paths of length $t$ in the Euclidean $d$-dimensional lattice, where each path is penalised by a factor proportional to the size of its boundary and an inverse temperature $beta$. We prove that, for all $beta>0$, the random walk condensates to a set of diameter $(t/beta)^{1/3}$ in dimension $d=2$, up to a multiplicative constant. In all dimensions $dge 3$, we also prove that the volume is bounded above by $(t/beta)^{d/(d+1)}$ and the diameter is bounded below by $(t/beta)^{1/(d+1)}$. Similar results hold for a random walk conditioned to have local time greater than $beta$ everywhere in its range when $beta$ is larger than some explicit constant, which in dimension two is the logarithm of the connective constant.
We consider critical branching Brownian motion with absorption, in which there is initially a single particle at $x > 0$, particles move according to independent one-dimensional Brownian motions with the critical drift of $-sqrt{2}$, and particles are absorbed when they reach zero. Here we obtain asymptotic results concerning the behavior of the process before the extinction time, as the position $x$ of the initial particle tends to infinity. We estimate the number of particles in the system at a given time and the position of the right-most particle. We also obtain asymptotic results for the configuration of particles at a typical time.
We consider branching Brownian motion on the real line with absorption at zero, in which particles move according to independent Brownian motions with the critical drift of $-sqrt{2}$. Kesten (1978) showed that almost surely this process eventually dies out. Here we obtain upper and lower bounds on the probability that the process survives until some large time $t$. These bounds improve upon results of Kesten (1978), and partially confirm nonrigorous predictions of Derrida and Simon (2007).
We show that an infinite Galton-Watson tree, conditioned on its martingale limit being smaller than $eps$, agrees up to generation $K$ with a regular $mu$-ary tree, where $mu$ is the essential minimum of the offspring distribution and the random variable $K$ is strongly concentrated near an explicit deterministic function growing like a multiple of $log(1/eps)$. More precisely, we show that if $muge 2$ then with high probability as $eps downarrow 0$, $K$ takes exactly one or two values. This shows in particular that the conditioned trees converge to the regular $mu$-ary tree, providing an example of entropic repulsion where the limit has vanishing entropy.
