James Propp

Enumeration of Matchings: Problems and Progress

James Propp

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…

math.CO2024

Trimer covers in the triangular grid: twenty mostly open problems

James Propp

In the past three decades, the study of rhombus tilings and domino tilings of various plane regions has been a thriving subfield of enumerative combinatorics. Physicists classify s…

Brussels Sprouts, Noncrossing Trees, and Parking Functions

Caleb Ji, James Propp

We consider a variant of the game of Brussels Sprouts that, like Conway's original version, ends in a predetermined number of moves. We show that the endstates of the game are in n…

math.CO2013

Chip-Firing and Rotor-Routing on Directed Graphs

Alexander E. Holroyd, Lionel Levine, Karola Meszaros +3

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 s…

math.PR2015

Formation of an interface by competitive erosion

Shirshendu Ganguly, Lionel Levine, Yuval Peres +1

In 2006, the fourth author proposed a graph-theoretic model of interface dynamics called competitive erosion. Each vertex of the graph is occupied by a particle that can be either…

math.DS1995

Further travels with my ant

David Gale, James Propp, Scott Sutherland +1

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 abo…

math.CO2011

Local-to-global principles for rotor walk

Giuliano Pezzolo Giacaglia, Lionel Levine, James Propp +1

In rotor walk on a finite directed graph, the exits from each vertex follow a prescribed periodic sequence. Here we consider the case of rotor walk where a particle starts from a d…

math.CO2003

Exponentiation and Euler measure

James Propp

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$ -el…

math.CO2007

Combinatorial interpretations for rank-two cluster algebras of affine type

Gregg Musiker, James Propp

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…

math.CO2024

Tilings of Benzels via Generalized Compression

Colin Defant, Leigh Foster, Rupert Li +2

Defant, Li, Propp, and Young recently resolved two enumerative conjectures of Propp concerning the tilings of regions in the hexagonal grid called benzels using two types of protot…

math.CO2015

Lessons I learned from Richard Stanley

James Propp

I will share with the reader what I have learned from Richard Stanley and the ways in which he has contributed to research in combinatorics conducted by me and my collaborators.

math.CO1991

Alternating sign matrices and domino tilings

Noam Elkies, Greg Kuperberg, Michael Larsen +1

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 no…

Euler measure as generalized cardinality

James Propp

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 fi…

Combinatorial, piecewise-linear, and birational homomesy for products of two chains

David Einstein, James Propp

This article illustrates the dynamical concept of $h o m o m esy$ in three kinds of dynamical systems -- combinatorial, piecewise-linear, and birational -- and shows the relationship be…

math.CO2023

Homomesy via Toggleability Statistics

Colin Defant, Sam Hopkins, Svetlana PoznanoviÄ +1

The rowmotion operator acting on the set of order ideals of a finite poset has been the focus of a significant amount of recent research. One of the major goals has been to exhibit…

math.CO2009

Perfect matchings for the three-term Gale-Robinson sequences

Mireille Bousquet-MÃ©lou, James Propp, Julian West

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,…

Quantifying Noninvertibility in Discrete Dynamical Systems

Colin Defant, James Propp

Given a finite set $X$ and a function $f : X \to X$ , we define the degree of noninvertibility of $f$ to be $deg (f) = \frac{1}{∣ X ∣} x \in X \sum ∣ f^{- 1} (f (x)) ∣$ . This…

math.PR2022

A Greedy Chip-firing Game

Rupert Li, James Propp

We introduce a deterministic analogue of Markov chains that we call the hunger game. Like rotor-routing, the hunger game deterministically mimics the behavior of both recurrent Mar…

math.CO2011

Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions

Steven Linton, James Propp, Tom Roby +1

We consider a large family of equivalence relations on permutations in Sn that generalise those discovered by Knuth in his study of the Robinson-Schensted correspondence. In our mo…

math.DS2007

Degree-growth of monomial maps

Boris Hasselblatt, James Propp

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…

math.CO2000

Local statistics for random domino tilings of the Aztec diamond

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 at random according to the uniform distribution on such tilings, th…

math.CO2026

Random Domino Tilings and the Arctic Circle Theorem

William Jockusch, James Propp, Peter Shor

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…

nlin.CG2010

Discrete analogue computing with rotor-routers

James Propp

