Random-turn Hex and other selection games (2009)
Yuval Peres, Oded Schramm, Scott Sheffield, David B. Wilson
Overview. The game of Hex, invented independently by Piet Hein in 1942 and John Nash in 1948 [9], has two players who take turns placing stones of their respective colors on the hexagons of 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...
The scaling limit of the Minimal Spanning Tree - a preliminary report (2009)
Garban, Christophe, Pete, Gábor, Schramm, Oded
This is a short (and somewhat informal) contribution to the proceedings of the XVIth International Congress on Mathematical Physics, Prague, 2009, written up by the second author. We describe how the...
Russell Lyons, Ron Peled, Oded Schramm
The number of spanning trees in the giant component of the random graph G(n, c/n) (c>1) grows like exp{m(f(c)+o(1))} as n →∞,wherem is the number of vertices in the giant component. The...
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...
Conformal radii for conformal loop ensembles (2009)
Oded Schramm, Scott Sheffield, David B. Wilson
The conformal loop ensembles CLEκ, defined for 8/3 ≤ κ ≤ 8, are random collections of loops in a planar domain which are conjectured scaling limits of the O(n) loop models. We calculate the...
Markov chain intersections and the loop-erased walk (2008)
Russell Lyons, Yuval Peres, Oded Schramm
Abstract. Let X and Y be independent transient Markov chains on the same state space that have the same transition probabilities. Let L denote the “loop-erased path ” obtained from the path of X...
Continuity of the SLE trace in simply connected domains (2008)
Garban, Christophe, Rohde, Steffen, Schramm, Oded
We prove that the $SLE_\kappa$ trace in any simply connected domain $G$ is continuous (except possibly near its endpoints) if $\kappa
Ends in Uniform Spanning Forests (2008)
Lyons, Russell; Indiana University; Rdlyons@indiana.edu, Morris, Benjamin J.; U. Calif., Davis; Morris@math.ucdavis.edu, Schramm, Oded; Microsoft Research; Schramm@microsfot.com
It has hitherto been known that in a transitive unimodular graph, each tree in the wired spanning forest has only one end a.s. We dispense with the assumptions of transitivity and unimodularity,...
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...
The Fourier Spectrum of Critical Percolation (2008)
Garban, Christophe, Pete, Gabor, Schramm, Oded
Consider the indicator function $f$ of a two-dimensional percolation crossing event. In this paper, the Fourier transform of $f$ is studied and sharp bounds are obtained for its lower tail in several...
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...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2008)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
TUG-OF-WAR AND THE INFINITY LAPLACIAN (2008)
Yuval Peres, Oded Schramm, Scott Sheffield, B. Wilson
1.1. Overview. We consider a class of zero-sum two-player stochastic games called tug-of-war and use them to prove that every bounded real-valued Lipschitz function F on a subset Y of a length space...
Holroyd, Alexander E., Pemantle, Robin, Peres, Yuval, Schramm, Oded
Suppose that red and blue points occur as independent homogeneous Poisson processes in R^d. We investigate translation-invariant schemes for perfectly matching the red points to the blue points. For...
Hyperfinite graph limits (2007)
G\'abor Elek introduced the notion of a hyperfinite graph family: a collection of graphs is hypefinite if for every $\epsilon>0$ there is some finite $k$ such that each graph $G$ in the collection...
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...
Boundary proximity of SLE (2007)
This paper examines how close the chordal $\SLE_\kappa$ curve gets to the real line asymptotically far away from its starting point. In particular, when $\kappa\in(0,4)$, it is shown that if...
Growth of the Number of Spanning Trees of the Erd\"os-R\'enyi Giant Component (2007)
Lyons, Russell, Peled, Ron, Schramm, Oded
The number of spanning trees in the giant component of the random graph $\G(n, c/n)$ ($c>1$) grows like $\exp\big\{m\big(f(c)+o(1)\big)\big\}$ as $n\to\infty$, where $m$ is the number of vertices in...
Combinatorically Prescribed Packings and Applications to Conformal and Quasiconformal Maps (2007)
The Andreev-Thurston Circle Packing Theorem is generalized to packings of convex bodies in planar simply connected domains. This turns out to be a useful tool for constructing conformal and...
Combinatorically Prescribed Packings and Applications to Conformal and Quasiconformal Maps (2007)
The Andreev-Thurston Circle Packing Theorem is generalized to packings of convex bodies in planar simply connected domains. This turns out to be a useful tool for constructing conformal and...
Dynamical sensitivity of the infinite cluster in critical percolation (2007)
Peres, Yuval, Schramm, Oded, Steif, Jeffrey E.
In dynamical percolation, the status of every bond is refreshed according to an independent Poisson clock. For graphs which do not percolate at criticality, the dynamical sensitivity of this property...
Ends in Uniform Spanning Forests (2007)
Lyons, Russell, Morris, Benjamin J., Schramm, Oded
It has hitherto been known that in a transitive unimodular graph, each tree in the wired spanning forest has only one end a.s. We dispense with the assumptions of transitivity and unimodularity,...
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...
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...
Conformal radii for conformal loop ensembles (2006)
Schramm, Oded, Sheffield, Scott, Wilson, David B.
The conformal loop ensembles CLE(k), defined for k in [8/3, 8], are random collections of loops in a planar domain which are conjectured scaling limits of the O(n) loop models. We calculate the...
Minimal spanning forests (2006)
Minimal spanning forests on infinite graphs are weak limits of minimal spanning trees from finite subgraphs. These limits can be taken with free or wired boundary conditions and are denoted FMSF...
Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces (2006)
Naor, Assaf, Peres, Yuval, Schramm, Oded, Sheffield, Scott
A metric space $X$ has Markov-type $2$ if for any reversible finite-state Markov chain $\{Z_t\}$ (with $Z_0$ chosen according to the stationary distribution) and any map $f$ from the state space to...
Contour lines of the two-dimensional discrete Gaussian free field (2006)
Schramm, Oded, Sheffield, Scott
We prove that the chordal contour lines of the discrete Gaussian free field converge to forms of SLE(4). Specifically, there is a constant lambda > 0 such that when h is an interpolation of the...
Tug-of-war and the infinity Laplacian (2006)
Peres, Yuval, Schramm, Oded, Sheffield, Scott, Wilson, David B.
We prove that every bounded Lipschitz function F on a subset Y of a length space X admits a tautest extension to X, i.e., a unique Lipschitz extension u for which Lip_U u = Lip_{boundary of U} u for...
Conformally invariant scaling limits (an overview and a collection of problems) (2006)
Many mathematical models of statistical physics in two dimensions are either known or conjectured to exhibit conformal invariance. Over the years, physicists proposed predictions of various exponents...
Abstract. The purpose of this note is to describe a framework which unifies radial, chordal and dipolar SLE. When the definition of SLE(κ; ρ) is extended to the setting where the force points can...
Harmonic explorer and its convergence to SLE4 (2005)
Schramm, Oded, Sheffield, Scott
The harmonic explorer is a random grid path. Very roughly, at each step the harmonic explorer takes a turn to the right with probability equal to the discrete harmonic measure of the left-hand side...
Random-Turn Hex and other selection games (2005)
Peres, Yuval, Schramm, Oded, Sheffield, Scott, Wilson, David B.
The game of Hex has two players who take turns placing stones of their respective colors on the hexagons of a rhombus-shaped hexagonal grid. Black wins by completing a crossing between two opposite...
Every decision tree has an influential variable (2005)
O'Donnell, Ryan, Saks, Michael, Schramm, Oded, Servedio, Rocco A.
We prove that for any decision tree calculating a boolean function $f:\{-1,1\}^n\to\{-1,1\}$, \[ \Var[f] \le \sum_{i=1}^n \delta_i \Inf_i(f), \] where $\delta_i$ is the probability that the $i$th...
Schramm, Oded, Wilson, David B.
The purpose of this note is to describe a framework which unifies radial, chordal and dipolar SLE. When the definition of SLE(kappa;rho) is extended to the setting where the force points can be in...
Quantitative noise sensitivity and exceptional times for percolation (2005)
Schramm, Oded, Steif, Jeffrey E.
One goal of this paper is to prove that dynamical critical site percolation on the planar triangular lattice has exceptional times at which percolation occurs. In doing so, new quantitative noise...
Basic properties of SLE (2005)
\SLEk/ is a random growth process based on Loewner's equation with driving parameter a one-dimensional Brownian motion running with speed $\kappa$. This process is intimately connected with scaling...
Basic properties of SLE (2005)
SLE¿È is a random growth process based on Loewner¿fs equation with driving parameter a one-dimensional Brownian motion running with speed ¿È. This process is intimately connected with scaling...
Thoughts on noise and quantum computing (2005)
Gil Kalai, Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2005)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
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...
Minimal spanning forests (2004)
Lyons, Russell, Peres, Yuval, Schramm, Oded
Minimal spanning forests on infinite graphs are weak limits of minimal spanning trees from finite subgraphs. These limits can be taken with free or wired boundary conditions and are denoted FMSF...
Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces (2004)
Naor, Assaf, Peres, Yuval, Schramm, Oded, Sheffield, Scott
A metric space $X$ has {\em Markov type} 2, if for any reversible finite-state Markov chain $\{Z_t\}$ (with $Z_0$ chosen according to the stationary distribution) and any map $f$ from the state space...
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...
Compositions of random transpositions (2004)
Let $Y=(y_1,y_2,...)$, $y_1\ge y_2\ge...$, be the list of sizes of the cycles in the composition of $c n$ transpositions on the set $\{1,2,...,n\}$. We prove that if $c>1/2$ is constant and...
Conformal invariance of planar loop-erased random walks and uniform spanning trees (2004)
Lawler, Gregory F., Schramm, Oded, Werner, Wendelin
This paper proves that the scaling limit of a loop-erased random walk in a simply connected domain $Dsubsetneqq\C$ is equal to the radial SLE$_2$ path. In particular, the limit exists and is...
The harmonic explorer and its convergence to SLE(4) (2003)
Schramm, Oded, Sheffield, Scott
The harmonic explorer is a random grid path. Very roughly, at each step the harmonic explorer takes a turn to the right with probability equal to the discrete harmonic measure of the left-hand side...
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...
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...
Conformal restriction: the chordal case (2002)
Lawler, Gregory, Schramm, Oded, Werner, Wendelin
We characterize and describe all random subsets $K$ of a given simply connected planar domain (the upper half-plane $\H$, say) which satisfy the ``conformal restriction'' property, i.e., $K$ connects...
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...
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...
On the scaling limit of planar self-avoiding walk (2002)
Lawler, Gregory F., Schramm, Oded, Werner, Wendelin
A planar self-avoiding walk (SAW) is a nearest neighbor random walk path in the square lattice with no self-intersection. A planar self-avoiding polygon (SAP) is a loop with no self-intersection. In...
First Passage Percolation Has Sublinear Distance Variance (2002)
Benjamini, Itai, Kalai, Gil, Schramm, Oded
Let $0
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...
Conformal invariance of planar loop-erased random walks and uniform spanning trees (2001)
Lawler, Gregory F., Schramm, Oded, Werner, Wendelin
We prove that the scaling limit of loop-erased random walk in a simply connected domain $D$ is equal to the radial SLE(2) path in $D$. In particular, the limit exists and is conformally invariant. It...
One-Arm Exponent for Critical 2D Percolation (2001)
Lawler, Gregory F.; Duke University And Cornell University; Lawler@math.cornell.edu, Schramm, Oded; Microsoft Research; Schramm@microsoft.com, Werner, Wendelin; Université Paris-Sud And IUF; Werner@math.u-psud.fr
The probability that the cluster of the origin in critical site percolation on the triangular grid has diameter larger than R is proved to decay like R to the power 5/48 as R goes to infinity.
One-Arm Exponent for Critical 2D Percolation (2001)
Lawler, Gregory F.; Duke University And Cornell University; Lawler@math.cornell.edu, Schramm, Oded; Microsoft Research; Schramm@microsoft.com, Werner, Wendelin; Université Paris-Sud And IUF; Werner@math.u-psud.fr
The probability that the cluster of the origin in critical site percolation on the triangular grid has diameter larger than R is proved to decay like R to the power 5/48 as R goes to infinity.
Schramm, Oded; Microsoft Research; Schramm@microsoft.com
Let A be an arc on the boundary of the unit disk U. We prove an asymptotic formula for the probability that there is a percolation cluster K for critical site percolation on the triangular grid in U...
Schramm, Oded; Microsoft Research; Schramm@microsoft.com
Let A be an arc on the boundary of the unit disk U. We prove an asymptotic formula for the probability that there is a percolation cluster K for critical site percolation on the triangular grid in U...
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...
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...
One-arm exponent for critical 2D percolation (2001)
Lawler, Gregory F., Schramm, Oded, Werner, Wendelin
The probability that the cluster of the origin in critical site percolation on the triangular grid has diameter larger than $R$ is proved to decay like $R^{-5/48}$ as $R\to\infty$.
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
Let $A$ be an arc on the boundary of the unit disk $U$. We prove an asymptotic formula for the probability that there is a percolation cluster $K$ for critical site percolation on the triangular grid...
Markov Chain Intersections and the Loop-Erased Walk (2001)
Lyons, Russell, Peres, Yuval, Schramm, Oded
Let X and Y be independent transient Markov chains on the same state space that have the same transition probabilities. Let L denote the ``loop-erased path'' obtained from the path of X by erasing...
Basic properties of SLE (2001)
SLE is a random growth process based on Loewner's equation with driving parameter a one-dimensional Brownian motion running with speed $\kappa$. This process is intimately connected with scaling...
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 )...
Sharp estimates for Brownian non-intersection probabilities (2001)
Lawler, Greg, Schramm, Oded, Werner, Wendelin
This paper gives an accessible (but still technical) self-contained proof to the fact that the intersection probabilities for planar Brownian motion are given in terms of the intersection exponents,...
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...
The dimension of the planar Brownian frontier is 4=3 (2001)
Gregory F. Lawler, Oded Schramm, Wendelin Werner
The purpose of this note is to announce and sketch the proofs of results determining the Hausdorff dimension of certain subsets of planar Brownian paths. Proofs are currently written down in a...
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...
The Dimension of the Planar Brownian Frontier is 4/3 (2000)
Lawler, Gregory F., Schramm, Oded, Werner, Wendelin
In a series of recent preprints, we have proven that with probability one the Hausdorff dimension on the outer boundary of planar Brownian motion is 4/3, confirming a conjecture by Mandelbrot. It is...
Values of Brownian intersection exponents III: Two-sided exponents (2000)
Lawler, Gregory F., Schramm, Oded, Werner, Wendelin
This paper determines values of intersection exponents between packs of planar Brownian motions in the half-plane and in the plane that were not derived in our first two papers. For instance, it is...
Analyticity of intersection exponents for planar Brownian motion (2000)
Lawler, Gregory F., Schramm, Oded, Werner, Wendelin
We show that the intersection exponents for planar Brownian motions are analytic. More precisely, let $B$ and $B'$ be independent planar Brownian motions started from distinct points, and define the...
On the Cover Time of Planar Graphs (2000)
Jonasson, Johan; Chalmers University Of Technology; Jonasson@math.chalmers.se, Schramm, Oded; Microsoft Research; Schramm@microsoft.com
The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all the vertices. It is known that the cover time on any n-vertex,...
On the Cover Time of Planar Graphs (2000)
Jonasson, Johan; Chalmers University Of Technology; Jonasson@math.chalmers.se, Schramm, Oded; Microsoft Research; Schramm@microsoft.com
The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all the vertices. It is known that the cover time on any n-vertex,...
Values of Brownian intersection exponents II: Plane exponents (2000)
Lawler, Gregory F., Schramm, Oded, Werner, Wendelin
We derive the exact value of intersection exponents between planar Brownian motions or random walks, confirming predictions from theoretical physics by Duplantier and Kwon. Let B and B' be...
On the cover time of planar graphs (2000)
Jonasson, Johan, Schramm, Oded
The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all the vertices. It is known that the cover time on any n-vertex,...
On the Cover Time of Planar Graphs (2000)
The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all the vertices. It is known that the cover time on any n-vertex,...
COMMUNICATIONS in PROBABILITY ON THE COVER TIME OF PLANAR GRAPHS (2000)
effective resistance, commute time, hitting time, difference time, circle packing, triangulation The cover time of a finite connected graph is the expected number of steps needed for a simple random...
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,...
Values of Brownian intersection exponents I: Half-plane exponents (1999)
Lawler, Gregory F., Schramm, Oded, Werner, Wendelin
This paper proves conjectures originating in the physics literature regarding the intersection exponents of Brownian motion in a half-plane. For instance, suppose that B and B' are two independent...
Indistinguishability of Percolation Clusters (1999)
We show that when percolation produces infinitely many infinite clusters on a Cayley graph, one cannot distinguish the clusters from each other by any invariantly defined property. This implies that...
Trees, Not Cubes: Hypercontractivity, Cosiness, and Noise Stability (1999)
Schramm, Oded; Microsoft Research; Schramm@microsoft.com, Tsirelson, Boris; Tel Aviv University; Tsirel@math.tau.ac.il
Noise sensitivity of functions on the leaves of a binary tree is studied, and a hypercontractive inequality is obtained. We deduce that the spider walk is not noise stable.
Trees, Not Cubes: Hypercontractivity, Cosiness, and Noise Stability (1999)
Schramm, Oded; Microsoft Research; Schramm@microsoft.com, Tsirelson, Boris; Tel Aviv University; Tsirel@math.tau.ac.il
Noise sensitivity of functions on the leaves of a binary tree is studied, and a hypercontractive inequality is obtained. We deduce that the spider walk is not noise stable.
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...
Stationary Measures for Random Walks in a Random Environment with Random Scenery (1999)
Let $\Gamma$ act on a countable set V with only finitely many orbits. Given a $\Gamma$-invariant random environment for a Markov chain on V and a random scenery, we exhibit, under certain conditions,...
Scaling limits of loop-erased random walks and uniform spanning trees (1999)
The uniform spanning tree (UST) and the loop-erased random walk (LERW) are related probabilistic processes. We consider the limits of these models on a fine grid in the plane, as the mesh goes to...
Trees, not cubes: hypercontractivity, cosiness, and noise stability (1999)
Schramm, Oded, Tsirelson, Boris
Noise sensitivity of functions on the leaves of a binary tree is studied, and a hypercontractive inequality is obtained. We deduce that the spider walk is not noise stable.
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,...
Stationary Measures for Random Walks in a Random Environment with Random Scenery (1999)
. Let \Gamma act on a countable set V with only finitely many orbits. Given a \Gamma-invariant random environment for a Markov chain on V and a random scenery, we exhibit, under certain conditions,...
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...
Indistinguishability of Percolation Clusters (1999)
We show that when percolation produces infinitely many infinite clusters on a Cayley graph, one cannot distinguish the clusters from each other by any invariantly defined property. This implies that...
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...
Trees, Not Cubes: Hypercontractivity, Cosiness, and Noise Stability (1999)
Noise sensitivity of functions on the leaves of a binary tree is studied, and a hypercontractive inequality is obtained. We deduce that the spider walk is not noise stable. Introduction For the...
Scaling Limits of Loop-Erased Random Walks and Uniform Spanning Trees (1999)
. The uniform spanning tree (UST) and the loop-erased random walk (LERW) are strongly related probabilistic processes. We consider the limits of these models on a fine grid in the plane, as the mesh...
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...
Stationary measures for random walks in a random environment with random scenery (1999)
Abstract. Let Γ act on a countable set V with only finitely many orbits. Given a Γ-invariant random environment for a Markov chain on V and a random scenery, we exhibit, under certain conditions,...
Stationary measures for random walks in a random environment with random scenery (1999)
Abstract. Let; act on a countable set V with only nitely many orbits. Given a;-invariant random environment for a Markov chain on V and a random scenery, we exhibit, under certain conditions, an...
Indistinguishability of Percolation Clusters (1998)
We show that when percolation produces infinitely many infinite clusters on a Cayley graph, one cannot distinguish the clusters from each other by any invariantly defined property. This implies that...
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...
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...
for the inattention is that while Koebe, and consequently most readers of his papers, was a mathematical analyst, the theorem is of a combinatorial geometric nature. Around 1980, W. Thurston...
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...
Convergence Of Hexagonal Disk Packings To The Riemann Map (1998)
. Let\Omega $ C be a simply connected domain. The Rodin-Sullivan Theorem states that a sequence of disk packings in the unit disk U converges, in a well defined sense, to a conformal map from\Omega...
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)...
Convergence Of Hexagonal Disk Packings To The Riemann Map (1998)
. Let\Omega $ C be a simply connected domain. The Rodin-Sullivan Theorem states that a sequence of disk packings in the unit disk U converges, in a well defined sense, to a conformal map from\Omega...
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...
On The Distortion Of Relative Circle Domain Isomorphisms (1997)
. Several qualitative properties of the conformal homeomorphisms between relative circle domains are proved. In particular, counterexamples are presented to the analog of Koebe's 1=4 Theorem for...
Circle Patterns With The Combinatorics Of The Square Grid (1997)
. Explicit families of entire circle patterns with the combinatorics of the square grid are constructed, and it is shown that the collection of entire, locally univalent circle patterns on the sphere...
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...
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....
On The Convergence Of Circle Packings To The Riemann Map (1996)
. Rodin and Sullivan (1987) proved Thurston's conjecture that a scheme based on the Circle Packing Theorem converges to the Riemann mapping, thereby providing a refreshing geometric view of...
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...
Transboundary extremal length (1995)
Abstract. We introduce two basic notions, `transboundary extremal length ' and `fat sets', and apply these concepts to the theory of conformal uniformization of multiply connected planar...
Average kissing numbers for non-congruent sphere packings (1994)
Kuperberg, Greg, Schramm, Oded
The Koebe circle packing theorem states that every finite planar graph can be realized as the nerve of a packing of (non-congruent) circles in R^3. We investigate the average kissing number of finite...
Hyperbolic And Parabolic Packings (1994)
. The contacts graph, or nerve, of a packing, is a combinatorial graph that describes the combinatorics of the packing. Let G be the 1-skeleton of a triangulation of an open disk. G is said to be CP...
Average Kissing Numbers for Non-Congruent Sphere Packings (1994)
Introduction Let P be a packing of n (round) balls in R 3 . (A packing of round balls, also known as a sphere packing, is a collection of round balls with disjoint interiors.) The balls may have...
Embeddings Of Gromov Hyperbolic Spaces
. It is shown that a Gromov hyperbolic geodesic metric space X with bounded growth at some scale is roughly quasi-isometric to a convex subset of hyperbolic space. If one is allowed to rescale 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...
Conformal Uniformization And Packings
. A new short proof is given for Brandt and Harrington's theorem about conformal uniformizations of planar finitely connected domains as domains with boundary components of specified shapes....
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...