(Note that an electronic bibliography of my published research (last updated in September 2004) is available, thanks to Jim Pitman. Also, most of my recent work has been posted to the arXiv.

I really like Martin A. Schwartz's article The importance of stupidity in scientific research as a description of the sort of temperament that's recommended for someone who wants to be both a researcher and a happy person, though I personally don't tend to feel stupid as much as I feel chronically stuck. Progress comes in gushes, and I spend weeks in between those gushes, trying out ideas that don't work until I find one that does.

The newer articles are available as PDF files. The older articles are available as both compressed and uncompressed Postscript files. The default versions of older articles, obtained by clicking on the titles, are compressed (via gzip); many browsers take care of de-compression automatically. If you want an uncompressed file, just delete the .gz suffix of a file-name. If there are problems, please let me know! (My email address is JamesPropp at gmail dot calm, with the last word respelled.)

I've arranged these links into six sections: Dynamical Algebraic Combinatorics, Random and Quasirandom Sampling, Tiling, Games and Puzzles, Teaching, Miscellaneous, and Expository (including book reviews), Within each section, I've made an effort to sort the articles in reverse chronicial order (though that can get dicey, since the order in which articles are written isn't always the same as the order in which they are published).

DYNAMICAL ALGEBRAIC COMBINATORICS

Homomesy in products of two chains by James Propp and Tom Roby, accepted by the conference Formal Power Series and Algebraic Combinatorics 2013. "Homomesy" is our term for the constant-orbit-along-averages property first observed by Panyushev. In future articles, Roby and I and others will show how pervasive this phenomenon is, both within and beyond combinatorics.

RANDOM AND QUASIRANDOM SAMPLING

Rotor Walks and Markov Chains by A. Holroyd and J. Propp, Algorithmic Probability and Combinatorics, Manuel E. Lladser, Robert S. Maier, Marni Mishna, and Andrew Rechnitzer, Editors, Contemporary Mathematics, volume 520, pp. 105-126.

Chip-firing and rotor-routing on directed graphs by A. Holroyd, L. Levine, K. Meszaros, Y. Peres, J. Propp, and D. Wilson (to appear in In and out of Equilibrium II, edited by V. Sidoravicius and M.E. Vares, Birkhauser 2008) gives some of the combinatorial and algebraic background for my forthcoming publications on derandomization with rotor-routers.

Discrete low-discrepancy sequences by Omer Angel, Alexander Holroyd, James Martin, and myself gives a simple algorithm for designing deterministic stack versions of iid random processes (when all probabilities are rational, these deterministic stacks turn out to be rotor-routers). After writing this article, my collaborators and I learned that our main results were already proved by Tijdeman.

Generalized Domino-Shuffling (Theoretical Computer Science vol. 303, 267-301 (2003)) shows how the problems of counting domino-tilings of regions, computing placement-probabilities, and generating domino-tilings at random are linked together in a uniform framework that extends the earlier version of the shuffling algorithm described in Alternating-Sign Matrices and Domino Tilings (see below).

Generating a Random Sink-Free Orientation in Quadratic Time (by Henry Cohn, Robin Pemantle and myself; Electronic Journal of Combinatorics, volume 9 (2002) article R10; last revised March 27, 2001) shows how David Wilson's cycle-popping trick can be applied in a different setting. Are there other "partial-rejection" sampling algorithms waiting to be found?

How to Get a Perfectly Random Sample From a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph, by David Wilson and myself (last revised April 9, 1998; published in the Journal of Algorithms, volume 27 (1998), pages 170-217) applies the coupling from the past protocol to some different sorts of problems.

Coupling from the Past: A User's Guide (by myself and David Wilson; last revised January 30, 1998), was published in the proceedings of the DIMACS-sponsored workshop Microsurveys in Discrete Probability.

Generating Random Elements of Finite Distributive Lattices (last revised January 13, 1998; published in the Electronic Journal of Combinatorics, volume 4, issue 2, article R15) is an exposition of the Propp-Wilson coupling-from-the-past method in the context of some specific combinatorial applications. Note that the version published in the Electronic Journal of Combinatorics has some appended comments by me; these comments appear at the end of the updated version of the article that is on my Web-page.

Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics by David Wilson and myself (last revised July 16, 1996; published in Random Structures and Algorithms, volume 9 (1996), pages 223-252) describes a variant of Monte Carlo schemes for random generation of combinatorial objects that converges to the steady-state distribution in finite time, rather than infinite time, through use of a method we call coupling from the past. This paper was presented at the 1995 conference on Random Structures and Algorithms, and (along with the companion paper published in the Journal of Algorithms in 1998) was awarded with Institute for Operations Research and the Management Sciences (INFORMS) College on Simulation's Outstanding Simulation Publication Award in 2000). David Wilson has written an annotated bibliography of related papers on the topic of "perfect sampling".

TILINGS AND MATCHINGS

Perfect matchings for the three-term Gale-Robinson sequences by Mireille Bousquet-Mélou, Julian West, and myself presents a combinatorial model for a class of integer sequences defined by rational recurrences, thereby providing an enumerative proof of the integrality of these sequences.

Tiling Lattices with Sublattices, I by David Feldman, Sinai Robins, and myself gives the classic generating-functions proof of the Mirsky-Newman theorem a Fourier-theoretic makeover and generalizes it to higher dimensions. See also Tiling Lattices with Sublattices, II by David Feldman, Sinai Robins, and myself, which is currently in preparation; among other things, this article shows that a suitable version of the original Mirsky-Newman proof does in fact apply to the higher-dimensional version.

Combinatorial Interpretations for Rank-Two Cluster Algebras of Affine Type by Gregg Musiker and myself gives a combinatorial account of the recurrence f(n) = (f(n-1)² + 1)/f(n-2), as well as the variant in which the exponent of f(n-1) alternates between the values 1 and 4, according to the parity of n. As is the case for many (though not all) cases of algebraic recurrences with the Laurent property (see for instance the next article in this list!), perfect matchings of graphs turn out to be a convenient language for explaining what is going on. (This article is also available on the web at math.CO/0602408, but for some reason the arXiv versions of the PostScript and PDF files aren't as sharp-looking as the one at the EJC site.)

The preprint The combinatorics of frieze patterns and Markoff numbers (math.CO/0511633), based on work done with REACH students Gabriel Carroll, Andy Itsara, Ian Le, Gregg Musiker, Gregory Price, Dylan Thurston, and Rui Viana, presents a combinatorial model based on perfect matchings that explains the symmetries of the numerical arrays that Conway and Coxeter dubbed frieze patterns. This paper was presented at the 18th International Conference on Formal Power Series & Algebraic Combinatorics ("FPSAC 2006").

The article Lambda-determinants and domino-tilings (math.CO/0406301, Advances in Applied Mathematics, Volume 34, Issue 4, May 2005, pages 871-879) appeared in a special issue dedicated to David Robbins. I've decided to stop publishing my work in Elsevier journals, but I made an exception for David. The main thing this article offers is a simple and efficient recursive scheme for using integer arithmetic to compute the number of domino-tilings of a 2n-by-2n square.

The article A Reciprocity Theorem for Domino Tilings (last revised April 30, 2001; published in the Electronic Journal of Combinatorics, volume 8(1), 2001, article R18) explains why there is a natural way of extending the notion of domino tilings of m-by-n rectangles to situations in which n is negative – and why, when n is negative, domino tilings of an m-by-n rectangle have a lot to do with domino tilings of an m-by-(– 2 – n) rectangle.

The Many Faces of Alternating-Sign Matrices (published in "Discrete Models: Combinatorics, Computation, and Geometry", a special issue of Discrete Mathematics and Theoretical Computer Science, published July 2001; on-line version last revised August 15, 2002) is an overview of the many different combinatorial forms of alternating-sign matrices, including corner-sum matrices, height-function matrices, three-colorings, monotone triangles, tetrahedral order ideals, square ice, gasket-and-basket tilings and full packings of loops.

A Variational Principle for Domino Tilings (with Henry Cohn and Rick Kenyon, published in the Journal of the AMS, volume 14 (2001), pages 297-346) gives a very general answer to the question "In how many ways can a region be tiled by dominos?" This question turns out to be intimately related to the question of the asymptotic behavior of randomly-tiled larged regions. The statistical behavior of random tilings can be highly non-homogeneous; a quantitative analysis of this non-homogeneity is one of the main ingredients of a formula for the number of tilings.

Trees and Matchings by Rick Kenyon, David Wilson and myself (published in the Electronic Journal of Combinatorics, Vol. 7(1) (2000), article R25) generalizes Temperley's bijection to the setting of general planar directed (or undirected) graphs whose edges may carry nonnegative weights that induce a weighting on the set of spanning trees. We show that the weighted, directed spanning trees of any planar weighted directed graph G can be put into a one-to-one weight-preserving correspondence with perfect matchings of a related weighted planar graph H. A special case of this result gives a bijection between lozenge-tilings of certain planar regions and directed spanning trees on associated subgraphs of a triangular lattice. (Also available, for the sake of completeness, is an unpublished earlier article on the same subject, with fewer results and no coauthors.)

Enumeration of Matchings: Problems and Progress (published in New Perspectives in Geometric Combinatorics, edited by Billera et al.; Cambridge University Press, 1999) 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 maintain a document giving updates on the status of these problems (most recently updated on May 8, 2007).

Domino Tilings with Barriers by Richard Stanley and myself (last revised November 12, 1998; published in the Journal of Combinatorial Theory, Series A, vol. 87 (1999), pages 347-356) gives a proof of a curious "independence" assertion about random domino tilings.

The Shape of a Typical Boxed Plane Partition by Henry Cohn, Michael Larsen, and myself (published in the New York Journal of Mathematics, 4 (1998), 137-165) analyzes the behavior of a typical plane partition in which the number of rows, the number of columns, and the maximum size of any part are bounded above by specified values (but the size of the partition, that is, the sum of the parts is allowed to vary); equivalently (and this is where the relevance to tiling comes in), the paper determines the asymptotic behavior of a random tiling of a hexagon by unit rhombuses. Here, as in the two preceding papers, there is a central region, perfectly circular in the limit, in which tiles of different orientations tend to be interspersed, and a residual outer region in which tiles tend to line up with their neighbors. The article is on the web at http://arxiv.org/abs/math/9801059.

A Pedestrian Approach to a Method of Conway, or, A Tale of Two Cities (published in the December 1997 issue of Mathematics Magazine) is my own attempt to expound the ideas on boundary-invariants of tilings introduced by Conway and developed further by Thurston. My goal was to remove all the apparatus of combinatorial group theory and present the intuitive kernel of the method. The illustrations are available separately, but are not suited for reading via ghostview. (Note: there's an even simpler way to think about the problem, using ideas I got from reading work by Moore and Pak. Or, if you prefer the Conway-Lagarias approach, you can look at Mike Reid's method.)

Boundary-Dependent Local Behavior for 2-D Dimer Models (last revised June 6, 1996; published in the International Journal of Modern Physics B, volume 11 (1997), pages 183-187) gives an idea of how I and my collaborators hope to apply our earlier ideas from the combinatorial study of domino tilings in the setting of statistical mechanics. (Note that the figures are at the end of the article.) Unfortunately, the idea of "effective fields" does not apply as broadly as the closing paragraphs of the article suggest, but the approach still has some promise.

I gave a poster-presentation at the 1996 conference on Formal Power Series and Algebraic Combinatorics, entitled Counting Constrained Domino Tilings of Aztec Diamonds. (It's a preview of results that will appear in a forthcoming paper by Henry Cohn, Peter Du, Ira Gessel, Alex Ionescu Robin Pemantle, and myself, obtained by a method described in the paper Generalized Domino-Shuffling, listed above. You can also check out the displays that were used in my talk Diabolo Tilings of Fortresses (presented in the MIT Combinatorics Seminar on 5/13/98). You'll need to gunzip the file and view it with gs (not ghostview) or print it out.

Local Statistics for Random Domino Tilings of the Aztec Diamond by Henry Cohn, Noam Elkies and myself (last revised November 30, 1995; published in the Duke Mathematical Journal, volume 85 (1996), pages 117-166) gives an exact formula governing the behavior of random domino tilings inside the arctic circle. We also give a new proof of the arctic circle theorem and extend our ideas to apply to random domino tilings of finite planar regions in general.

Random Domino Tilings and the Arctic Circle Theorem by William Jockusch, Peter Shor and myself (last revised October 10, 1995) starts from a problem about random tilings and gradually transforms the problem until it devolves into a question about interacting particles. In this way we are able to prove that a random domino tiling of a large Aztec diamond has different kinds of statistical behavior on different sub-regions, and that in particular, there is a sharp transition between ``random-looking'' and ``non-random-looking'' behavior when one crosses a certain domain-boundary that is asymptotically a perfect circle (the ``arctic circle'' of the title). This is the new (but not yet final) 10/10/95 version. Click here for the figures.

Lattice Structure for Orientations of Graphs (last modified April 26, 1994) gives a unified framework for understanding various partial orderings that have imposed on various classes of combinatorial objects, including matchings and alternating-sign matrices.

The Projective Fundamental Group of a Z^2-Shift by William Geller and myself (last revised October 26, 1993; published in Ergodic Theory and Dynamical Systems, volume 15 (1995), pages 1091-1118) describes one direction in which Thurston's Thurston's geometrical approach to Conway's theory can be extended. Unfortunately, the figures accompanying this article are unavailable via the Web; fortunately, the article appears in the December 1995 issue of Ergodic Theory and Dynamical Systems.

Alternating-Sign Matrices and Domino Tilings, by Noam Elkies, Greg Kuperberg, Michael Larsen, and myself (published in the Journal of Algebraic Combinatorics, volume 1 (1992), pages 111-132 and 219-234), is the first of my papers on tiling. A certain region, dubbed the Aztec Diamond of order n, has exactly 2 to the power n(n+1)/2 distinct tilings by 1-by-2 rectangles (or "dominos"). The original article contains four proofs of this fact, none of them as simple as one might hope; a slicker proof of this result is sketched in my slide-presentation A new proof of a formula of Richard Stanley, presented at the AMS/MAA Joint Winter Meetings in 1997. [Note: There are problems with the on-line version of Elkies-Kuperberg-Larsen-Propp: for instance, it's missing a title-page, and there's a discrepancy in the labelling of some of the figures. If you don't have access to the Journal of Algebraic Combinatorics and you want a copy of the final published version of this, let me know and I'll send you a reprint.] Click here for errata.

GAMES AND PUZZLES

The Eight Rotors Puzzle describes a puzzle I created for the Eighth Gathering for Gardner. To solve the puzzle, one must know (or figure out) some properties of the rotor-router model mentioned above. This write-up was submitted for the (not-to-be-published) ``gift book'' for G4G8 and will be submitted for publication in one of the published proceedings volumes.

Three-Player Impartial Games (published in Theoretical Computer Science, volume 233 (2000), pages 263-278) describes an extension of the theory of impartial ("Nim-like") games to situations in which there are more than two players.

Combinatorial Games under Auction Play by Andrews Lazarus, Danny Loeb, Walter Stromquist, Dan Ullman and myself (published in Games and Economic Behavior, volume 27 (1999), pages 229-264; last revised September 12, 1997) concerns various ways of playing two-person games so that the right to make the next move is repeatedly being auctioned off to one player or the other. (This is a followup to my earlier article "Richman Games", described below.) Some of these results were later rediscovered by people studying random-turn selection games; see e.g., Random-turn Hex and other selection games by Yuval Peres, Oded Schramm, Scott Sheffield, and David Wilson.)

Richman Games by Andrew Lazarus, Danny Loeb, Dan Ullman and myself (published in "Games of No Chance", Richard Nowakowski, editor, MSRI volume 29, Cambridge University Press, 1996), is dedicated to the memory of mathematician David Richman, who came up with the original idea of auctioning off moves in a combinatorial game. (For a brief bio of David Richman, click here.)

A New Take Away Game (published in the book The Lighter Side of Mathematics, Richard K. Guy and Robert E. Woodrow, editors; MAA Spectrum, 1994; pages 212-221) introduces a variant of Nim in which heaps spontaneously decrease in size.

Surreal Vectors and the Game of Cutblock (August 22, 1994) was an attempt to generalize the theory of partizan games to situations in which there are more than two players. I still think my main conjecture about Cutblock is likely to be true, but Claim 2 is not (take P = R' = {1} and Q = R = P' = Q' = {}). Note that Figure 1, Figure 2, and the unnumbered figure at the bottom of page 4 are available separately.

On the Cookie Game by Dan Ullman and myself (published in the International Journal of Game Theory, volume 20 (1992), pages 313-324) answers some (but not all!) of the open questions raised in my article "A New Take Away Game" (written earlier but published later; see above).

TEACHING

A counterexample to integration by parts (published by Mathematics Magazine, volume 83 (2010), pages 222-225) by Alexander Kheifets and myself discusses an example in which f and g are differentiable functions to which the integration-by-parts formula does not apply.

A Frosh-Friendly Completeness Axiom for the Reals (still under development) describes the way I like to introduce students to the completeness property of the real numbers. After writing the article, I learned that the Cut Axiom that I describe is not new, but can be traced back to Dedekind! Some of this material will find its way into an article I plan to write on analogies between the induction property of the integers and the completeness property of the reals.

Carrying On With Infinite Decimals (a short version of a longer treatment I plan to write sometime between 2010 and 2020) discusses how one can construct, and operate with, real numbers as strings of digits. I'll need to know a bit more about chip-firing on infinite graphs before I feel I'm ready to carry out this construction in the sweetest possible way. This write-up was submitted for the (not-to-be-published) ``gift book'' for G4G9 (the ninth Gathering for Gardner conference), and will be submitted for publication in one of the published proceedings volumes.

MISCELLANEOUS

Real analysis in reverse (American Mathematical Monthly, Vol. 120, May 2013, pp. 392--408) shows that many theorems that students first encounter in a calculus class distinguish the ordered field of real numbers among all other ordered fields. A mistake was pointed out to me by Ricky Demer (see his most recent comment in the MathOverflow post on "propositions equivalent to the completeness of the real numbers"). On page 13 of the web-version of the article, I assert that the field of surreal numbers created before Day omega-sub-one can be used to show that the Nested Interval Property does not imply completeness; but this makes a tacit appeal to the Axiom of Choice. Indeed, one can't prove in ZF that there exists an ordinal with uncountable cofinality.

A Galois connection in the social network (Mathematics Magazine, Vol. 85, No. 1, February 2012, pp. 34--36) grew out of a problem I learned about when I was studying for prelims in U.C. Berkeley in the 1980s.

Discrete analogue computing with rotor-routers has been submitted to Chaos (specifically, to a Special Focus issue on Intrinsic and Designed Computation). This is an outgrowth of my interest in quasirandom simulation, though with a rather different focus.

Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions by Steven Linton, Tom Roby, Julian West, and myself (Journal of Integer Sequences, Vol. 15 (2012), Article 12.9.1) considers a family of equivalence relations on permutations in S_n in which two elements can be transposed conditional upon the presence of a third element of suitable value and location. This write-up was accepted for the poster session of FPSAC 2010.

I wrote an article with Kiran Kedlaya called In search of Robbins stability (math.NT/0409535, Advances in Applied Mathematics, Volume 34, Issue 4, May 2005, pages 659-668) that appeared in a special issue dedicated to David Robbins. (I've decided to stop publishing my work in Elsevier journals, but I made an exception for David.) This article, building on work by Robbins, makes a start toward explaining why certain sorts of algebraic recurrence (notably Dodgson condensation) are more numerically stable (p-adically) than one would expect.

In 1997, I posed two open problems at a workshop entitled Microsurveys in Discrete Probability, organized by myself and David Aldous and held at the Institute for Advanced Study: one problem on Continuum spanning trees and one problem on Spanning trees in high-dimensional grids. In the spring of 1998 the American Mathematical Society published Proceedings for this workshop.

Exponentiation and Euler Characteristic (published in Algebra Universalis, volume 49 (2003), pages 459-471), dedicated to the memory of Gian-Carlo Rota, describes some incompletely developed ideas of mine for how one might apply some naive notions in order to generalize the concept of Euler characteristic to certain huge infinite-dimensional spaces, like the space of piecewise-linear, not-necessarily-continuous maps from an interval to itself. You can also view this work, in part, as an attempt to make sense of the notion of sets whose cardinality is not a counting number (an idea that is also explored in my unpublished research memo Euler measure as generalized cardinality.)

The Fractional Chromatic Number of Mycielski's Graphs by Michael Larsen, Dan Ullman and myself (published in the Journal of Graph Theory, volume 19 (1995), pages 411-416) calculates the fractional chromatic numbers of an important sequence of graphs. One interesting feature of the calculation is that the denominators of these fractional chromatic numbers grow rather quickly.

Producing New Bijections from Old by David Feldman and myself (published in Advances in Mathematics, volume 113 (1995), pages 1-44) is concerned with questions of the following sort: If someone hands you a bijection between the Cartesian square of some finite set A and the Cartesian square of some finite set B, can you construct a bijection between the underlying sets A and B without making some arbitrary choices? If you like this article, you will probably enjoy John Conway and Peter Doyle's article on division by three.

Further Travels with My Ant (by David Gale, Scott Sutherland, Serge Troubetzkoy and myself; published in the Mathematical Intelligencer, volume 17 (1995), summer issue, pages 48-56; reprinted in the book "Tracking the Automatic Ant" by David Gale, pages 137-149) describes a cellular automaton model with some interesting features. In particular, one finds that certain symmetries (both transient and recurrent) arise naturally as the system evolves.

What is a ... Sandpile? by Lionel Levine and myself; to appear in the Notices of the American Mathematical Society.

Book review: The Cat in Numberland by Ivar Ekeland, illustrated by John O'Brien. This review appeared in the January 2009 issue of the Notices of the American Mathematical Society (volume 56, number 1, pages 31-32).

Book review: The Art of Mathematics: Coffee Time in Memphis by Béla Bollobás (illustrations by Gabriella Bollobás). This review appeared in the November-December 2007 issue of the American Scientist (volume 95, pages 536-538).

How the Alternating Sign Matrix Conjecture Was Solved by David Bressoud and myself (published in the Notices of the American Mathematical Society, volume 46 (1999), number 6, pages 637-646) tells the exciting story of how the problem arose through the work of Mills, Robbins, and Rumsey, and was eventually solved through the work of Zeilberger and Greg Kuperberg. If this article whets your appetite, you'll be glad to know that Bressoud has written a whole book on the subject, entitled Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture and published by MAA Spectrum. The ASM story is actually far from over; for two recent articles on the subject, see Symmetry Classes of Alternating-Sign Matrices Under One Roof by Greg Kuperberg and A Large Dihedral Symmetry of the Set of Alternating Sign Matrices by Ben Wieland.

Fermat's Last Theorem and the Fourth Dimension gives a peek into some of the mathematics that went into the solution of this problem by Andrew Wiles, and in particlar, the connection between FLT and elliptic curves.

Chinook is a piece of reportage that describes a match that took place during the summer of 1994 between the late Marion Tinsley, the best checkers player in the history of the game, and Chinook, a computer program written by a team headed by computer scientist Jonathan Schaeffer. This piece was eventually published in the American Chess Journal.

Dimers and Dominoes (first written back in 1993; last revised October 5, 2000) is an essay I wrote a few years ago to give an introduction to the enumeration of domino tilings of finite regions by consideration of the most natural class of shapes, namely rectangles.

Last updated July 2, 2010