Rotor-routing is a procedure for routing tokens through a network that can implement certain kinds of computation. These computations are inherently asynchronous (the order in whic…

math.CO2001

A variational principle for domino tilings

Henry Cohn, Richard Kenyon, James Propp

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 stat…

math.CO2025

Whirling injections, surjections, and other functions between finite sets

Michael Joseph, James Propp, Tom Roby

This paper analyzes a certain action called "whirling" that can be defined on any family of functions between two finite sets equipped with a linear (or cyclic) ordering. Many maps…

math.CO2021

A spectral theory for combinatorial dynamics

James Propp

This article proposes a framework for the study of periodic maps $T$ from a (typically finite) set $X$ to itself when the set $X$ is equipped with one or more real- or complex-valu…

math.HO2013

Real Analysis in Reverse

James Propp

Many of the theorems of real analysis, against the background of the ordered field axioms, are equivalent to Dedekind completeness, and hence can serve as completeness axioms for t…

math.CO2014

Piecewise-linear and birational toggling

David Einstein, James Propp

We define piecewise-linear and birational analogues of the toggle-involutions on order ideals of posets studied by Striker and Williams and use them to define corresponding analogu…

math.CO2010

Discrete low-discrepancy sequences

Omer Angel, Alexander E. Holroyd, James B. Martin +1

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…

math.CO2022

Tilings of Benzels via the Abacus Bijection

Colin Defant, Rupert Li, James Propp +1

Propp recently introduced regions in the hexagonal grid called benzels and stated several enumerative conjectures about the tilings of benzels using two types of prototiles called…

math.CO2024

Some 2-adic conjectures concerning polyomino tilings of Aztec diamonds

James Propp

For various sets of tiles, we count the ways to tile an Aztec diamond of order $n$ using tiles from that set. The resulting function $f (n)$ often has interesting behavior when one…

math.CO2016

Sorting via chip-firing

Sam Hopkins, Thomas McConville, James Propp

We investigate a variant of the chip-firing process on the infinite path graph: rather than treating the chips as indistinguishable, we label them with positive integers. To fire a…

#dimer models#q-deformation#real numbers#partially ordered sets

Germ order for one-dimensional packings

Aaron Abrams, Henry Landau, Zeph Landau +3

Every set of natural numbers determines a generating function convergent for $q \in (- 1, 1)$ whose behavior as $q \to 1^{-}$ determines a germ. These germs admit a natural par…

math.CO2015

Homomesy in products of two chains

James Propp, Tom Roby

Many invertible actions $I ¨ $ on a set $S$ of combinatorial objects, along with a natural statistic $f$ on $S$ , exhibit the following property which we dub \…

math.PR2026

Dimers, filters, and $q$ -deformed real numbers

James Propp

The paper introduces a q‑parameterized function [[x]]_q for each positive real number x by constructing an inhomogeneous dimer model (equivalently, a filter model on a poset) and s…

Twenty Open Problems in Enumeration of Matchings: Progress Report

James Propp

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 s…

math.CO2010

Tiling Lattices with Sublattices, II

David Feldman, James Propp, Sinai Robins

Our earlier article proved 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…

Twenty Open Problems in Enumeration of Matchings

James Propp

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 ti…

Generalized domino-shuffling

James Propp

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 grap…

The many faces of alternating-sign matrices

James Propp

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 matrice…

Three-player impartial games

James Propp

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 oppon…

math.CO2023

A pentagonal number theorem for tribone tilings

Jesse Kim, James Propp

Conway and Lagarias showed that certain roughly triangular regions in the hexagonal grid cannot be tiled by shapes Thurston later dubbed tribones. Here we study a two-parameter fam…

math.CO2010

Tiling Lattices with Sublattices, I

David Feldman, James Propp, Sinai Robins

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 o…

math.CO2014

Dimers and Dominoes

James Propp

Using Kasteleyn's determinant method, we count perfect matchings of rectangular subgraphs of the square grid.

The combinatorics of frieze patterns and Markoff numbers

James Propp

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 pe…

math.CO1998

Generating Random Elements of Finite Distributive Lattices

James Propp

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…

math.CO2025

Lattice structure for orientations of graphs

James Propp

In 1986, Oliver Pretzel studied the set of orientations of a connected finite graph $G$ and showed that any two such orientations having the same flow-difference around all closed…

math.CO2016

Noncrossing partitions, toggles, and homomesies

David Einstein, Miriam Farber, Emily Gunawan +4

We introduce $n (n - 1) /2$ natural involutions ("toggles") on the set $S$ of noncrossing partitions $I ¨ $ of size $n$ , along with certain composite operations obtained by composing the…

math.CO2026

Grid designs

Alon Danai, Joshua Kou, Andy Latto +2

We define a grid graph $G$ as a Cartesian product of path-graphs $P_{n}$ or cycle-graphs $C_{n}$ as shown in Figure 1, and we ask, when can the edge set of a complete graph be expresse…

math.CO2004

Lambda-determinants and domino-tilings

James Propp

Consider the $2 n$ -by- $2 n$ matrix $M = (m_{i, j})_{i, j = 1}^{2 n}$ with $m_{i, j} = 1$ for $i, j$ satisfying $∣2 i - 2 n - 1∣ + ∣2 j - 2 n - 1∣ \leq 2 n$ and $m_{i, j} = 0$ for all other $i, j$ , consisting…

math.PR2002

Generating a random sink-free orientation in quadratic time

Henry Cohn, Robin Pemantle, James Propp

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 Ch…

Domino tilings with barriers

James Propp, Richard Stanley

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 t…

math.CO2001

A reciprocity theorem for domino tilings

James Propp

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…

math.CO2025

Hyperbinary partitions and q-deformed rationals

Thomas McConville, James Propp, Bruce E. Sagan

A hyperbinary partition of the nonnegative integer n is a partition where every part is a power of 2 and every part appears at most twice. We give three applications of the length…

math.PR2010

Rotor Walks and Markov Chains

Alexander E. Holroyd, James Propp

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 f…

math.DS2005

Topological entropy for non-uniformly continuous maps

Boris Hasselblatt, Zbigniew Nitecki, James Propp

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 lea…