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...
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 >=...
Geometric Properties of Poisson Matchings (2009)
Suppose that red and blue points occur as independent Poisson processes of equal intensity in R^d, and that the red points are matched to the blue points via straight edges in a translation-invariant...
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...
Rotor Walks and Markov Chains (2009)
Holroyd, Alexander E., Propp, James
The rotor walk is a derandomized version of the random walk on a graph. On successive visits to any given vertex, the walker is routed to each of the neighboring vertices in some fixed cyclic order,...
Local Bootstrap Percolation (2009)
Gravner, Janko; University Of California Davis; Gravner@math.ucdavis.edu, Holroyd, Alexander E.; University Of British Columbia, Microsoft Research; Holroyd@math.ubc.ca
We study a variant of bootstrap percolation in which growth is restricted to a single active cluster. Initially there is a single active site at the origin, while other sites of Z^2 are independently...
Local Bootstrap Percolation (2008)
Gravner, Janko, Holroyd, Alexander E.
We study a variant of bootstrap percolation in which growth is restricted to a single active cluster. Initially there is a single active site at the origin, while other sites of Z^2 are independently...
doi:10.1112/plms/pdl018 UNIVERSAL FINITARY CODES WITH EXPONENTIAL TAILS (2008)
Nate Harvey, Alexander E. Holroyd, Yuval Peres, Dan Romik
In 1977, Keane and Smorodinsky showed that there exists a finitary homomorphism from any finite-alphabet Bernoulli process to any other finite-alphabet Bernoulli process of strictly lower entropy. In...
Chip-Firing and Rotor-Routing on Directed Graphs (2008)
Holroyd, Alexander E., Levine, Lionel, Meszaros, Karola, Peres, Yuval, Propp, James, Wilson, David B.
We give a rigorous and self-contained survey of the abelian sandpile model and rotor-router model on finite directed graphs, highlighting the connections between them. We present several intriguing...
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...
Entanglement and Rigidity in Percolation Models (2007)
We review recent progress and open problems in entanglement and rigidity percolation. 1
Partition Identities and the Coin Exchange Problem (2007)
The number of partitions of n into parts divisible by a or b equals the number of partitions of n in which each part and each difference of two parts is expressible as a non-negative integer...
Slow Convergence in Bootstrap Percolation (2007)
Gravner, Janko, Holroyd, Alexander E.
In the bootstrap percolation model, sites in an L by L square are initially infected independently with probability p. At subsequent steps, a healthy site becomes infected if it has at least 2...
Universal finitary codes with exponential tails (2007)
Harvey, Nate, Holroyd, Alexander E., Peres, Yuval, Romik, Dan
In 1977, Keane and Smorodinsky showed that there exists a finitary homomorphism from any finite-alphabet Bernoulli process to any other finite-alphabet Bernoulli process of strictly lower entropy. In...
A Non-Measurable Set From Coin-Flips (2006)
Holroyd, Alexander E., Soo, Terry
In this expository note, we construct a non-measurable set in the probability space of coin flips indexed by the integers.
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...
A Percolating Hard Sphere Model (2006)
Cotar, Codina, Holroyd, Alexander E., Revelle, David
Given a homogeneous Poisson point process in R^d, Haggstrom and Meester asked whether it is possible to place spheres (of differing radii) centred at the points, in a translation-invariant way, so...
A stable marriage of Poisson and Lebesgue (2006)
Hoffman, Christopher, Holroyd, Alexander E., Peres, Yuval
Let Ξ be a discrete set in ℝd. Call the elements of Ξ centers. The well-known Voronoi tessellation partitions ℝd into polyhedral regions (of varying sizes) by allocating each site of ℝd to...
The Metastability Threshold for Modified Bootstrap Percolation in d Dimensions (2006)
Holroyd, Alexander E; Department Of Mathematics, University Of British Columbia; Holroyd@math.ubc.ca
In the modified bootstrap percolation model, sites in the cube {1,...,L}d are initially declared active independently with probability p. At subsequent steps, an inactive site becomes active if it...
The Metastability Threshold for Modified Bootstrap Percolation in d Dimensions (2006)
In the modified bootstrap percolation model, sites in the cube {1,...,L}^d are initially declared active independently with probability p. At subsequent steps, an inactive site becomes active if it...
Universal finitary codes with exponential tails (2006)
Harvey, Nate, Holroyd, Alexander E., Peres, Yuval, Romik, Dan
In 1977, Keane and Smorodinsky showed that there exists a finitary homomorphism from any finite-alphabet Bernoulli process to any other finite-alphabet Bernoulli process of strictly lower entropy. In...
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...
Tail Bounds for the Stable Marriage of Poisson and Lebesgue (2005)
Hoffman, Christopher, Holroyd, Alexander E., Peres, Yuval
Let \Xi be a discrete set in R^d. Call the elements of \Xi centers. The well-known Voronoi tessellation partitions R^d into polyhedral regions (of varying volumes) by allocating each site of R^d to...
A stable marriage of Poisson and Lebesgue (2005)
Hoffman, Christopher, Holroyd, Alexander E., Peres, Yuval
Let $\Xi$ be a discrete set in ${\mathbb{R}}^d$. Call the elements of $\Xi$ centers. The well-known Voronoi tessellation partitions ${\mathbb{R}}^d$ into polyhedral regions (of varying sizes) by...
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...
Universal finitary codes with exponential tails (2005)
Harvey, Nate, Holroyd, Alexander E., Peres, Yuval, Romik, Dan
In 1977, Keane and Smorodinsky showed that there exists a finitary homomorphism from any finite-alphabet Bernoulli process to any other finite-alphabet Bernoulli process of strictly lower entropy. In...
Extra heads and invariant allocations (2005)
Holroyd, Alexander E., Peres, Yuval
Let Π be an ergodic simple point process on ℝd and let Π* be its Palm version. Thorisson [Ann. Probab. 24 (1996) 2057–2064] proved that there exists a shift coupling of Π and Π*; that is, one...
Extra heads and invariant allocations (2003)
Holroyd, Alexander E., Peres, Yuval
Let \Pi be an ergodic simple point process on R^d and let \Pi^* be its Palm version. Thorisson [Ann. Probab. 24 (1996) 2057-2064] proved that there exists a shift coupling of \Pi and \Pi^*; that is,...
Trees and Matchings from Point Processes (2003)
Holroyd, Alexander E.; University Of California, Berkeley; Holroyd@math.berkeley.edu, Peres, Yuval; University Of California, Berkeley; Peres@stat.berkeley.edu
A factor graph of a point process is a graph whose vertices are the points of the process, and which is constructed from the process in a deterministic isometry-invariant way. We prove that the...
Integrals, Partitions, and Cellular Automata (2003)
Holroyd, Alexander E., Liggett, Thomas M., Romik, Dan
We prove that $$\int_0^1\frac{-\log f(x)}xdx=\frac{\pi^2}{3ab}$$ where $f(x)$ is the decreasing function that satisfies $f^a-f^b=x^a-x^b$, for $0
Integrals, Partitions, and Cellular Automata (2003)
Alexander E. Holroyd, Thomas M. Liggett, Dan Romik
We prove that x where f(x) is the decreasing function that satisfies f for 0 < a < b. When a is an integer and b = a + 1 we deduce several combinatorial results. These include an asymptotic...
forest A factor graph of a point process is a graph whose vertices are the points of the process, and which is constructed from the process in a deterministic isometry-invariant way. We prove that...
Trees and matchings from point processes (2002)
Holroyd, Alexander E., Peres, Yuval
A factor graph of a point process is a graph whose vertices are the points of the process, and which is constructed from the process in a deterministic isometry-invariant way. We prove that the...
Sharp Metastability Threshold for Two-Dimensional Bootstrap Percolation (2002)
In the bootstrap percolation model, sites in an $L$ by $L$ square are initially independently declared active with probability $p$. At each time step, an inactive site becomes active if at least two...
Rigidity Percolation and Boundary Conditions (2001)
We study the effects of boundary conditions in two-dimensional rigidity percolation. Specifically, we consider generic rigidity in the bond percolation model on the triangular lattice. We introduce a...
How to Find an extra Head: Optimal Random Shifts of Bernoulli and Poisson Random Fields (2001)
Holroyd, Alexander E., Liggett, Thomas M.
We consider the following problem:given an i.i.d. family of Bernoulli random variables indexed by $\mathbb{Z}^d$, find a random occupied site $X \in \mathbb{Z}^d$ such that relative to $X$, the other...
Entanglement in Percolation (1999)
Georey R. Grimmett, Alexander E. Holroyd, Geo#rey R. Grimmett, Er E. Holroyd
We study the existence of finite and infinite entangled graphs in the bond percolation process in three dimensions with density p. After a discussion of the relevant definitions, the entanglement...
Existence and uniqueness of infinite components in generic rigidity percolation (1998)
We consider a percolation configuration on a general lattice in which edges are included independently with probability p. We study the rigidity properties of the resulting configuration, in the...
Geoffrey R. Grimmett, Alexander E. Holroyd
We study ®nite and in®nite entangled graphs in the bond percolation process in three dimensions with density p. After a discussion of the relevant de®nitions, the entanglement critical...