Arctic circles, domino tilings and square Young tableaux (2009)
The arctic circle theorem of Jockusch, Propp, and Shor asserts that uniformly random domino tilings of an Aztec diamond of high order are frozen with asymptotically high probability outside the...
A formula for the doubly-refined enumeration of alternating sign matrices (2009)
Zeilberger proved the Refined Alternating Sign Matrix Theorem, which gives a product formula, first conjectured by Mills, Robbins and Rumsey, for the number of alternating sign matrices with given...
More refined enumerations of alternating sign matrices (2009)
We study a further refinement of the standard refined enumeration of alternating sign matrices (ASMs) according to their first two rows instead of just the first row, and more general "d-refined"...
Phase Transitions in Gravitational Allocation (2009)
Chatterjee, Sourav, Peled, Ron, Peres, Yuval, Romik, Dan
Given a Poisson point process of unit masses (``stars'') in dimension d>=3, Newtonian gravity partitions space into domains of attraction (cells) of equal volume. In earlier work, we showed the...
On Distributions Computable by Random Walks on Graphs * (2008)
Key words. Finite-state generator, automata, random walks on graphs, random number generation. AMS Subject Classifications. 65C10, 68Q05, 68Q70. Abstract. We answer a question raised by Donald E....
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...
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...
The Number of Guillotine Partitions in d Dimensions ∗ (2008)
Eyal Ackerman, Gill Barequet, Ron Y. Pinter, Dan Romik
Guillotine partitions play an important role in many research areas and application domains, e.g., computational geometry, computer graphics, integrated circuit layout, and solid modeling, to mention...
We prove two new formulas for the central trinomial coefficients and the Motzkin numbers. 1
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...
Article 03.2.4 Journal of Integer Sequences, Vol. 6 (2003), 2 (2007)
Some formulas for the central trinomial
Enumeration formulas for Young tableaux in a diagonal strip (2007)
Baryshnikov, Yuliy, Romik, Dan
We derive combinatorial identities, involving the Bernoulli and Euler numbers, for the numbers of standard Young tableaux of certain skew shapes. This generalizes the classical formulas of D. Andre...
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...
Gravitational allocation to Poisson points (2006)
Chatterjee, Sourav, Peled, Ron, Peres, Yuval, Romik, Dan
For d>=3, we construct a non-randomized, fair and translation-equivariant allocation of Lebesgue measure to the points of a standard Poisson point process in R^d, defined by allocating to each of the...
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...
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...
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...
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...
The dynamics of Pythagorean triples (2004)
We construct a piecewise onto 3-to-1 dynamical system on the positive quadrant of the unit circle, such that for rational points (which correspond to normalized Primitive Pythagorean Triples), the...
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...
Limit shapes for random square Young tableaux and plane partitions (2004)
Our main result is a limit shape theorem for the two-dimensional surface defined by a uniform random n-by-n square Young tableau. The analysis leads to a calculus of variations minimization problem...
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...
Shortest paths in the Tower of Hanoi graph and finite automata (2003)
We present efficient algorithms for constructing a shortest path between two states in the Tower of Hanoi graph, and for computing the length of the shortest path. The key element is a finite-state...
Explicit formulas for hook walks on continual Young diagrams (2003)
We consider, following the work of S. Kerov, random walks which are continuous-space generalizations of the Hook Walks defined by Greene-Nijenhuis-Wilf, performed under the graph of a continual Young...
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
Shortest paths in the Tower of Hanoi graph and finite automata (2003)
Abstract. We present efficient algorithms for constructing a shortest path between two configurations in the Tower of Hanoi graph, and for computing the length of the shortest path. The key element...
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...
Sharp entropy bounds for discrete statistical simulation
We define a general procedure for simulating a given discrete distribution using a sequence of i.i.d. random variables. This procedure is used to prove that a natural information-theoretic bound on...