One-dimensional long-range diffusion-limited aggregation I (2009)
Amir, Gideon, Angel, Omer, Benjamini, Itai, Kozma, Gady
We examine diffusion-limited aggregation generated by a random walk on Z with long jumps. We derive upper and lower bounds on the growth rate of the aggregate as a function of the number moments a...
Lack of Sphere Packing of Graphs via Non-Linear Potential Theory (2009)
Benjamini, Itai, Schramm, Oded
It is shown that there is no quasi-sphere packing of the lattice grid Z^{d+1} or a co-compact hyperbolic lattice of H^{d+1} or the 3-regular tree \times Z, in R^d, for all d. A similar result is...
Local limit of packable graphs (2009)
Benjamini, Itai, Curien, Nicolas
We adapt some planar results into higher dimensions. In particular, it is shown that every unbiased local limit of graphs sphere packed in R^d is d-parabolic (under some additional boundedness...
Sharp threshold for percolation on expanders (2009)
Benjamini, Itai, Boucheron, Stephane, Lugosi, Gabor, Rossignol, Raphael
We study the appearance of the giant component in random subgraphs of a given finite graph G=(V,E) in which each edge is present independently with probability p. We show that if G is an expander...
Stationary map coloring (2009)
Angel, Omer, Benjamini, Itai, Gurel-Gurevich, Ori, Meyerovitch, Tom, Peled, Ron
We consider a planar Poisson process and its associated Voronoi map. We show that there is a proper coloring with 6 colors of the map which is a deterministic isometry-equivariant function of the...
Sums and products along sparse graphs (2009)
Alon, Noga, Angel, Omer, Benjamini, Itai, Lubetzky, Eyal
In their seminal paper from 1983, Erd\H{o}s and Szemer\'edi showed that any $n$ distinct integers induce either $n^{1+\epsilon}$ distinct sums of pairs or that many distinct products, and conjectured...
ABSTRACT Routing Complexity of Faulty Networks (2009)
Omer Angel, Eran Ofek, Itai Benjamini
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Entropy of Random Walk Range (2009)
Benjamini, Itai, Kozma, Gady, Yadin, Ariel, Yehudayoff, Amir
We study the entropy of the set traced by an $n$-step random walk on $\Z^d$. We show that for $d \geq 3$, the entropy is of order $n$. For $d = 2$, the entropy is of order $n/\log^2 n$. These values...
Poisson asymptotics for random projections of points on a high-dimensional sphere (2009)
Benjamini, Itai, Schramm, Oded, Sodin, Sasha
Project a collection of points on the high-dimensional sphere onto a random direction. If most of the points are sufficiently far from one another in an appropriate sense, the projection is locally...
Cutpoints and resistance of random walk paths (2009)
Benjamini, Itai, Gurel-Gurevich, Ori, Schramm, Oded
We construct a bounded degree graph G, such that a simple random walk on it is transient but the random walk path (i.e., the subgraph of all the edges the random walk has crossed) has only finitely...
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...
Balanced Allocation: Memory Performance Tradeoffs (2009)
Benjamini, Itai, Makarychev, Yury
Suppose that we sequentially put $n$ balls into $n$ bins. If we put each ball into a random bin then the heaviest bin will contain $\log n /\log\log n$ balls (w.h.p.). However, Azar, Broder, Karlin...
On k-wise independent distributions and Boolean functions (2008)
Itai Benjamini, Ori Gurel-gurevich, Ron Peled
We pursue a systematic study of the following problem. Let f: {0, 1} n → {0, 1} be a (usually monotone) boolean function whose behaviour is well understood when the input bits are identically...
Noga Alon, Itai Benjamini, Alan Stacey
on finite graphs and isoperimetric inequalities
Spacings and pair correlations for finite Bernoulli convolutions (2008)
Benjamini, Itai, Solomyak, Boris
We consider finite Bernoulli convolutions with a parameter $1/2 < r < 1$ supported on a discrete point set, generically of size $2^N$. These sequences are uniformly distributed with respect to the...
Visibility to infinity in the hyperbolic plane, despite obstacles (2008)
Benjamini, Itai, Jonasson, Johan, Schramm, Oded, Tykesson, Johan
Suppose that $Z$ is a random closed subset of the hyperbolic plane $\H^2$, whose law is invariant under isometries of $\H^2$. We prove that if the probability that $Z$ contains a fixed ball of radius...
KPZ in one dimensional random geometry of multiplicative cascades (2008)
Benjamini, Itai, Schramm, Oded
We prove a formula relating the Hausdorff dimension of a subset of the unit interval and the Hausdorff dimension of the same set with respect to a random path matric on the interval, which is...
A double phase transition arising from Brownian entropic repulsion (2008)
Benjamini, Itai, Berestycki, Nathanael
We analyze one-dimensional Brownian motion conditioned on a self-repelling behaviour. In the main result of this paper, it is shown that a double phase transition occurs when the growth of the local...
Brownian Entropic Repulsion (2008)
Benjamini, Itai, Berestycki, Nathanael
We consider one-dimensional Brownian motion conditioned (in a suitable sense) to have a local time at every point and at every moment bounded by some fixed constant. Our main result shows that a...
WAITING FOR A BAT TO FLY BY (IN POLYNOMIAL TIME) (2008)
Itai Benjamini, Gady Kozma, László Lovász, Dan Romik
Abstract. We observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition...
ABSTRACT Routing Complexity of Faulty Networks (2008)
Omer Angel, Eran Ofek, Itai Benjamini
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
The isoperimetric constant of the random graph process, preprint (2008)
Itai Benjamini, Simi Haber, Michael Krivelevich, Eyal Lubetzky
2\Delta graphs, where eG(0) is the edgeless graph on n vertices, and eG(t) is the result of addingan edge to e G(t- 1), uniformly distributed over all the missing edges. We show that in almost every...
Every Minor-Closed Property of Sparse Graphs is Testable (2008)
Benjamini, Itai, Schramm, Oded, Shapira, Asaf
Suppose $G$ is a graph with degrees bounded by $d$, and one needs to remove more than $\epsilon n$ of its edges in order to make it planar. We show that in this case the statistics of local...
Giant component and vacant set for random walk on a discrete torus (2008)
Benjamini, Itai, Sznitman, Alain-Sol
We consider random walk on a discrete torus $E$ of side-length $N$, in sufficiently high dimension $d$. We investigate the percolative properties of the vacant set corresponding to the collection of...
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm
Abstract. We study uniform spanning forest measures on infinite graphs, which are weak limits of uniform spanning tree measures from finite subgraphs. These limits can be taken with free (FSF) or...
Percolation In The Hyperbolic Plane (Extended Abstract) (2007)
ITAI BENJAMINI AND ODED SCHRAMM The Voronoi model for percolation in H 2 . Percolation has been studied extensively in R d and in lattices of R d . In [1], we have proposed some conjectures about...
On random graph homomorphisms into Z (2007)
Itai Benjamini, Elchanan Mossel
Given a bipartite connected nite graph G = (V; E) and a vertex v0 2 V, we consider uniform probability measure on the set of graph homomorphisms f: V! Z satisfying f(v0) = 0. This measure can be...
Which properties of a random sequence are dynamically sensitive? (2007)
Itai Benjamini, Olle Haggstrom, Yuval Peres, Jeffrey E. Steif
Consider a sequence of i.i.d. random variables, where each variable is refreshed (i.e., replaced by an independent variable with the same law) independently, according to a Poisson clock. At any...
On random graph homomorphisms into Z (2007)
Itai Benjamini, Olle Haggstrom, Elchanan Mossel
Given a bipartite connected finite graph G = (V; E) and a vertex v0 2 V, we consider uniform probability measure on the set of graph homomorphisms f: V! Z satisfying f(v0) = 0. This measure can be...
Maximal Arithmetic Progressions in Random Subsets (2007)
Benjamini, Itai; Weizmann Institute Of Science; Itai.benjamini@weizmann.ac.il, Yadin, Ariel; Weizmann Institute Of Science; Ariel.yadin@weizmann.ac.il, Zeitouni, Ofer; University Of Minnesota; Zeitouni@math.umn.edu
Let U(N) denote the maximal length of arithmetic progressions in a random uniform subset of {0,1}N. By an application of the Chen-Stein method, we show that U(N)- 2 log(N)/log(2) converges in law to...
Dimension Reduction for the Hyperbolic Space (2007)
Benjamini, Itai, Makarychev, Yury
A dimension reduction for the hyperbolic space is established. When points are far apart an embedding with bounded distortion into the hyperbolic plane is achieved.
Exponential clogging time for a one dimensional DLA (2007)
Benjamini, Itai, Hoffman, Christopher
When considering DLA on a cylinder it is natural to ask how many particles it takes to clog the cylinder, e.g. modeling clogging of arteries. In this note we formulate a very simple DLA clogging...
Maximal Arithmetic Progressions in Random Subsets (2007)
Benjamini, Itai, Yadin, Ariel, Zeitouni, Ofer
Let U(N) denote the maximal length of arithmetic progressions in a random uniform subset of {0,1}^N. By an application of the Chen-Stein method, we show that U(N)- 2 log(N)/log(2) converges in law to...
Effective resistance on random electrical networks (2007)
Benaim, Michel, Benjamini, Itai, Rossignol, Raphael
This paper has been withdrawn. See v1 still available to understand the problem: Proposition 2.2 is false. The error in the proof is in claim (3). Then, the whole paper collapses. We do not have any...
Random Graph-Homomorphisms and Logarithmic Degree (2007)
Benjamini, Itai; Weizmann Institute; Itai.benjamini@weizmann.ac.il, Yadin, Ariel; Weizmann Institute; Ariel.yadin@weizmann.ac.il, Yehudayoff, Amir; Weizmann Institute; Amir.yehudayoff@weizmann.ac.il
A graph homomorphism between two graphs is a map from the vertex set of one graph to the vertex set of the other graph, that maps edges to edges. In this note we study the range of a uniformly chosen...
Random Graph-Homomorphisms and Logarithmic Degree (2007)
Benjamini, Itai; Weizmann Institute; Itai.benjamini@weizmann.ac.il, Yadin, Ariel; Weizmann Institute; Ariel.yadin@weizmann.ac.il, Yehudayoff, Amir; Weizmann Institute; Amir.yehudayoff@weizmann.ac.il
A graph homomorphism between two graphs is a map from the vertex set of one graph to the vertex set of the other graph, that maps edges to edges. In this note we study the range of a uniformly chosen...
On the range of the simple random walk bridge on groups (2007)
Benjamini, Itai; Weizmann Institute Of Science; Itai.benjamini@gmail.com, Izkovsky, Roey; Weizmann Institute Of Science; Roey.izkovsky@gmail.com, Kesten, Harry; Cornell University; Kesten@math.cornell.edu
Abstract. Let G be a vertex transitive graph. A study of the range of simple random walk on G and of its bridge is proposed. While it is expected that on a graph of polynomial growth the sizes of the...
On the range of the simple random walk bridge on groups (2007)
Benjamini, Itai; Weizmann Institute Of Science; Itai.benjamini@gmail.com, Izkovsky, Roey; Weizmann Institute Of Science; Roey.izkovsky@gmail.com, Kesten, Harry; Cornell University; Kesten@math.cornell.edu
Abstract. Let G be a vertex transitive graph. A study of the range of simple random walk on G and of its bridge is proposed. While it is expected that on a graph of polynomial growth the sizes of the...
Long Range Percolation Mixing Time (2007)
Benjamini, Itai, Berger, Noam, Yadin, Ariel
We provide an estimate, sharp up to poly-logarithmic factors, of the asymptotically almost sure mixing time of the graph created by long-range percolation on the cycle of length N (Z/NZ). While it is...
The Biham-Middleton-Levine traffic model for a single junction (2007)
Benjamini, Itai, Gurel-Gurevich, Ori, Izkovsky, Roey
In the Biham-Middleton-Levine traffic model cars are placed with some density p on a two dimensional torus, and move according to a (simple) set of predefined rules. Computer simulations show this...
The birthday problem and Markov chain Monte Carlo (2007)
We study the problem of generating a sample from the stationary distribution of a Markov chain, given a method to simulate the chain. We give an approximation algorithm for the case of a random walk...
Diffusion Limited Aggregation on a Cylinder (2007)
We consider the DLA process on a cylinder G x N. It is shown that this process "grows arms", provided that the base graph G has small enough mixing time. Specifically, if the mixing time of G is at...
Every minor-closed property of sparse graphs is testable (2007)
Itai Benjamini, Oded Schramm, Asaf Shapira
Suppose G is a graph of bounded degree d, and one needs to remove ɛn of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around vertices of G is...
Every minor-closed property of sparse graphs is testable (2007)
Itai Benjamini, Oded Schramm, Asaf Shapira
Suppose G is a graph with degrees bounded by d, and one needs to remove more than ǫn of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around...
Maximal Arithmetic Progressions in Random Subsets (2007)
Itai Benjamini, Ariel Yadin, Ofer Zeitouni
Let U (N) denote the maximal length of arithmetic progressions in a random uni-form subset of {0,1} N. By an application of the Chen-Stein method, we show that U (N) −2log N / log 2 converges in...
Every minor-closed property of sparse graphs is testable (2007)
Itai Benjamini, Oded Schramm, Asaf Shapira
Testing a property P of graphs in the bounded degree model is the following computational problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the...
Random Graph-Homomorphisms and Logarithmic Degree (2006)
Benjamini, Itai, Yadin, Ariel, Yehudayoff, Amir
A graph homomorphism between two graphs is a map from the vertex set of one graph to the vertex set of the other graph, that maps edges to edges. In this note we study the range of a uniformly chosen...
Giant Component and Vacant Set for Random Walk on a Discrete Torus (2006)
Benjamini, Itai, Sznitman, Alain-Sol
We consider random walk on a discrete torus E of side-length N, in sufficiently high dimension d. We investigate the percolative properties of the vacant set corresponding to the collection of sites...
Non-backtracking random walks mix faster (2006)
Alon, Noga, Benjamini, Itai, Lubetzky, Eyal, Sodin, Sasha
We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as...
The mixing time of the giant component of a random graph (2006)
Benjamini, Itai, Kozma, Gady, Wormald, Nicholas
We show that the total variation mixing time of the simple random walk on the giant component of supercritical Erdos-Renyi graphs is log^2 n. This statement was only recently proved, independently,...
Submean variance bound for effective resistance of random electric networks (2006)
Benjamini, Itai, Rossignol, Raphael
We study a model of random electric networks with Bernoulli resistances. In the case of the lattice Z^2, we show that the point-to-point effective resistance between 0 and a vertex v has a variance...
Geodesics and almost geodesic cycles in random regular graphs (2006)
Benjamini, Itai, Hoppen, Carlos, Ofek, Eran, Pralat, Pawel, Wormald, Nick
A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and...
Benjamini, Itai, Gurel-Gurevich, Ori, Solomyak, Boris
We consider a Branching Random Walk on $\R$ whose step size decreases by a fixed factor, $0 (\sqrt{5}-1)/2$ the support of the measure is a.s. the closure of its interior; (3) for Pisot $1/b$ the...
Transience of percolation clusters on wedges (2006)
Berger, Noam; University Of California, Los Angeles; Berger@math.ucla.edu, Benjamini, Itai; The Weizmann Institute; Itai@wisdom.weizmann.ac.il, Angel, Omer; University Of British Columbia; Angel@math.ubc.ca, Peres, Yuval; The University Of California, Berkeley; Peres@stat.berkeley.edu
We study random walks on supercritical percolation clusters on wedges in $Z^3$, and show that the infinite percolation cluster is (a.s.) transient whenever the wedge is transient. This solves a...
Austin, Tim D., Benjamini, Itai
For any initial configuration of fewer than N/2 cars the BML model will self organize to attain speed one. On the other hand, there is a configuration of size m in which no car can move if and only...
Random walks with k-wise independent increments (2006)
Benjamini, Itai; The Weizmann Institute Of Science; Itai@wisdom.weizmann.ac.il, Kozma, Gady; The Weizmann Institute Of Science; Gady@ias.edu, Romik, Dan; University Of California, Berkeley; Romik@stat.berkeley.edu
We construct examples of a random walk with pairwise-independent steps which is almost surely bounded, and for any m and k a random walk with k-wise independent steps which has no stationary...
On the range of the simple random walk bridge on groups (2006)
Benjamini, Itai, Izkovsky, Roey, Kesten, Harry
Let G be a vertex transitive graph. A study of the range of simple random walk on G and of its bridge is proposed. While it is expected that on a graph of polynomial growth the sizes of the range of...
Recurrence of random walk traces (2006)
Benjamini, Itai, Gurel-Gurevich, Ori, Lyons, Russell
We show that the edges crossed by a random walk in a network form a recurrent graph a.s. In fact, the same is true when those edges are weighted by the number of crossings.
Non-backtracking random walks mix faster (2006)
Noga Alon, Itai Benjamini, Eyal Lubetzky, Sasha Sodin
We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as...
Benjamini, Itai, Burdzy, Krzysztof, Chen, Zhen-Qing
A pair of Markov processes is called a Markov coupling if both processes have the same transition probabilities and the pair is also a Markov process. We say that a coupling is ``shy'' if the...
Excited random walk against a wall (2005)
Amir, Gideon, Benjamini, Itai, Kozma, Gady
We analyze random walk in the upper half of a three dimensional lattice which goes down whenever it encounters a new vertex, a.k.a. excited random walk. We show that it is recurrent with an expected...
The isoperimetric constant of the random graph process (2005)
Benjamini, Itai, Haber, Simi, Krivelevich, Michael, Lubetzky, Eyal
The isoperimetric constant of a graph $G$ on $n$ vertices, $i(G)$, is the minimum of $\frac{|\partial S|}{|S|}$, taken over all nonempty subsets $S\subset V(G)$ of size at most $n/2$, where $\partial...
Almost Sure Recurrence of the Simple Random Walk Path (2005)
Benjamini, Itai, Gurel-Gurevich, Ori
It is shown that the path of a simple random walk on any graph, consisting of all vertices visited and edges crossed by the walk, is almost surely a recurrent subgraph.
Mixing times of the biased card shuffling and the asymmetric exclusion process (2005)
Benjamini, Itai, Berger, Noam, Hoffman, Christopher, Mossel, Elchanan
Consider the following method of card shuffling. Start with a deck of N cards numbered 1 through N. Fix a parameter p between 0 and 1. In this model a "shuffle" consists of uniformly selecting a pair...
Routing complexity of faulty networks (2005)
Omer Angel, Itai Benjamini, Eran Ofek, Udi Wieder
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Routing complexity of faulty networks (2005)
Omer Angel, Itai Benjamini, Eran Ofek, Udi Wieder
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Mixing times of the biased card shuffling and the asymmetric exclusion process (2005)
Itai Benjamini, Noam Berger, Christopher Hoffman
Abstract. Consider the following method of card shuffling. Start with a deck of N cards numbered 1 through N. Fix a parameter p between 0 and 1. In this model a “shuffle ” consists of uniformly...
Routing complexity of faulty networks (2005)
Omer Angel, Itai Benjamini, Eran Ofek, Udi Wieder
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Itai Benjamini, Oded Schramm, David B. Wilson
A Boolean function of n bits is balanced if it takes the value 1 with probability 1/2. We exhibit a balanced Boolean function with a randomized evaluation procedure (with probability 0 of making a...
Benjamini, Itai, Schramm, Oded, Wilson, David B.
A Boolean function of n bits is balanced if it takes the value 1 with probability 1/2. We exhibit a balanced Boolean function with a randomized evaluation procedure (with probability 0 of making a...
Geometry of the uniform spanning forest: Transitions in dimensions 4, 8, 12,... (2004)
Benjamini, Itai, Kesten, Harry, Peres, Yuval, Schramm, Oded
The uniform spanning forest (USF) in $\Zd$ is the weak limit of random, uniformly chosen, spanning trees in $[-n,n]^d$. Pemantle proved that the USF consists a.s. of a single tree if and only if $d...
Routing Complexity of Faulty Networks (2004)
Angel, Omer, Benjamini, Itai, Ofek, Eran, Wieder, Udi
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Percolation on finite graphs and isoperimetric inequalities (2004)
Alon, Noga, Benjamini, Itai, Stacey, Alan
Consider a uniform expanders family Gn with a uniform bound on the degrees. It is shown that for any p and c>0, a random subgraph of Gn obtained by retaining each edge, randomly and independently,...
Random walks with $k$-wise independent increments (2004)
Benjamini, Itai, Kozma, Gady, Romik, Dan
We construct examples of a random walk with pairwise-independent steps which is almost-surely bounded, and for any $m$ and $k$ a random walk with $k$-wise independent steps which has no stationary...
Random Walks in Varying Dimensions (2004)
Benjamini, Itai, Pemantle, Robin, Peres, Yuval
We establish recurrence criteria for sums of independent random variables which take values in Euclidean lattices of varying dimension. In particular, we describe transient inhomogenous random walks...
Martin Capacity for Markov Chains (2004)
Benjamini, Itai, Pemantle, Robin, Peres, Yuval
The probability that a transient Markov chain, or a Brownian path, will ever visit a given set Lambda, is classically estimated using the capacity of Lambda with respect to the Green kernel G(x,y)....
Waiting for a bat to fly by (in polynomial time) (2003)
Benjamini, Itai, Kozma, Gady, Lovasz, Laszlo, Romik, Dan, Tardos, Gabor
We observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition matrix. This...
Instability of set recurrence and Green's function on groups with the Liouville property (2003)
Benjamini, Itai, Revelle, David
Let $\mu$ and $\nu$ be probability measures on a group \Gamma and let G_\mu and G_\nu denote Green's function with respect to \mu and \nu . The group \Gamma is said to admit instability of Green's...
First passage percolation has sublinear distance variance (2003)
Benjamini, Itai, Kalai, Gil, Schramm, Oded
Let $0 < a < b < \infty$, and for each edge e of $\Z^d$ let $\omega_e=a$ or $\omega_e=b$, each with probability $1/2$, independently. This induces a random metric $\dist_\omega$ on the vertices of...
Loop-erased random walk on a torus in dimensions 4 and above (2003)
Sharp estimates for the length of loop erased random walk between two vertices on the [n]^d -torus, d > 4, are established. The mean length is order n^{d/2} . In dimension 4 we have only an upper...
Benjamini, Itai, Hoffman, Chris
$\omega$-periodic graphs are introduced and studied. These are graphs which arise as the limits of periodic extensions of the nearest neighbor graph on the integers. We observe that all bounded...
Boundary Trace of Reflecting Brownian Motions (2003)
Benjamini, Itai, Chen, Zhen-Qing, Rohde, Steffen
A uniform dimensional result for normally reflected Brownian motion (RBM) in a large class of non-smooth domains is established. Exact Hausdorff dimensions for the boundary occupation time and the...
A Phase Transition for the Metric Distortion of Percolation on the Hypercube (2003)
Let H_n be the hypercube {0,1}^n, and let H_{n,p} denote the same graph with Bernoulli bond percolation with parameter p=n^-\alpha. It is shown that at \alpha=1/2 there is a phase transition for the...
Benjamini, Itai; Weizmann Institute, Rehovot 76100, Israel; Itai@wisdom.weizmann.ac.il, Wilson, David Bruce; Microsoft Research; Dbwilson@microsoft.com
A random walk on Zd is excited if the first time it visits a vertex there is a bias in one direction, but on subsequent visits to that vertex the walker picks a neighbor uniformly at random. We show...
Pinched exponential volume growth implies an infinite dimensional isoperimetric inequality (2003)
Benjamini, Itai, Schramm, Oded
Let $G$ be a graph which satisfies $c^{-1} a^r \le |B(v,r)| \le c a^r$, for some constants $c,a>1$, every vertex $v$ and every radius $r$. We prove that this implies the isoperimetric inequality...
Benjamini, Itai, Wilson, David B.
A random walk on Z^d is excited if the first time it visits a vertex there is a bias in one direction, but on subsequent visits to that vertex the walker picks a neighbor uniformly at random. We show...
Random Walks that Avoid Their Past Convex Hull (2003)
Angel, Omer; Weizmann Institute Of Science; Omer@wisdom.weizmann.ac.il, Benjamini, Itai; Weizmann Institute Of Science; Itai@wisdom.weizmann.ac.il, Virág, Bálint; MIT; Balint@math.mit.edu
We explore planar random walk conditioned to avoid its past convex hull. We prove that it escapes at a positive lim sup speed. Experimental results show that fluctuations from a limiting direction...
Which properties of a random sequence are dynamically sensitive? (2003)
Benjamini, Itai, Häggström, Olle, Peres, Yuval, Steif, Jeffrey E.
Consider a sequence of i.i.d.\ random variables, where each variable is refreshed (i.e., replaced by an independent variable with the same law) independently, according to a Poisson clock. At any...
A Resistance Bound via an Isoperimetric Inequality (2002)
An isoperimetric upper bound on the resistance is given. As a corollary we resolve two problems, regarding mean commute time on finite graphs and resistance on percolation clusters. Further...
Benjamini, Itai, Merenkov, Sergei, Schramm, Oded
Consider a simply connected Riemann surface represented by a Speiser graph. Nevanlinna asked if the type of the surface is determined by the mean excess of the graph: whether mean excess zero implies...
Random walks that avoid their past convex hull (2002)
Angel, Omer, Benjamini, Itai, Virag, Balint
We introduce planar random walk conditioned to avoid its past convex hull, and we show that it escapes at a positive limsup speed. Experimental results show that fluctuations from a limiting...
Mixing times of the biased card shuffling and the asymmetric exclusion process (2002)
Benjamini, Itai, Berger, Noam, Hoffman, Christopher, Mossel, Elchanan
Consider the following method of card shuffling. Start with a deck of $N$ cards numbered 1 through N. Fix a parameter $p$ between 0 and 1. In this model a ``shuffle'' consists of uniformly selecting...
Percolation on finite graphs and isoperimetric inequalities (2002)
Alon, Noga, Benjamini, Itai, Stacey, Alan
Consider a uniform expanders family G_n with a uniform bound on the degrees. It is shown that for any p and c>0, a random subgraph of G_n obtained by retaining each edge, randomly and independently,...
Transience of percolation clusters on wedges (2002)
Angel, Omer, Benjamini, Itai, Berger, Noam, Peres, Yuval
We study random walks on supercritical percolation clusters on wedges in $\Z^3$, and show that the infinite percolation cluster is (a.s.) transient whenever the wedge is transient. This solves a...
First Passage Percolation Has Sublinear Distance Variance (2002)
Benjamini, Itai, Kalai, Gil, Schramm, Oded
Let $0
Determining the Genus of a Map by Local Observation of a Simple Random Process (2002)
Benjamini, Itai, Lovasz, Laszlo
Given a graph embedded in an orientable surface, a process consisting of random excitations and random node and face balancing is constructed and analyzed. It is shown that given a priori bounds g'...
Determining the genus of a map by local observation of a simple random process (2002)
Given a graph embedded in an orientable surface, a process with stationary increments, consisting of random excitations and random node and face balancing, is constructed and analyzed. It is shown...
Mixing Times of the biased card shuffling and the asymmetric exclusion process (2002)
Itai Benjamini, Noam Berger, Christopher Hoffman, Elchanan Mossel
Consider the following method of card shu#ing. Start with a deck of N cards numbered 1 through N . Fix a parameter p between 0 and 1. In this model a "shu#e" consists of uniformly selecting...
First Passage Percolation Has Sublinear Distance Variance (2002)
Itai Benjamini, Gil Kalai, Oded Schramm
Let 0 < a < b < 1, and for each edge e of Z let ! e = a or ! e = b, each with probability 1=2, independently. This induces a random metric dist ! on the vertices of Z , called rst passage...
Random Walks That Avoid Their Past Convex Hull (2002)
Omer Angel, Itai Benjamini, Bálint Virág
We explore planar random walk conditioned to avoid its past convex hull. We prove that it escapes at a positive lim sup speed. Experimental results show that uctuations from a limiting direction are...
Recurrence of Distributional Limits of Finite Planar Graphs (2001)
Benjamini, Itai; The Weizmann Institute Of Science; Itai@wisdom.weizmann.ac.il, Schramm, Oded; Microsoft Research; Schramm@microsoft.com
Suppose that Gj is a sequence of finite connected planar graphs, and in each Gj a special vertex, called the root, is chosen randomly-uniformly. We introduce the notion of a distributional limit G of...
Geometry of the Uniform Spanning Forest: Transitions in Dimensions 4, 8, 12 (2001)
Benjamini, Itai, Kesten, Harry, Peres, Yuval, Schramm, Oded
The uniform spanning forest (USF) in Z^d is the weak limit of random, uniformly chosen, spanning trees in [-n,n]^d. Pemantle proved that the USF consists a.s. of a single tree if and only if d
percolation on finite graphs (2001)
The asymptotic study of percolation on finite transitive graphs is considered. Several questions and very few answers regarding percolation on finite graphs are presented.
Uniform spanning forests (2001)
Benjamini, Itai, Lyons, Russell, Peres, Yuval, Schramm, Oded
We study uniform spanning forest measures on infinite graphs, which are weak limits of uniform spanning tree measures from finite subgraphs. These limits can be taken with free (FSF )or wired (WSF )...
Uniform spanning forests (2001)
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm
Abstract. We study uniform spanning forest measures on infinite graphs, which are weak limits of uniform spanning tree measures from finite subgraphs. These limits can be taken with free (FSF) or...
Gaussian Random Field and the Range of Random Graph Homomorphisms into Z (2001)
The Erwin, Schrödinger International Boltzmanngasse, Itai Benjamini, Gideon Schechtman, Itai Benjamini, Gideon Schechtman
Bounds on the range of random graph homomorphism into Z, and the maximal height difference of the Gaussian random field, are presented. 1
The Diameter of Long-Range Percolation Clusters on Finite Cycles (2000)
Bounds for the diameter and for the expansion of long-range percolation clusters on the cycle $\Z / N\Z$ are given.
On the mixing time of simple random walk on the super critical percolation cluster (2000)
Benjamini, Itai, Mossel, Elchanan
We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in $\Z^d$. We show that for $d \geq 2$ and $p > p_c(\Z^d)$,...
Recurrence of Distributional Limits of Finite Planar Graphs (2000)
Benjamini, Itai, Schramm, Oded
Suppose that $G_j$ is a sequence of finite connected planar graphs, and in each $G_j$ a special vertex, called the root, is chosen randomly-uniformly. We introduce the notion of a distributional...
A Large Wiener Sausage from Crumbs. (2000)
Angel, Omer; Weizmann Institute Of Science; Omer@wisdom.weizmann.ac.il, Benjamini, Itai; Weizmann Institute Of Science; Itai@wisdom.weizmann.ac.il, Peres, Yuval; University Of California, Berkeley; Peres@stat.berkeley.edu
Let $B(t)$ denote Brownian motion in $R^d$. It is a classical fact that for any Borel set $A$ in $R^d$, the volume $V_1(A)$ of the Wiener sausage $B[0,1]+A$ has nonzero expectation iff $A$ is...
The Erwin, Schrodinger International Boltzmanngasse, Itai Benjamini, Itai Benjamini, Gideon Schechtman, Gideon Schechtman
Bounds on the range of random graph homomorphism into Z, and the maximal height dierence of the Gaussian random eld, are presented. 1 Introduction In this note we study the range of two related...
Random Graph Homomorphisms into Z (2000)
Itai Benjamini, Gideon Schechtman, Itai Benjamini
Gaussian Random Field and the Range of
Percolation in the Hyperbolic Plane (1999)
Benjamini, Itai, Schramm, Oded
This is a study of percolation in the hyperbolic plane and on regular tilings in the hyperbolic plane. The processes discussed include Bernoulli site and bond percolation on planar hyperbolic graphs,...
Critical Percolation on Any Nonamenable Group has no Infinite Clusters (1999)
Benjamini, Itai, Lyons, Russell, Peres, Yuval, Schramm, Oded
We show that independent percolation on any Cayley graph of a nonamenable group has no infinite components at the critical parameter. This result was obtained by the present authors earlier as a...
Benjamini, Itai, Häggström, Olle, Schramm, Oded
We show that adding epsilon-Bernoulli percolation to an everywhere percolating subgraph of Z^2 results in a graph which has large scale geometry similar to that of supercritical Bernoulli...
Percolation perturbations in potential theory and random walks (1999)
Itai Benjamini, Russell Lyons, Oded Schramm
Abstract. We show that on a Cayley graph of a nonamenable group, a.s. the infinite clusters of Bernoulli percolation are transient for simple random walk, that simple random walk on these clusters...
Critical percolation on any nonamenable group has no infinite clusters (1999)
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm, In Z
Abstract. We show that independent percolation on any Cayley graph of a nonamenable group has no infinite components at the critical parameter. This result was obtained in Benjamini, Lyons, Peres,...
Itai Benjamini, Gideon Schechtman
Bounds on the range of random graph homomorphism into Z, and the maximal height difference of the Gaussian random field, are presented. 1 Introduction In this note we study the range of two related...
Itai Benjamini, Olle Häggström, Oded Schramm
We show that adding -Bernoulli percolation to an everywhere percolating subgraph of Z 2 results in a graph which has large scale geometry similar to that of supercritical Bernoulli percolation, in...
Group-Invariant Percolation on Graphs (1999)
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm
. Let G be a closed group of automorphisms of a graph X . We relate geometric properties of G and X , such as amenability and unimodularity, to properties of G-invariant percolation processes on X ,...
Noise Sensitivity of Boolean Functions And Applications to Percolation (1999)
Itai Benjamini, Gil Kalai, Oded Schramm
It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the conguration with an arbitrary small percent of...
Itai Benjamini, Olle Häggström, Oded Schramm
We show that adding ffl-Bernoulli percolation to an everywhere percolating subgraph of Z 2 results in a graph which has large scale geometry similar to that of supercritical Bernoulli percolation, in...
Itai Benjamini, Gideon Schechtman
Abstract Bounds on the range of random graph homomorphism into Z, and the maximal height difference of the Gaussian random field, are presented.
Noise Sensitivity of Boolean Functions and Applications to Percolation (1998)
Benjamini, Itai, Kalai, Gil, Schramm, Oded
It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of...
Unpredictable paths and percolation (1998)
Benjamini, Itai, Pemantle, Robin, Peres, Yuval
4 We construct a nearest-neighbor process ${S_n}$ on Z that is less predictable than simple random walk, in the sense that given the process until time $n$, the conditional probability that $S_{n+k}...
Percolation Perturbations in Potential Theory and Random Walks (1998)
Benjamini, Itai, Lyons, Russell, Schramm, Oded
We show that on a Cayley graph of a nonamenable group, almost surely the infinite clusters of Bernoulli percolation are transient for simple random walk, that simple random walk on these clusters has...
Conformal invariance of Voronoi percolation (1998)
Abstract. It is proved that in the Voronoi model for percolation in dimension 2 and 3, the crossing probabilities are asymptotically invariant under conformal change of metric. To define Voronoi...
Noise Sensitivity of Boolean Functions And Applications to Percolation (1998)
Itai Benjamini, Gil Kalai, Oded Schramm
It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of...
Uniform Spanning Forests (1998)
Itai Benjamini, Russell Lyons, Yuval Peres, Oded Schramm
. We study uniform spanning forest measures on infinite graphs, which are weak limits of uniform spanning tree measures from finite subgraphs. These limits can be taken with free (FSF) or wired (WSF)...
On random graph homomorphisms into Z (1998)
Itai Benjamini, Olle Häggström, Elchanan Mossel
Given a bipartite connected finite graph G = (V; E) and a vertex v 0 2 V , we consider uniform probability measure on the set of graph homomorphisms f : V ! Z satisfying f(v 0 ) = 0. This measure can...
Paths with exponential intersection tails and oriented percolation (1997)
Benjamini, Itai, Pemantle, Robin, Peres, Yuval
We show that oriented percolation occurs whenever a condition is satisfied called "exponential intersection tails". This condition says that a measure on paths exists for which the probability of two...
Abstract. It is shown that every (infinite) graph with a positive Cheeger constant contains a tree with a positive Cheeger constant. Moreover, for every nonnegative integer k there is a unique...
Percolation Beyond Z^d, Many Questions And a Few Answers (1996)
Benjamini, Itai; Weizmann Institute Of Science; Itai@wisdom.weizmann.ac.il, Schramm, Oded; Microsoft Research; Schramm@microsoft.com
A comprehensive study of percolation in a more general context than the usual $Z^d$ setting is proposed, with particular focus on Cayley graphs, almost transitive graphs, and planar graphs. Results...
Random walks and harmonic functions on infinite planar graphs using square tilings (1996)
Benjamini, Itai, Schramm, Oded
We study a wide class of transient planar graphs, through a geometric model given by a square tiling of a cylinder. For many graphs, the geometric boundary of the tiling is a circle and is easy to...
Random walks and harmonic functions on infinite planar graphs using square tilings (1996)
Abstract. We study a wide class of transient planar graphs, through a geometric model given by a square tiling of a cylinder. For many graphs, the geometric boundary of the tiling is a circle, and is...
Percolation beyond Z d , many questions and a few answers (1996)
Abstract. A comprehensive study of percolation in a more general context than the usual Z d setting is proposed, with particular focus on Cayley graphs, almost transitive graphs, and planar graphs....
Percolation Beyond Z d, Many Questions and a Few Answers (1996)
Itai Benjamini, Oded Schramm, A Few Answers
A comprehensive study of percolation in a more general context than the usual ZZ d setting is proposed, with particular focus on Cayley graphs, almost transitive graphs, and planar graphs. Results...
Martin Capacity For Markov Chains (1995)
Itai Benjamini, Robin Pemantle, Yuval Peres
The probability that a transient Markov chain, or a Brownian path, will ever visit a given set , is classically estimated using the capacity of with respect to the Green kernel G(x; y). We show that...
North-Holland Examples of simply-connected Liouville manifolds with positive spectrum (1994)
Itai Benjamini, Jianguo Cao, Communicated M. Gromov
Abstract: For each n 2 3, we present a family of Riemannian metrics g on W ” such that each Riemannian manifold M ” = (IT’, g) has positive bottom of the spectrum of Laplacian A, (M”)> 0...
Martin Capacity For Markov Chains And Random Walks In Varying Dimensions (1993)
Itai Benjamini, Robin Pemantle, Yuval Peres
this paper is organized as follows. Martin capacity for Markov chains is the focus of Section 2. Several examples are given, including an interesting relation between simple random walk in three...
Spacings and pair correlations for finite Bernoulli convolutions (0000)
We consider finite Bernoulli convolutions with a parameter 1/2 < ? < 1 supported on a discrete point set, generically of size 2N. These sequences are uniformly distributed with respect to the...
Harmonic Functions On Planar And Almost Planar Graphs And Manifolds, Via Circle Packings
Via Circle Packings, Itai Benjamini, Oded Schramm
. The circle packing theorem is used to show that on any bounded valence transient planar graph there exists a non constant, harmonic, bounded, Dirichlet function. If P is a bounded circle packing in...
Exceptional Planes of Percolation
Consider the standard continuous percolation in R 4 , and choose the parameters so that the induced percolation on a fixed two dimensional linear subspace is critical. Although two dimensional...
Spacings and pair correlations for finite Bernoulli convolutions
We consider finite Bernoulli convolutions with a parameter 1/2 < ? < 1 supported on a discrete point set, generically of size 2N. These sequences are uniformly distributed with respect to the...