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 >=...
Perfect matchings for the three-term Gale-Robinson sequences (2009)
Bousquet-Mélou, Mireille, Propp, James, West, Julian
In 1991, David Gale and Raphael Robinson, building on explorations carried out by Michael Somos in the 1980s, introduced a three-parameter family of rational recurrence relations, each of which (with...
Tiling Lattices with Sublattices (2009)
Feldman, David, Propp, James, Robins, Sinai
We use Fourier methods to prove that if $n > 1$ translates of sublattices of $Z^d$ tile $Z^d$, and all the sublattices are Cartesian products of arithmetic progressions, then two of the tiles must be...
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,...
Perfect matchings for the three-term Gale-Robinson sequences (2009)
Bousquet-Mélou, Mireille, Propp, James, West, Julian
In 1991, David Gale and Raphael Robinson, building on explorations carried out by Michael Somos in the 1980s, introduced a three-parameter family of rational recurrence relations, each of which (with...
Perfect matchings for the three-term Gale-Robinson sequences (2009)
Bousquet-Mélou, Mireille, Propp, James, West, Julian
In 1991, David Gale and Raphael Robinson, building on explorations carried out by Michael Somos in the 1980s, introduced a three-parameter family of rational recurrence relations, each of which (with...
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...
Degree-growth of monomial maps (2006)
Hasselblatt, Boris, Propp, James
For projectivizations of rational maps Bellon and Viallet defined the notion of algebraic entropy using the exponential growth rate of the degrees of iterates. We want to call this notion to the...
Combinatorial interpretations for rank-two cluster algebras of affine type (2006)
Fomin and Zelevinsky show that a certain two-parameter family of rational recurrence relations, here called the (b,c) family, possesses the Laurentness property: for all b,c, each term of the (b,c)...
The combinatorics of frieze patterns and Markoff numbers (2005)
This article, based on joint work with Gabriel Carroll, Andy Itsara, Ian Le, Gregg Musiker, Gregory Price, Dylan Thurston, and Rui Viana, presents a combinatorial model based on perfect matchings...
Topological entropy for non-uniformly continuous maps (2005)
Hasselblatt, Boris, Nitecki, Zbigniew, Propp, James
The topological entropy of a continuous self-map of a compact metric space can be defined in several distinct ways; when the space is not assumed compact, these definitions can lead to distinct...
Lambda-determinants and domino-tilings (2004)
Consider the $2n$-by-$2n$ matrix $M=(m_{i,j})_{i,j=1}^{2n}$ with $m_{i,j} = 1$ for $i,j$ satisfying $|2i-2n-1|+|2j-2n-1| \leq 2n$ and $m_{i,j} = 0$ for all other $i,j$, consisting of a central...
Lattice structure for orientations of graphs (2002)
Earlier researchers have studied the set of orientations of a connected finite graph $G$, and have shown that any two such orientations having the same flow-difference around all closed loops can be...
The many faces of alternating-sign matrices (2002)
I give a survey of different combinatorial forms of alternating-sign matrices, starting with the original form introduced by Mills, Robbins and Rumsey as well as corner-sum matrices, height-function...
Exponentiation and Euler measure (2002)
Two of the pillars of combinatorics are the notion of choosing an arbitrary subset of a set with $n$ elements (which can be done in $2^n$ ways), and the notion of choosing a $k$-element subset of a...
Euler measure as generalized cardinality (2002)
Schanuel has pointed out that there are mathematically interesting categories whose relationship to the ring of integers is analogous to the relationship between the category of finite sets and the...
Generating A Random Sink-Free Orientation In (2002)
Quadratic Time Henry, Henry Cohn, Robin Pemantle, James Propp
A sink-free orientation of a nite undirected graph is a choice of orientation for each edge such that every vertex has out-degree at least 1. Bubley and Dyer (1997) use Markov Chain Monte Carlo to...
Generalized domino-shuffling (2001)
The problem of counting tilings of a plane region using specified tiles can often be recast as the problem of counting (perfect) matchings of some subgraph of an Aztec diamond graph A_n, or more...
A reciprocity theorem for domino tilings (2001)
Let T(m,n) denote the number of ways to tile an m-by-n rectangle with dominos. For any fixed m, the numbers T(m,n) satisfy a linear recurrence relation, and so may be extrapolated to negative values...
Generating a random sink-free orientation in quadratic time (2001)
Cohn, Henry, Pemantle, Robin, Propp, James
A sink-free orientation of a finite undirected graph is a choice of orientation for each edge such that every vertex has out-degree at least 1. Bubley and Dyer (1997) use Markov Chain Monte Carlo to...
Local statistics for random domino tilings of the Aztec diamond (2000)
Cohn, Henry, Elkies, Noam, Propp, James
We prove an asymptotic formula for the probability that, if one chooses a domino tiling of a large Aztec diamond at random according to the uniform distribution on such tilings, the tiling will...
A variational principle for domino tilings (2000)
Cohn, Henry, Kenyon, Richard, Propp, James
We formulate and prove a variational principle (in the sense of thermodynamics) for random domino tilings, or equivalently for the dimer model on a square grid. This principle states that a typical...
Enumeration of Matchings: Problems and Progress (1999)
This document is built around a list of thirty-two problems in enumeration of matchings, the first twenty of which were presented in a lecture at MSRI in the fall of 1996. I begin with a capsule...
Three-player impartial games (1999)
Past efforts to classify impartial three-player combinatorial games (the theories of Li and Straffin) have made various restrictive assumptions about the rationality of one's opponents and the...
Enumeration of Matchings: Problems and Progress (1999)
. This document is built around a list of thirty-two problems in enumeration of matchings, the first twenty of which were presented in a lecture at MSRI in the fall of 1996. I begin with a capsule...
Enumeration of Matchings: Problems and Progress (1999)
: This document is built around a list of thirty-two problems in enumeration of matchings, the first twenty of which were presented in a lecture at MSRI in the fall of 1996. I begin with a capsule...
The shape of a typical boxed plane partition (1998)
Cohn, Henry, Larsen, Michael, Propp, James
Using a calculus of variations approach, we determine the shape of a typical plane partition in a large box (i.e., a plane partition chosen at random according to the uniform distribution on all...
Twenty Open Problems in Enumeration of Matchings (1998)
This document is an exposition of an assortment of open problems arising from the exact enumeration of (perfect) matchings of finite graphs. Roughly half have been solved at the time of this writing;...
Twenty Open Problems in Enumeration of Matchings: Progress Report (1998)
This document is a brief summary of progress that has been made on the problems posed in the document "Twenty Open Problems in Enumeration of Matchings" (also available from this server as...
Generating Random Elements of Finite Distributive Lattices (1998)
This survey article describes a method for choosing uniformly at random from any finite set whose objects can be viewed as constituting a distributive lattice. The method is based on ideas of the...
Domino tilings with barriers (1998)
Propp, James, Stanley, Richard
In this paper, we continue the study of domino-tilings of Aztec diamonds. In particular, we look at certain ways of placing ``barriers'' in the Aztec diamond, with the constraint that no domino may...
Random Domino Tilings and the Arctic Circle Theorem (1998)
Jockusch, William, Propp, James, Shor, Peter
In this article we study domino tilings of a family of finite regions called Aztec diamonds. Every such tiling determines a partition of the Aztec diamond into five sub-regions; in the four outer...
A variational principle for domino tilings (1998)
Henry Cohn, Richard Kenyon, James Propp, Dedicated Pieter, Willem Kasteleyn
Abstract. We formulate and prove a variational principle (in the sense of thermodynamics) for random domino tilings, or equivalently for the dimer model on a square grid. This principle states that a...
The Shape of a Typical Boxed Plane Partition (1998)
Henry Cohn, Michael Larsen, James Propp
. Using a calculus of variations approach, we determine the shape of a typical plane partition in a large box (i.e., a plane partition chosen at random according to the uniform distribution on all...
A Variational Principle For Domino Tilings (1998)
Henry Cohn, Richard Kenyon, James Propp, Dedicated Pieter, Willem Kasteleyn
. We formulate and prove a variational principle (in the sense of thermodynamics) for random domino tilings, or equivalently for the dimer model on a square grid. This principle states that a typical...
Enumeration of Matchings (1998)
: This document is built around a list of twenty problems in enumeration of matchings that were gathered together in 1996 and presented in a lecture at MSRI that fall. Since then, roughly half of the...
A variational principle for domino tilings (1998)
Henry Cohn, Richard Kenyon, James Propp, Dedicated Pieter, Willem Kasteleyn
The effect of boundary conditions is, however, not entirely trivial and will be discussed in more detail in a subsequent paper. P. W. Kasteleyn, 1961 1.
Generating random elements of finite distributive lattices (1997)
Abstract. This survey article describes a method for choosing uniformly at random from any finite set whose objects can be viewed as constituting a distributive lattice. The method is based on ideas...
Generating random elements of finite distributive lattices (1997)
Abstract. This survey article describes a method for choosing uniformly at random from any finite set whose objects can be viewed as constituting a distributive lattice. The method is based on ideas...
Generating Random Elements Of Finite Distributive Lattices (1997)
. This survey article describes a method for choosing uniformly at random from any finite set whose objects can be viewed as constituting a distributive lattice. The method is based on ideas of the...
Coupling from the Past: a User's Guide (1997)
. The Markov chain Monte Carlo method is a general technique for obtaining samples from a probability distribution. In earlier work, we showed that for many applications one can modify the Markov...
A Pedestrian Approach to A Method of Conway, or, A Tale of Two Cities (1997)
this article. Define an Aztec diamond of order n as a region consisting of 2n(n+ 1) unit cells, arranged in centered rows of lengths 2; 4; 6; : : : ; 2n \Gamma 2; 2n; 2n; 2n \Gamma 2; : : : ; 6; 4;...
Boundary-Dependent Local Behavior For 2-D Dimer Models (1997)
robably do not correspond to any physical properties of the substances that the dimer models were originally introduced to model. However, insofar as the study of exactly solved models has taken on a...
Exponentiation and Euler characteristic (1996)
Introduction In the work of Hadwiger, Lenz, McMullen, Rota, Chen, and others, Euler characteristic of polytopes in R n is extended to a valuation Ø on the algebra of sets generated by these...
Local Statistics For Random Domino Tilings Of The Aztec Diamond (1996)
Henry Cohn, Noam Elkies, James Propp
. We prove an asymptotic formula for the probability that, if one chooses a domino tiling of a large Aztec diamond according to the uniform distribution on such tilings, the tiling will contain a...
Generating Random Elements of Finite Distributive Lattices (1996)
. This survey article describes a method for choosing uniformly at random from any finite set whose objects can be viewed as constituting a distributive lattice. The method is based on ideas of the...
The Shape Of A Typical Boxed Plane Partition (1996)
Henry Cohn, Michael Larsen, James Propp
. Using a calculus of variations approach, we determine the shape of a typical plane partition in a large box (i.e., a plane partition chosen at random according to the uniform distribution on all...
Further travels with my ant (1995)
Gale, David, Propp, James, Sutherland, Scott, Troubetzkoy, Serge
We discuss some properties of a class of cellular automata sometimes called a "generalized ant". This system is perhaps most easily understood by thinking of an ant which moves about a lattice in the...
The Fractional Chromatic Number Of Mycielski's Graphs (1995)
Michael Larsen, James Propp, Daniel Ullman
The most familiar construction of graphs whose clique number is much smaller than their chromatic number is due to Mycielski, who constructed a sequence G n of triangle-free graphs with Ø(Gn ) = n....
The Projective Fundamental Group of a Z²-Shift (1993)
We define a new invariant for symbolic Z 2 -actions, the projective fundamental group. This invariant is the limit of an inverse system of groups, each of which is the fundamental group of a space...
On Tensor Powers Of Integer Programs (1992)
Robin Pemantle, James Propp, Daniel Ullman
We define a natural product on integer programming problems with nonnegative coefficients. Hypergraph covering problems are a special case of such integer programs, and the product we define is a...
Alternating sign matrices and domino tilings (1991)
Elkies, Noam, Kuperberg, Greg, Larsen, Michael, Propp, James
We introduce a family of planar regions, called Aztec diamonds, and study the ways in which these regions can be tiled by dominoes. Our main result is a generating function that not only gives the...