Random Subnetworks of Random Sorting Networks (2009)
Angel, Omer, Holroyd, Alexander E.
A sorting network is a shortest path from 12...n to n...21 in the Cayley graph of S_n generated by nearest-neighbor swaps. For minfinity implied by the great circle conjecture Angel, Holroyd, Romik...
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...
Scaling limit of the invasion percolation cluster on a regular tree (2009)
Angel, Omer, Goodman, Jesse, Merle, Mathieu
We prove existence of the scaling limit of the invasion percolation cluster (IPC) on a regular tree. The limit is a random real tree with a single end. The contour and height functions of the limit...
Discrete low-discrepancy sequences (2009)
Angel, Omer, Holroyd, Alexander E., Martin, James B., Propp, James
Holroyd and Propp used Hall's marriage theorem to show that, given a probability distribution pi on a finite set S, there exists an infinite sequence s_1,s_2,... in S such that for all integers k >=...
Global divergence of spatial coalescents (2009)
Angel, Omer, Berestycki, Nathanael, Limic, Vlada
A class of processes called spatial \Lambda-coalescents was recently introduced by Limic and Sturm (2006). In these models particles perform independent random walks on some underlying graph G. In...
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...
Amenability of linear-activity automaton groups (2009)
Amir, Gideon, Angel, Omer, Virag, Balint
We prove that every linear-activity automaton group is amenable. The proof is based on showing that a sufficiently symmetric random walk on a specially constructed degree 1 automaton group -- 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...
The TASEP speed process (2008)
Amir, Gideon, Angel, Omer, Valko, Benedek
In a multi-type totally asymmetric simple exclusion process (TASEP) on the line, each site of Z is occupied by a particle labeled with a number and two neighboring particles are interchanged at rate...
Angel, Omer, Flaxman, Abraham D., Wilson, David B.
In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to...
The oriented swap process (2008)
Angel, Omer, Holroyd, Alexander, Romik, Dan
Particles labelled $1,...,n$ are arranged initially in increasing order. Subsequently, each pair of neighbouring particles that is currently in increasing order swaps according to a Poisson process...
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 Non-Backtracking Spectrum of the Universal Cover of a Graph (2007)
Angel, Omer, Friedman, Joel, Hoory, Shlomo
A non-backtracking walk on a graph, $H$, is a directed path of directed edges of $H$ such that no edge is the inverse of its preceding edge. Non-backtracking walks of a given length can be counted...
Card shuffling and diophantine approximation (2007)
Angel, Omer, Peres, Yuval, Wilson, David B.
The ``overlapping-cycles shuffle'' mixes a deck of $n$ cards by moving either the $n$th card or the $(n-k)$th card to the top of the deck, with probability half each. We determine the spectral gap...
Random Sorting Networks (2006)
Angel, Omer, Holroyd, Alexander E., Romik, Dan, Virag, Balint
A sorting network is a shortest path from 12...n to n...21 in the Cayley graph of S_n generated by nearest-neighbour swaps. We prove that for a uniform random sorting network, as n->infinity 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...
Invasion percolation on regular trees (2006)
Angel, Omer, Goodman, Jesse, Hollander, Frank Den, Slade, Gordon
We consider invasion percolation on a rooted regular tree. For the infinite cluster invaded from the root, we identify the scaling behavior of its $r$-point function for any $r\geq2$ and of its...
The Jammed Phase of the Biham-Middleton-Levine Traffic Model (2005)
Angel, Omer; University Of British Columbia, Canada; Angel@math.ubc.ca, Holroyd, Alexander E.; University Of British Columbia, Canada; Holroyd@math.ubc.ca, Martin, James B.; CNRS And Université Paris 7, France; James.Martin@liafa.jussieu.fr
Initially a car is placed with probability $p$ at each site of the two-dimensional integer lattice. Each car is equally likely to be East-facing or North-facing, and different sites receive...
The Jammed Phase of the Biham-Middleton-Levine Traffic Model (2005)
Angel, Omer, Holroyd, Alexander E, Martin, James B
Initially a car is placed with probability p at each site of the two-dimensional integer lattice. Each car is equally likely to be East-facing or North-facing, and different sites receive independent...
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...
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...
The Stationary Measure of a 2-type Totally Asymmetric Exclusion Process (2004)
We give a combinatorial description of the stationary measure for a totally asymmetric exclusion process (TASEP) with second class particles, on either Z or on the cycle Z_N. The measure is the image...
Scaling of Percolation on Infinite Planar Maps, I (2004)
We consider several aspects of the scaling limit of percolation on random planar triangulations, both finite and infinite. The equivalents for random maps of Cardy's formula for the limit under...
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...
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...
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...
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...
Growth and Percolation on the Uniform Infinite Planar Triangulation (2002)
A construction as a growth process for sampling of the uniform infinite planar triangulation (UIPT), defined in a previous paper, is given. The construction is algorithmic in nature, and is an...
Uniform Infinite Planar Triangulations (2002)
The existence of the weak limit as n --> infinity of the uniform measure on rooted triangulations of the sphere with n vertices is proved. Some properties of the limit are studied. In particular, the...
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...
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...
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...