Perfect Matchings as IID Factors on Non-Amenable Groups (2009)
Lyons, Russell, Nazarov, Fedor
We prove that in every bipartite Cayley graph of every non-amenable group, there is a perfect matching that is obtained as a factor of independent uniform random variables. We also discuss expansion...
Poisson Splitting by Factors (2009)
Holroyd, Alexander E., Lyons, Russell, Soo, Terry
Given a homogeneous Poisson process on R^d with intensity L, we prove that it is possible to partition the points into two sets, as a deterministic function of the process, and in an...
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...
MINIMAL SPANNING FORESTS (2009)
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...
A transient Markov chain with finitely many cutpoints (2009)
Nicholas James, Russell Lyons, Yuval Peres
Dedicated to David Freedman with admiration Abstract: We give an example of a transient reversible Markov chain that almost surely has only a finite number of cutpoints. We explain how this is...
A love and respect of trees has been characteristic of mankind since the beginning of human evolution. Instinctively, we understood the importance of trees to our lives before we were able to ascribe...
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...
Random Complexes and l^2-Betti Numbers (2008)
Uniform spanning trees on finite graphs and their analogues on infinite graphs are a well-studied area. On a Cayley graph of a group, we show that they are related to the first $\ell^2$-Betti number...
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,...
Abstract. Determinantal point processes have arisen in diverse settings in recent years and have been investigated intensively. We study basic combinatorial and probabilistic aspects in the discrete...
Identities and Inequalities for Tree Entropy (2008)
Abstract. The notion of tree entropy was introduced by the author as a normalized limit of the number of spanning trees in finite graphs, but is defined on random infinite rooted graphs. We give some...
Identities and Inequalities for Tree Entropy (2007)
The notion of tree entropy was introduced by the author as a normalized limit of the number of spanning trees in finite graphs, but is defined on random infinite rooted graphs. We give some new...
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...
Potts Models, Olle Haggstrom Johan, Johan Jonasson, Russell Lyons
The random-cluster model is a dependent percolation model that has applications in the study of Ising and Potts models. In this paper, several new results for the random-cluster model with cluster...
Processes on Unimodular Random Networks (2007)
Aldous, David J.; University Of California, Berkeley; Aldous@stat.Berkeley.EDU, Lyons, Russell; Indiana University; Rdlyons@indiana.edu
We investigate unimodular random networks. Our motivations include their characterization via reversibility of an associated random walk and their similarities to unimodular quasi-transitive graphs....
Olle Haggstrom, Johan Jonasson, Russell Lyons
An explicit coupling construction of random-cluster measures is presented. As one of the applications of the construction, the Potts model on amenable Cayley graphs is shown to exhibit at every...
Olle Haggstrom, Johan Jonasson, Russell Lyons
isoperimetric constants and phase transitions in the
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...
A Measurable-Group-Theoretic Solution to von Neumann's Problem (2007)
Gaboriau, Damien, Lyons, Russell
We give a positive answer, in the measurable-group-theory context, to von Neumann's problem of knowing whether a non-amenable countable discrete group contains a non-cyclic free subgroup. We also get...
A Measurable-Group-Theoretic Solution to von Neumann's Problem (2007)
Gaboriau, Damien, Lyons, Russell
We give a positive answer, in the measurable-group-theory context, to von Neumann's problem of knowing whether a non-amenable countable discrete group contains a non-cyclic free subgroup. We also get...
Uniform non-amenability, cost, and the first l^2-Betti number (2007)
Lyons, Russell, Pichot, Mikaël, Vassout, Stéphane
It is shown that $2\beta_1(\G)\leq h(\G)$ for any countable group $\G$, where $\beta_1(\G)$ is the first $\ell^2$-Betti number and $h(\G)$ the uniform isoperimetric constant. In particular, a...
A transient Markov chain with finitely many cutpoints (2007)
James, Nicholas, Lyons, Russell, Peres, Yuval
We give an example of a transient reversible Markov chain that almost surely has only a finite number of cutpoints. We explain how this is relevant to a conjecture of Diaconis and Freedman and a...
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,...
Járai, Antal A., Lyons, Russell
We study Abelian sandpiles on graphs of the form $G \times I$, where $G$ is an arbitrary finite connected graph, and $I \subset \Z$ is a finite interval. We show that for any fixed $G$ with at least...
A Measurable-Group-Theoretic Solution to von Neumann's Problem (2007)
Gaboriau, Damien, Lyons, Russell
We give a positive answer, in the measurable-group-theory context, to von Neumann's problem of knowing whether a non-amenable countable discrete group contains a non-cyclic free subgroup. We also get...
A Measurable-Group-Theoretic Solution to von Neumann's Problem (2007)
Gaboriau, Damien, Lyons, Russell
We give a positive answer, in the measurable-group-theory context, to von Neumann's problem of knowing whether a non-amenable countable discrete group contains a non-cyclic free subgroup. We also get...
A Measurable-Group-Theoretic Solution to von Neumann's Problem (2007)
Gaboriau, Damien, Lyons, Russell
We give a positive answer, in the measurable-group-theory context, to von Neumann's problem of knowing whether a non-amenable countable discrete group contains a non-cyclic free subgroup. We also get...
A measurable-group-theoretic solution to von Neumann’s problem (2007)
Damien Gaboriau, Russell Lyons
We give a positive answer, in the measurable-group-theory context, to von Neumann’s problem of knowing whether a non-amenable countable discrete group contains a non-cyclic free subgroup. We also...
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.
Processes on Unimodular Random Networks (2006)
We investigate unimodular random networks. Our motivations include their characterization via reversibility of an associated random walk and their similarities to unimodular quasi-transitive graphs....
A Solidification Phenomenon in Random Packings (2005)
Bowen, Lewis, Lyons, Russell, Radin, Charles, Winkler, Peter
We prove that uniformly random packings of copies of a certain simply-connected figure in the plane exhibit global connectedness at all sufficiently high densities, but not at low densities.
Fluid/solid transition in a hard-core system (2005)
Bowen, Lewis, Lyons, Russell, Radin, Charles, Winkler, Peter
We prove that a system of particles in the plane, interacting only with a certain hard-core constraint, undergoes a fluid/solid phase transition.
Processes on unimodular random networks (2005)
Abstract. We investigate unimodular random networks. Our motivations include their characterization via reversibility of an associated random walk and their similarities to unimodular...
Asymptotic enumeration of spanning trees (2005)
Note: Theorem numbers differ from the published version. Abstract. We give new general formulas for the asymptotics of the number of spanning trees of a large graph. A special case answers a question...
Asymptotic Enumeration of Spanning Trees (2005)
We give new formulas for the asymptotics of the number of spanning trees of a large graph. A special case answers a question of McKay [Europ. J. Combin. 4 149–160] for regular graphs. The general...
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...
Conceptual Proofs of L log L Criteria (2004)
Lyons, Russell, Pemantle, Robin, Peres, Yuval
The Kesten-Stigum Theorem is a fundamental criterion for the rate of growth of a supercritical branching process, showing that an L log L condition is decisive. In critical and subcritical cases,...
Random Walk in a Random Environment and First-Passage Percolation on Trees (2004)
Pemantle, Robin, Lyons, Russell
We show that the transience or recurrence of a random walk in certain random environments on an arbitrary infinite locally finite tree is determined by the branching number of the tree, which is a...
Lyons, Russell, Steif, Jeffrey E.
We study a class of stationary processes indexed by ℤd that are defined via minors of d-dimensional (multilevel) Toeplitz matrices. We obtain necessary and sufficient conditions for phase...
High-Precision Entropy Values for Spanning Trees in Lattices (2003)
Felker, Jessica L., Lyons, Russell
Shrock and Wu have given numerical values for the exponential growth rate of the number of spanning trees in Euclidean lattices. We give a new technique for numerical evaluation that gives much more...
Random complexes and ℓ 2 -Betti numbers (2003)
Abstract. Uniform spanning trees on finite graphs and their analogues on infinite graphs are a well-studied area. On a Cayley graph of a group, we show that they are related to the first ℓ 2-Betti...
Asymptotic Enumeration of Spanning Trees (2002)
We give new general formulas for the asymptotics of the number of spanning trees of a large graph. A special case answers a question of McKay (1983) for regular graphs. The general answer involves a...
The first Szego limit theorem has been extended by Bump-Diaconis and Tracy-Widom to limits of other minors of Toeplitz matrices. We extend their results still further to allow more general measures...
Lyons, Russell, Steif, Jeffrey E.
We study a class of stationary processes indexed by $\Z^d$ that are defined via minors of $d$-dimensional (multilevel) Toeplitz matrices. We obtain necessary and sufficient conditions for phase...
Determinantal probability measures (2002)
Determinantal point processes have arisen in diverse settings in recent years and have been investigated intensively. We study basic combinatorial and probabilistic aspects in the discrete case. Our...
Coupling and Bernoullicity in random-cluster and Potts models (2002)
Häggström, Olle, Jonasson, Johan, Lyons, Russell
An explicit coupling construction of random-cluster measures is presented. As one of the applications of the construction, the Potts model on amenable Cayley graphs is shown to exhibit at every...
Explicit Isoperimetric Constants and Phase Transitions in the Random-Cluster Model (2002)
Häggström, Olle, Jonasson, Johan, Lyons, Russell
The random-cluster model is a dependent percolation model that has applications in the study of Ising and Potts models. In this paper, several new results are obtained for the random-cluster model on...
A computer proof of a series evaluation in terms of harmonic numbers (2002)
Russell Lyons, Peter Paule, Axel Riese
Abstract. A fruitful interaction between a new randomized WZ procedure and other computer algebra programs is illustrated by the computer proof of a series evaluation that originates from a denite...
A computer proof of a series evaluation in terms of harmonic numbers (2002)
Russell Lyons, Peter Paule, Axel Riese
Abstract. A fruitful interaction between a new randomized WZ procedure and other computer algebra programs is illustrated by the computer proof of a series evaluation that originates from a definite...
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...
Coupling and Bernoullicity in random-cluster and Potts models (2001)
Haggstrom, Olle, Jonasson, Johan, Lyons, Russell
An explicit coupling construction of random-cluster measures is presented. As one of the applications of the construction, the Potts model on amenable Cayley graphs is shown to exhibit at every...
Change Intolerance in Spanning Forests (2001)
Heicklen, Deborah, Lyons, Russell
Call a percolation process on edges of a graph change intolerant if the status of each edge is almost surely determined by the status of the other edges. We give necessary and sufficient conditions...
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...
Coupling and Bernoullicity in Random-cluster and Potts Models (2001)
Olle Häggström, Johan Jonasson, Russell Lyons
An explicit coupling construction of random-cluster measures is presented. As one of the applications of the construction, the Potts model on amenable Cayley graphs is shown to exhibit at every...
Explicit Isoperimetric Constants and Phase Transitions in the Random-Cluster Model (2001)
Olle Häggström, Johan Jonasson, Russell Lyons
The random-cluster model is a dependent percolation model that has applications in the study of Ising and Potts models. In this paper, several new results are obtained for the random-cluster model on...
Explicit isoperimetric constants and phase transitions in the random-cluster model (2000)
Haggstrom, Olle, Jonasson, Johan, Lyons, Russell
The random-cluster model is a dependent percolation model that has applications in the study of Ising and Potts models. In this paper, several new results are obtained for the random-cluster model on...
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...
Singularity of Some Random Continued Fractions (1999)
We prove singularity of some distributions of random continued fractions that correspond to iterated function systems with overlap and a parabolic point. These arose while studying the conductance of...
Phase Transitions on Nonamenable Graphs (1999)
We survey known results about phase transitions in various models of statistical physics when the underlying space is a nonamenable graph. Most attention is devoted to transitive graphs and trees.
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...
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,...
Ancona, Alano, Lyons, Russell, Peres, Yuval
Let ${X _n}$ be a transient reversible Markov chain and let $f$ be a function on the state space with finite Dirichlet energy. We prove crossing inequalities for the process ${f (X _n)}_{n\geq 1}$...
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,...
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 ,...
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...
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...
A Simple Path to Biggins' Martingale Convergence for Branching Random Walk (1998)
We give a simple non-analytic proof of Biggins' theorem on martingale convergence for branching random walks.
Normality of tree-growing search strategies (1998)
Lyons, Russell, Zumbrun, Kevin
We study the class of tree-growing search strategies introduced by Lent and Mahmoud, searches for which data are stored in a deterministic sequence of tree structures (e.g., linear search in forward...
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)...
The Best Bounds, Russell Lyons
We sharpen a bound in a theorem of Russell Lyons [4] for percolation on a tree and associated random walk. 1
Random walks on the lamplighter group (1996)
Lyons, Russell, Pemantle, Robin, Peres, Yuval
Kaimanovich and Vershik described certain finitely generated groups of exponential growth such that simple random walk on their Cayley graph escapes from the identity at a sublinear rate, or...
When Does a Branching Process Grow Like its Mean? Conceptual Proofs of L log L Criteria (1993)
Russell Lyons, Robin Pemantle, Yuval Peres
. The Kesten-Stigum Theorem is a fundamental criterion for the rate of growth of a supercritical branching process, showing that an L log L condition is decisive. In critical and subcritical cases,...
When Does a Branching Process Grow Like its Mean? Conceptual Proofs of L log L Criteria (1993)
Russell Lyons, Robin Pemantle, Yuval Peres
Abstract. The Kesten-Stigum Theorem is a fundamental criterion for the rate of growth of a supercritical branching process, showing that an L log L condition is decisive. In critical and subcritical...