Arm exponents in high dimensional percolation (2009)
We study the probability that the origin is connected to the sphere of radius r (an arm event) in critical percolation in high dimensions, namely when the dimension d is large enough or when d>6 and...
A note about critical percolation on finite graphs (2009)
In this note we study the geometry of the largest component C_1 of critical percolation on a finite graph G which satisfies the finite triangle condition, defined by Borgs et al. There it is shown...
Is the critical percolation probability local? (2009)
Benjamini, Itai, Nachmias, Asaf, Peres, Yuval
We show that the critical probability for percolation on a d-regular non-amenable graph of large girth is close to the critical probability for percolation on an infinite d-regular tree. This is a...
The Alexander-Orbach conjecture holds in high dimensions (2008)
We examine the incipient infinite cluster (IIC) of critical percolation in regimes where mean-field behavior have been established, namely when the dimension d is large enough or when d>6 and the...
Testing the Expansion of a Graph (2008)
We study the problem of testing the expansion of graphs with bounded degree d in sublinear time. A graph is said to be an αexpander if every vertex set U ⊂ V of size at most 1|V | has a neigh-2...
Mean-field conditions for percolation on finite graphs (2007)
Let G_n be a sequence of finite transitive graphs with vertex degree d=d(n) and |G_n|=n. Denote by p^t(v,v) the return probability after t steps of the non-backtracking random walk on G_n. We show...
Critical percolation on random regular graphs (2007)
We describe the component sizes in critical independent p-bond percolation on a random d-regular graph on n vertices, where d \geq 3 is fixed and n grows. We prove mean-field behavior around the...
Critical random graphs: Diameter and mixing time (2007)
Let $\mathcal{C}_1$ denote the largest connected component of the critical Erd\H{o}s--R\'{e}nyi random graph $G(n,{\frac{1}{n}})$. We show that, typically, the diameter of $\mathcal{C}_1$ is of order...
Component sizes of the random graph outside the scaling window (2006)
We provide simple proofs describing the behavior of the largest component of the Erdos-Renyi random graph G(n,p) outside of the scaling window, p={1+\eps(n) \over n} where \eps(n) tends to 0, but...
Colouring complete bipartite graphs from random lists, Random Structures and Algorithms 29 (2006)
Michael Krivelevich, Asaf Nachmias
Abstract Let Kn,n be the complete bipartite graph with n vertices in each side. For each vertex drawuniformly at random a list of size k from a base set S of size s = s(n). In this paper we...
The critical random graph, with martingales (2005)
We give a short proof that the largest component of the random graph $G(n, 1/n)$ is of size approximately $n^{2/3}$. The proof gives explicit bounds for the probability that the ratio is very large...
Colouring complete bipartite graphs from random lists (2005)
Krivelevich, Michael, Nachmias, Asaf
Let $K_{n,n}$ be the complete bipartite graph with $n$ vertices in each side. For each vertex draw uniformly at random a list of size $k$ from a base set $S$ of size $s=s(n)$. In this paper we...
Colouring powers of cycles from random lists (2005)
Krivelevich, Michael, Nachmias, Asaf
Let $C_n^k$ be the $k$-th power of a cycle on $n$ vertices (i.e. the vertices of $C_n^k$ are those of the $n$-cycle, and two vertices are connected by an edge if their distance along the cycle is at...
Mixing for Markov Chains and Spin Systems (2005)
Yuval Peres, Ra Kliem, Lionel Levine, Yun Long, Asaf Nachmias, Alex Skorokhod, ...
for help preparing these notes. These notes have not been subjected to the usual scrutiny reserved for formal publications. –Yuval Lecture 1: Introduction and total variation distance