BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Asaf Nachmias contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Let $S_k$ be a sequence of compact hyperbolic surfaces of increasing volume which locally converges to a random rooted surface. We show that if the normalized sum of the reciprocal lengths of very short simple closed geodesics converges to 0, then the normalized logarithm of the determinant of the Laplacian of $S_k$ converges to a constant depending only the law of the limiting surface.
We show that the Brownian continuum random tree is the Gromov-Hausdorff-Prohorov scaling limit of the uniform spanning tree on high-dimensional graphs including the $d$-dimensional torus $\mathbb{Z}_n^d$ with $d>4$, the hypercube $\{0,1\}^n$, and transitive expander graphs. Several corollaries for associated quantities are then deduced: convergence in distribution of the rescaled diameter, height and simple random walk on these uniform spanning trees to their continuum analogues on the continuum random tree.
We study the simple random walk on stochastic hyperbolic half planar triangulations constructed in Angel and Ray [3]. We show that almost surely the walker escapes the boundary of the map in positive speed and that the return probability to the starting point after n steps scales like $\exp(-cn^{1/3})$.
We show that crossing probabilities in 2D critical site percolation on the triangular lattice in a piecewise analytic Jordan domain converge with power law rate in the mesh size to their limit given by the Cardy-Smirnov formula. We use this result to obtain new upper and lower bounds of exp(O(sqrt(log log R))) R^(-1/3) for the probability that the cluster at the origin in the half-plane has diameter R, improving the previously known estimate of R^(-1/3+o(1)).
We show that the distribution of the first return time $τ$ to the origin, v, of a simple random walk on an infinite recurrent graph is heavy tailed and nonconcentrated. More precisely, if $d_v$ is the degree of v, then for any $t\geq1$ we have \[\mathbf{P}_v(τ\ge t)\ge\frac{c}{d_v\sqrt{t}}\] and \[\mathbf{P}_v(τ=t\midτ\geq t)\leq\frac{C\log(d_vt)}{t}\] for some universal constants $c>0$ and $C<\infty$. The first bound is attained for all t when the underlying graph is $\mathbb{Z}$, and as for the second bound, we construct an example of a recurrent graph G for which it is attained for infinitely many t's. Furthermore, we show that in the comb product of that graph G with $\mathbb{Z}$, two independent random walks collide infinitely many times almost surely. This answers negatively a question of Krishnapur and Peres [Electron. Commun. Probab. 9 (2004) 72-81] who asked whether every comb product of two infinite recurrent graphs has the finite collision property.
We study bond percolation on the Hamming hypercube {0,1}^m around the critical probability p_c. It is known that if p=p_c(1+O(2^{-m/3})), then with high probability the largest connected component C_1 is of size Theta(2^{2m/3}) and that this quantity is non-concentrated. Here we show that for any sequence eps_m such that eps_m=o(1) but eps_m >> 2^{-m/3} percolation on the hypercube at p_c(1+eps_m) has |C_1| = (2+o(1)) eps_m 2^m and |C_2| = o(eps_m 2^m) with high probability, where C_2 is the second largest component. This resolves a conjecture of Borgs, Chayes, the first author, Slade and Spencer [17].
In this note we show that percolation on non-amenable Cayley graphs of high girth has a phase of non-uniqueness, i.e., p_c < p_u. Furthermore, we show that percolation and self-avoiding walk on such graphs have mean-field critical exponents. In particular, the self-avoiding walk has positive speed.
We prove that any distributional limit of finite planar graphs in which the degree of the root has an exponential tail is almost surely recurrent. As a corollary, we obtain that the uniform infinite planar triangulation and quadrangulation (UIPT and UIPQ) are almost surely recurrent, resolving a conjecture of Angel, Benjamini and Schramm. We also settle another related problem of Benjamini and Schramm. We show that in any bounded degree, finite planar graph the probability that the simple random walk started at a uniform random vertex avoids its initial location for T steps is at most C/log T.
The purpose of this note is twofold. First, we survey the study of the percolation phase transition on the Hamming hypercube {0,1}^m obtained in the series of papers [9,10,11,24]. Secondly, we explain how this study can be performed without the use of the so-called "lace-expansion" technique. To that aim, we provide a novel simple proof that the triangle condition holds at the critical probability. We hope that some of these techniques will be useful to obtain non-perturbative proofs in the analogous, yet much more difficult study on high-dimensional tori.
The Swendsen-Wang dynamics is a Markov chain widely used by physicists to sample from the Boltzmann-Gibbs distribution of the Ising model. Cooper, Dyer, Frieze and Rue proved that on the complete graph K_n the mixing time of the chain is at most O(n^{1/2}) for all non-critical temperatures. In this paper we show that the mixing time is Theta(1) in high temperatures, Theta(log n) in low temperatures and Theta(n^{1/4}) at criticality. We also provide an upper bound of O(log n) for Swendsen-Wang dynamics for the q-state ferromagnetic Potts model on any tree with n vertices.
The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovasz and Vu yielded a (log log n)^2 polynomial time approximation. We refine this upper bound, and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdos-Renyi random graph G(n,c/n) in the supercritical regime with c>1 fixed, is asymptotic to f(c) n \log^2 n, where f(c) tends to 1 as c tends to 1. However, our new bound implies that the cover time for the critical Erdos-Renyi random graph G(n,1/n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube {0,1}^n, on high-girth expanders, and on tori Z_n^d for fixed large d. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman, is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4.
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 or very small.