All of my research papers that are in a reasonably polished state can be found here
on the arXiv. Some of the expository
snippets and very old material below, as well as my dissertation, are
Here is a complete annotated listing of my papers as of
August 27, 2017.
A Gröbner basis
for the graph of the reciprocal plane with Alex Fink and Alexander
We answer some commutative algebra questions which have bothered me
for a long time, regarding why the cohomology class used by June Huh and
Eric Katz is so similar to the K-theory class in my paper with
Nick Proudfoot. I viewed this as a warm up to study some analogous
questions relevant to my work with Alex Fink, but we did not make
progress on the harder questions. This paper was developed in a
working group at the Fields Institute Special Semester on Combinatoral
Algebraic Geometry; thank you very much to the Fields Institute and to
all the participants in the working group.
subvarieties pull back in almost all characteristics
of Commutative Algebra to appear.
Suppose you have an algebraic variety equipped with a Frobenius
splitting and you want to list all the compatibly split subvarieties.
I show that, with little harm, you can normalize the ambient variety
first. This is convenient, because we often want to talk about
divisors and valuations in this context. This is a question Allen
Knutson asked me ages ago and I finally got around to publishing it.
Some sums over
Algebra and Number Theory to appear
I prove a bunch of conjectures of Dinesh Thakur. As an example of the sort of result, if you sum up 1/(P+1), where P
runs over all irreducible polynomial in F2[T] and the sum
is consdered in the T-1-adic topology, you get 0. This started as a Polymath problem.
The Growth Rate of Tri-Colored Sum-Free Sets with Robert Kleinberg and Will Sawin
Discrete Analysis to appear
My first extremal combinatorics paper! This is one of the papers pursuing the exciting new tools for bounding the size of sets in (Z/p)n with no 3-term arithmetic progressions.
Our result is one of the first to achieve a matching of upper and lower bounds. Our constructions of colored sum free sets have the same exponential growth rate as our upper bounds for
The twist for positroid
varieties with Greg Muller.
Proceedings of the LMS to appear
We fill in the last missing gap in Postnikov's positroid varieties paper -- discovering the analogue of the chamber ansatz and thus showing how to invert the boundary measurement map.
This has a number of important consequences. We show that the image of the boundary measure map is open immersed torus, and that the domain where any set of Plucker cluster variables
is nonzero is another torus — and they are not the same one! This involves lots of pretty combinatorics. We tried to write this to be a helpful reference for people who have ben
confused by how key results are spread across the literature, and I have had a number of grad students tell me they found this paper a great place to start learning the positroid story.
Give it a try!
Cohomology of cluster varieties. I. Locally acyclic case with Thomas Lam.
We work to describe the mixed Hodge structure on cluster varieties. The main results (with some hypotheses omitted): The mixed Hodge structure is entirely of Tate type and split over the
rationals, and we can prove the "curious Lefschetz property". There will be at least one major sequel to this, with explicit combinatorial rules in the acyclic setting.
Variations on a theme of Kasteleyn, with application to the totally nonnegative Grassmannian.
Electronic Journal of Combinatorics, Volume 23, Issue 2 (2016), Paper #P2.24
I provide a quick proof of Kasteleyn's theorem that the adjacency matrix of a planar graph can be decorated with signs so that its determinant computes the number of perfect matchings of the graph.
Then I show how this result and several related ones are key to Postnikov's parametrization of positroid varieties.
A Cambrian framework for
the oriented cycle with Nathan Reading.
Electronic Journal of Combinatorics, Volume 22, Issue 4 (2015), Paper #P4.46
Until we develop something new, this is the last of Nathan and my
papers on frameworks. We explain how to merge the theory of affine
frameworks from our previous paper, and the theory of sortable
elements for quivers with cycles that we developed several years
prior. It was one of the real pleasures of this project to see our old
definitions prove right. Sadly, I currently think we have reached the
limits of these methods.
determinantal representations of hyperbolic curves with Daniel
Sinn and Cynthia Vinzant.
International Journal of Algebra and Computation, Volume 25, Issue 08, December 2015.
We explain how to take a degree n plane curve and write it as a
determinant of an n by n Hermitian matrix of linear
forms with specified signature. Past work has focused on determinantal
representations, which are much harder. This work is accompanied by
Mathematica code, which, despite our lack of coding skill, works pretty well.
Cambrian frameworks for
cluster algebras of affine type with Nathan Reading.
Transactions of the AMS
Nathan and I explain how our theory works in the affine acyclic
case. It's very pretty!
scattering amplitudes in 4d N=4 SYM and 3d ABJM, with Henriette
Elvang, Yu-tin Huang, Cynthia Keeler, Thomas Lam, Timothy
M. Olson and Samuel B. Roland
Journal of High Energy Physics,
December 2014, 2014:181.
My first physics paper! We rewrite some old computations in scattering
theory and show to use the same method for some new ones. I much admit
that there are parts of this paper I understand very well and other
parts which I understand very little.
Links in the complex of of weakly separated collections, with Suho Oh
Journal of Combinatorics, to appear.
We show that, if we fix a weakly separated collection B, the set of all maximal weakly separated collections containing B is connected under mutation operations.
This is a start to the task of understanding the topology of the simplicial complex of weakly separated collections, a task which has also been tackled by Hess and Hirsch.
By using the technology from our earlier paper with Alex Postnikov, the proof becomes incredibly short; in my opinion, even in the case where B is empty, which was done by Postnikov, our argument is much simpler.
Cluster Algebras of Grassmannians are Locally Acyclic with Greg Muller
Proceedings of the AMS Volume 144, Number 8, August 2016, p. 3267-3281.
We show that cluster algebras of positroid varieties are locally acyclic, a condition introduced by Greg which makes them much easier to analyze. At the time we wrote the paper, it was not quite know that
positroid varieties had cluster structure, but that has
since been remedied by Leclerc.
An Infinitely Generated Upper Cluster Algebra
As the title says, I construct an infinitely generated upper cluster algebra, answering a question left open in Cluster Algebras III.
After writing this, I realized that a similar construction appeared in an early arXiv version of Birational Geometry of Cluster Algebras, by Gross, Hacking and Keel.
However, that construction didn't quite work and mine does.
Schubert problems with respect to osculating flags of stable rational curves
Algebraic Geometry Volume 1, Issue 1 (January 2014) pp. 14 — 45.
Given a point z on the projective line, the osculating flag at z is spanned succesively by (1,z,z2, ...), (0,1,2z, ...), (0,0,2,...), ...
Schubert problems with respect to osculating flags have a rich classical theory, and have come again to modern attention due to the proof of the Shapiro-Shapiro conjecture
by Mukhin, Tarasov and Varchenko.
We develop a language to describe what happens when the points collide; describing solutions to Schubert problems in families over the space of stable genus zero curves with
n marked points.
In particular, the topology of the real solutions to these problems is described by classical combinatorics of growth diagrams.
Grassmannians and their rays with Sven
Herrmann and Michael
Forum Mathematicum 26 (2014), no. 6, 1853
We develop tools to describe higher dimensional Dressians (a
combinatorial object a bit larger than the tropical Grassmannian), and
in particular to describe their rays. In particular, we describe a
construction for turning subdivisions of a product of two simplices
into points of the Dressian. This bridges the gap between the setup in
the "tropical convexity" and "tropical rank of a matrix" papers and in
the "tropical Grassmannian" papers.
My involvement with this paper is a little odd; there was already a
version written and on the arXiv with the other two authors, and I
pointed out some improvements that lead to me being added as a
co-author. As a result, I understand sections 2, 3 and 5 very well,
and know very little about the computational details in section 6.
Acyclic cluster algebras
revisited with Hugh
In Algebras, Quivers and Representations -- the Abel symposium 2011, ed. Buan, Reiten and Solberg, Springer-Verlag, (2013) pp. 275 — 298.
In my frameworks paper with Nathan Reading, we explain that the best
combinatorial data with which to describe a cluster algebra is to
assign an n-tuple of roots to each cluster, obeying a simple
recursion. Hugh and I show that we can extract this n-tuple of
roots as the dimension vectors of noncrossing exceptional sequences,
and we give a clean combinatorial description of such sequences of roots.
Positroid varieties: juggling and geometry with Allen Knutson and Thomas Lam.
Compositio Mathematica 149, Issue 10, (October 2013), pp. 1710--1752
We study Postnikov's stratification of the totally nonnegative Grassmannian from the persepcitve of algebraic geometry. We classify singularities, compute cohomology classes, give equations and
describe Groebner degenerations. There are connections to the
mathematics of juggling and to Stanley symmetric functions.
This material earlier appeared in our 2009 preprint, together with
some lengthy combinatorial arguments and a number of results on
projected Richardson varieties. The former are removed and replaced by
better proofs; the latter now appear in a separate paper.
for cluster algebras, with Nathan Reading.
International Mathematics Research Notices (2016), Issue 1 pp. 109-173.
The next paper in Nathan and my series on describing combinatorics of
cluster algebras in terms of Coxeter combinatorics. This is the big
one — we finally prove that the combiantorial objects we
constructed do match of with the cluster algebra. We also spend a lot
of time building general technology to describe combinatorial models
for cluster algebras; we hope this will streamline future papers both
by us and by others.
The next paper will be on some special combinatorial constructions
that occur in affine type.
Weak Separation and
Plabic Graphs with Suho Oh and Alex Postnikov.
Proc. London Math. Soc. (3) 110 (2015), no. 3, 721
– 754 .
We explain how, given a maximal weakly separated collection, to construct a
plabic graph. (And thus to construct an alternating strand diagram,
and any of the other objects from Postnikov's massive
work.) This closes a gap in the description of the cluster theory
of the Grassmannian which has been open since Josh Scott's thesis 1 2 ten years ago. In
particular, we now know that every cluster consisting of Plucker
coordinates comes from the plabic graph technology; and we have now
proven Scott's purity and connectedness conjectures.
This paper has been a long time in production, and incorporates
discussions I've had with Andre Henriques and Dylan Thurston. It also
has heavy overlap with work of Danilov, Karzanov and
Koshevoy; see our paper for a discussion of how our work is
related to theirs.
Projections of Richardson
Varieties with Allen Knutson and Thomas Lam.
Crelle's Journal, 687 (2014) pp.133 — 157
This paper takes those results from "Positroid Varieties I" which are true
in general type and gives uniform, cleaner proofs of them. There is a
second paper which focuses on the combinatorial aspects which are unique
Real Numbers by Fractions I and Approximating
Real Numbers by Fractions II
Girl's Angle, 4(2) December 2010 and 4(3)
January 2011, p. 6 — 8 and p. 5 — 7.
Expository pieces on approximation, written for high school or advanced middle school students.
matroids and equivariant localization, with Alex Fink.
Journal 161 no. 14 (2012), 2699 — 2723.
In my previous paper "A Matroid Invariant via the
K-theory of the Grassmannian", I explained how to associate a
class in K-theory to any matroid. In this paper we explain how
to relate the Tutte invariant to this construction, make several of
the constructions from that paper purely combinatorial, and give
cleaner proofs of several of the results from that paper.
Looping of the numbers game
and the alcoved hypercube with Qëndrim R. Gashi
Journal of Combinatorial Theory: Series A,
119 Issue 3, (April 2012),
pp. 713 — 730 .
Some cute problems about affine reflection groups, motivated by work
of Qëndrim on the Kottwitz-Rappaport conjecture.
Sortable elements for
quivers with cycles with Nathan Reading
Electronic Journal of Combinatorics, 17(1) (2010) #R90
We explain how to extend our Cambrian technology to the case of cycles, which is important for many applications to cluster algebras. While the definitions seem too simple to work, they do, due to
some nontrivial results about Bruhat order.
Positroid varieties I: juggling and geometry with Allen Knutson and Thomas Lam.
We have split this paper into two papers 1 2, with better results and
proofs in both. You probably don't want to read this one.
A non-crossing standard
monomial theory with Kyle Petersen and Pavlo Pylyavskyy
Journal of Algebra, 324 (2010), 951 — 969
One of the most classical topics in combinatorial commutative algebra is the standard monomial basis for the flag variety. This is a basis for the Plucker algebra indexed by semi-standard Young tableaux,
useful for computations in representation theory and algebraic geometry. Pavlo introduced objects he calls non-nesting tableaux which are a "non-nesting"
version of semi-standard Young tableaux. In this paper, we explain the corresponding commutative algebra. We hope our work will be useful in the investigation of the cluster algebra structures on flag
varieties and realted spaces, and of LeClerc and Zelevinsky's weakly seperated sets.
Sortable elements in
infinite Coxeter groups with Nathan Reading
Transactions of the AMS, 363 (2011), 699 — 761
This is the first of a series of papers where Nathan and I take connections between Coxeter groups and cluster algebras that have been proven in finite type and generalize them to all types. This paper is purely on the Coxeter combinatorics side. We prove that Nathan's definitions of sortable elements, and the Cambrian lattice, work with almost no modification in any Coxeter group. Among our key techinical tools are (1) the use of a skew symmetric form on the root space to impose pattern avoidance conditions, giving us a type-free description of the "aligned" condition in Nathan's earlier work, and (2) an explicit description of normal vectors to any cone in the Cambrian fan, in terms of "forced and unforced skips".
Powers of Coxeter elements in infinite groups are reduced
Proceedings of the AMS, 137 (2009), 1295 — 1302.
Let W be an infinite, irreducible Coxeter group, with simple generators s1, s2, ..., sn. I show that the word s1s2 ... sns1s2 ... sn...s1s2 ... sn is reduced, for any number of repetitions of s1s2 ... sn. This answers a question of Fomin and Zelevinsky, and provides an excellent opportunity to show off a quick application of technology which Nathan and I use in our much longer paper.
I want to emphasize that the main result of this paper was obtained earlier by Kleiner and Pelley. My argument is inspired by theirs, but it removes the use of quiver theory and simplifies the argument on several other points.
Parametrizing Tropical Curves I: Genus Zero and One
Algebra and Number Theory, Volume 8, Number 4, (2014), pp. 963-998
This is the first of what will be a series of two papers explaining how to use classical parameterizations of algebraic curves to write down curves with specified tropicalizations. In this paper, we deal with genus zero and one curves. The genus zero case, in particular, is very concrete. This material is drawn from the final chapter of my thesis.
The Multidimensional Cube
Recurrence with Andre Henriques
Advances in Mathematics 223 (2010), no. 3, 1107-1136
This paper returns to themes I was thinking about in 2002, when I
wrote the first octahedron and
papers. In those paper, we studied three dimensional recurrences,
whose initial conditions live on a two dimensional surface. Since
then, Andre Henriques and Joel Kamnitzer have taken the octahedron
recurrence and generalized it to a recurrence in any number of
dimensions, whose initial conditions still live on a two dimensional
lattice. This recurrence computes the associator and commutator in the category of gln-crystals. It is also related to Fock and Goncharov's higher Teichmuller spaces, to a number of classical type A varieties, and to the Toda lattice heirarchy.
In this paper, Andre and I introduce a recurrence which relates to the
cube recurrence as his and Joel's work relate to the octahedron
recurrence. We show that this recurrence has the same combinatorial
properties as the cube recurrence — well definedness,
propogation of inequalities, and Laurentness. A special case gives a
coordinatization of the isotropic grassmannian. I don't know what the underlying representation theory, or the underlying algebraic geometry, is. I also don't know how to extend Gabriel and my grove technology, Andre, Dylan Thurston and I are working on this.
Matching polytopes, toric geometry, and the non-negative part of the Grassmannian with Alex Postnikov and Lauren Williams.
Journal of Algebriac Combinatorics, 30 (2009), no. 2, 173-191
We take Postnikov's positroid varieties and describe how to parameterize them by toric varieties. In particular, we can describe the totally nonnegative part of these varieties as a (toplogical) quotient of a polytope. The underlying combinatorics involves matching polytopes.
Cambrian Fans with Nathan Reading
Journal of the European Mathematical Society (JEMS), 11 (2009), no. 2, 407--447
Let W be a Coxeter group of finite type and c a Coxeter element. In a
series of papers (see
introduced an equivalence relation on W called
the c-Cambrian congruence whose equivalence classes are in
natural bjection with clusters of the corresponding Cluster
Algebra. Combining cones of the Coxeter fan corresponding to
equivalent elements of W yields a coarsening of the Coxeter fan
which we term the c-Cambrian fan.
In this paper, we show that the c-Cambrian fan is a simplicial
fan whose combinatorics matches the cluster complex. We dispose of
almost all of the conjectures remaining from Reading's earlier papers
and establish several connections between the Cambrian fan and Cluster
Algebras — in particular, the g-vectors and quasi-Cartan
companions occur naturally in the Cambrian setting. Our proofs depend
on carefully checking the compatibility of a large number of
bijections when the Coxeter element c is changed in a manner
related to reversing a source in a quiver to a sink. Thankfully, now that these compatibilities have been checked, they will be available for future use.
Nathan and I are engaged in a long term research project to extend the results of this paper to infinite Coxeter groups. Our first paper on this subject is Sortable elements in infinite Coxeter groups.
A Matroid Invariant via the K-theory of the Grassmannian
Advances in Mathematics, 221 (2009), no. 3, 882-913
Let x be a point in the grassmannian G(d,n) and
let T be the n-1 dimensional torus which acts
on G(d,n). Take the closure of the T-orbit through x;
the class of the structure sheaf of thish subvariety in
the K-theory of G(d,n) depends only on the matroid
of x. By some standard operations in K-theory, I
associate a polynomial to x which behaves nicely under every
standard matoid operation. Using this invariant, I prove
the f-vector conjecture from
Tropical Linear Spaces
when all of the matrods involved are realizable in characteristic
I still don't have a great combinatorial interpretation of this
polynomial -- it imposes very strong restrictions on decompositions of
matroid polytopes into smaller matroid polytopes. If anyone recognizes what this guy is, please let me know!
A Kleiman-Beritini Theorem
for sheaf tensor products with Ezra
Journal of Algebraic Geometry, 7 (2008), 335-340
Let X be a variety with a transitive action by an
algebraic group G and let E and F be coherent sheaves
on X. We prove that, for elements g in a
dense open subset of G, the sheaf Tori(E, g F)
vanishes for all i > 0. This says that, when performing intersections in K-theory, we may
take a generic translate and then forget about higher Tor's. This
is like the Kleiman-Bertini theorem, which says the same for intersections
in Chow theory in characteristic zero.
Engagement Announcement with Erin
New Britain Herald December 3, 2005 p. C8
Erin and I announce the beginning of a collaboration. Possibly
confusing point: Erin has since
changed her name to Lark-Aeryn Speyer
Cyclically Orientable Graphs
Algebras II, Fomin and Zelevinsky classified cluster algebras of
finite type. Their classification did not yield an effective way of
deterimning whether a given cluster algebra was of finite type. In Cluster Algebras of
Finite Type and Symmetrizable Matrices, Barot, Geiss and
Zelevinsky give an algorithm for performing this test, one step of
which involves testing whether a graph is "cyclically orientable";
i.e., whether it has an orientation in which every cycle which
occurs as an induced subgraph is cyclically oriented. In this paper, I
give a simple and rapid algorithm for solving this graph theoretic
problem and show that all cyclically orientable graphs are essentially
built by gluing together cycles along single edges.
Shortly after writing this, I learned that my main results had
been obtained independently and several months earlier by Vladimir
Gurvich of Rutgers, see his preprint Cyclically
Orientable Graphs. With Gurvich's gracious agreement, I am posting my
note so that people will be aware of the results; I completely acknowledge
that he has several months of priority.
Varieties with Tristram Bogart, Anders
Jensen, Bernd Sturmfels and Rekha Thomas
Journal for Symbolic Computation Volume 42 , Issue 1-2 (January 2007)
Pages 54-73 .
We describe an algorithm for computing tropical varieties that is roughly
a thousand times faster on high codimension examples than the naive
approach via Groebner fans. There is some non-trivial math in the proof of
correctness -- we show that the tropicalization of a prime variety is
connected in codimension one. We have implemented our algorithm as an
extension to Gfan; it is included with Gfan
This is my dissertation, which attempts to do the ground work to
establish tropicalization as a major tool of algebraic geometry. There
are four major sections (plus a historical introduction.) The first
section tries to develop general tools, including establishing the
equivalence of several notions of tropicalization and describing the
tropical degeneration and compactification -- these are schemes
assosciated to a subvariety of a torus over a nonarchimedean
field. The combinatorics of these schemes are indexed by a polyhedral
complex whose underlying point set is the tropicalization. For further developments on this subject, consult David Helm and Eric Katz's paper Monodromy Filtrations and the Topology of Tropical Varieties.
The second section and third section respectively
cover the material in my papers The Tropical Grassmannian and
Tropical Linear Spaces below, rewritten to emphasize their
connections to the other material of the dissertation.
section studies the probleming of recognizing which graphs embedded in
Rn occur as tropicalizations of curves embedded in the
torus. It turns out that Mumford's techniques of nonarchimedean
uniformization are admirably suited to this problem. The curve
material, with a few technical hypotheses removed, will appear in Uniformizing Tropical Curves I: Genus Zero and One and a forthcoming sequel.
A few minor changes have been made to this file as compared to the
Tropical Linear Spaces
SIAM Journal of Discrete Mathematics Volume 22, Issue 4, pp. 1527-1558 (2008)
I define tropical analogues of the notion of "linear space" and
"Plucker coordinates" and basic constructions for working with
them. The arXiv version of this paper is an exhaustive introduction that tells almost everything I have figured out. The most interesting aspect of the
paper is the f-vector conjecture -- I conjecture what the maximal
possible f-vector of a tropical linear space should be and provide a
great deal of evidence for this claim. The published version is stripped down, and focuses more purely on this aspect of the subject. For further progress on the f-vector conjecture, see A Matroid Invariant via the K-theory of the Grassmannian
Although it can be read independently, this paper is naturally a
sequel to my paper The
Tropical Grassmannian below.
A Broken Circuit Ring
Beiträge zur Algebra und Geometrie Vol. 47, No. 1, pp. 161-166 (2006)
Given a linear subspace of affine space, we study the ring of rational
functions on the linear space generated by the reciprocals of the
coordinate functions. This ring has been studied previously by Terao
and others. We find a universal Groebner basis and show that the ring
degenerates to the Stanley-Reisner ring of the broken circuit
Tropical Mathematics with Bernd Sturmfels
Mathematics Magazine, 82 (2009), no. 3, 163-173
An elementary introduction to tropical mathematics, expanding on my co-author's Clay Public Lecture at Park City Math Institute 2004 (IAS/PCMI)
An arctic circle theorem for groves with Kyle Petersen
Presented at Formal Power Series and Algebraic Combinatorics (FPSAC) 2004.
Journal of Combinatorial Theory: Series A 111 Issue 1
(2005), p. 137-164
Proves that a randomly chosen grove (introduced in my paper with
Gabriel Carroll below) is "frozen" outside a certain circle. This is
analogous to results on random tilings of Aztec Diamonds and random
Alternating Sign Matrices.
The tropical totally positive Grassmannian with Lauren Williams
Journal of Algebraic Combinatorics 22 no. 2 (2005), p.
We study the tropical analogue of the totally positive cell in the
Grassmannian, introduced by Lusztig and studied in detail by Postnikov
and others. We discover a tight connection to the combinatorics of
cluster algebras and conjecture a general connection between the
cluster complex of a cluster algebra and its totally positive
Vinnikov Curves and Hives
Duke Journal of Mathematics 127 no. 3 (2005), p. 395-428
Horn's Problem asks to characterize the possible eigenvalues of a
triples of Hermitian matrices with sum 0. Allen Knutson and
Terry Tao gave an answer in terms of combinatorial objects called
honeycombs which look like tropical curves. I explain this
phenomenon by showing that Horn's problem is equivalent to studying
the possible intersections of plane curves with prescribed topology
with the coordinate axes and then showing that the tropical version of
this criterion recovers the results of Knutson and Tao.
Note: The above linked paper does not fully spell out the link
between honeycombs and eigenvalues; the chain of logic is as follows:
by appendix I of the above linked
paper, honeycombs are equivalent to Berenstein-Zelevinsky
patterns, which compute tensor product multiplicities, which are
related to eigenvalue computations by the Kirwan-Ness theorem. Allen Knutson
has a good survey paper explaining the last step.
from Subtree Weights with Lior Pachter
Applied Mathematical Letters, 17 (2004), p. 615-621
In computational phylogenetics, the problem of reconstructing a metric
tree from the distances between its leaves frequently arises. We study
the similar problem of reconstructing a tree from the total lengths of
the subtrees spanned by k of its leaves.
Grassmannian with Bernd
Advances in Geometry, 4 (2004), no. 3, p. 389-411
We study the tropicalization of the Grassmannian in its standard
Plucker emebedding. We show that its points parameterize
tropicalizations of linear spaces, give a complete description of the
case of G(2,n) and do some computations of larger cases.
I have done a good deal more work on the properties and classification
of tropicalizations of linear spaces, see my paper Tropical Linear Spaces above.
The Cube Recurrence with Gabriel Carroll
Electronic Journal of Combinatorics, 11 (2004) #R73
This paper is similar to the octahedron recurrence paper below, but with
applications to Propp's cube recurrence, a peculiar recurrence that
has Laurentness and positivity properties similar to the octahedron
recurrence but has no known relation to cluster algebras. The relevant
combinatorial objects are no longer perfect matchings but "groves",
certain highly symmetric forests that deserve further study. This paper was primarily written in Propp's REACH program.
Perfect Matchings and the Octahedron Recurrence
Journal of Algebraic Combinatorics 25, no. 3, May 2007
The octahedron recurrence is a certain recurrence whose entries are
indexed by a three dimensional lattice; the recurrence grows from a
two dimensional surface of initial conditions. It follows from Fomin
and Zelevinski's results on Cluster Algebras that all of the terms of
the recurrence are Laurent polynomials in the initial values. I show
that every term in these polynomials has coefficient 1 by establishing
a bijection between these monomials and the perfect matchings of
certain graphs. Special cases include formulas for Somos-4 and Somos-5
and for the number of perfect matchings of many families of
graphs. This paper is based on research done in Propp's REACH program.
A Reciprocity Sequence for Perfect
Matchings of Linearly Growing Graphs
This is a note that I wrote up back when I was an undergrad on how to
use transfer matrices to prove results like Propp's reciprocity
principle for domino tilings. Since then, a few people have cited
it as "D. Speyer, unpublished note on transfer matrices", so I figured I should
at least host a copy on my website. Rereading it today, I see a number
of typos but no mathematical errors. I am puzzled as to why I said
that these results were a special case of Propp's; it seems to me that
the reverse is true.
If anyone has the TeX original, I'd love it if they'd send me a copy
so that I could fix the typos without retyping everything.
Every tree is 3-equitable (link may require academic
access) with Zsuzsanna
Discrete Mathematics, 220 (2000) 283-289
Let G be a graph whose vertices are labelled with the numbers
0, 1, ... i. Label each edge with the absolute value of the difference
between its endpoints. A labelling is called equitable if, for any two
numbers a and b from 0 to i, the number of vertices with label a
differs by at most one from the number with label b and a similar
property holds for the number of edges with each label. It is
conjectured that every tree has an equitable labelling for every i. We
prove this conjecture for i=2.