David E Speyer

Contact Information:


E-mail: speyer@post.harvard.edu or speyer@math.mit.edu
The former is a forwarding address that currently forwards to the latter. The former will always be correct, but has problems with large files. The latter is my current e-mail address at MIT.

Office: In MIT speak, 2-332. In more ordinary language, that means room 2-332, which is on floor 3 of building 2.

Phone (Cell): (734)-255-8610

Mail (Work):
David E Speyer
Department of Mathematics, Room 2-332
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139 USA
Mail (Home):
David E Speyer
266 Chestnut Hill Avenue
Brighton, MA
02135-5946
Map

My Name:
My last name is pronounced "spire", like the top of a church. But I'll answer to "Sp-vowel-r!" or to "David!". For the curious, it is derived from the city of Speyer, Germany, although my friend Aaron tells me it could also be Yiddish for "pistol".

About Me:

I am a visiting scholar in the department of mathematics at MIT. I am funded by a Five Year Clay Research Fellowship.

I recently graduated from UC Berkeley, where I was a student of Bernd Sturmfels. My thesis is on tropical geometry, an approach to turning algebraic geometry problems into polyhedral geometry. Before coming to Berkeley, I was an undergraduate at Harvard. While there, I worked for Jim Propp's research group REACH and wrote an undergraduate thesis on the Eichler-Shimura correspondence under William Stein. I spent the rest of my time doing technical theater, hanging out with science fiction fans and working on Les Phys -- the physics musical! I spent four years as a counselor at PROMYS, a number theory program for high school students, and highly endorse it either as a place to go learn or to go work. I spent my own high school summers at MOP , which I found great but works better for some people than for others. I went to High School at Choate Rosemary Hall and to Middle School at Talcott Mountain Academy. If you are a young nerd in Connecticut, looking for a middle school or after school program, I highly recommend Talcott.

I enjoy algebraic problems with a combinatorial flavor. If you started out with a well motivated algebraic question but wound up with lots of little complicated pictures, I probably want to hear about it. Some topics I can usually be relied upon to think about: tropical geometry, cluster algebras, flag manifolds and other geometry of Lie Groups, interesting degenerations of algebraic structures, exact results and asymptopics of perfect matchings ( eg Arctic Circle phenomena). I also know a reasonable amount of Number Theory and enjoy talking about it, although as yet this is not a research interest.

Along with a number of my fellow Berkeley alumnae, I blog at The Secret Blogging Seminar.

I, together with Lauren Williams and Gregg Musiker, am organizing the MIT Combinatorics Seminar for the Fall of 2008. Please contact any of us if you would like to speak.

I was part of a group of 60 or so people who wrote the 2006 MIT Mystery Hunt. All of our puzzles are now archived online, along with a web script that will check your answers and reasonably complete solutions. I wrote Connect Four (along with Noah Snyder), Tea for Two and Two for Tea (with Aaron Dinkin), Just a Jump to Left, The Scrambler, Wry, Ergo, Dead (with Noah Snyder), All Work and No Play Makes Jack a Dull Boy (with Noah Snyder) and Drop Everything. I also wrote the Moscow Meta (puzzle here, solution here), the Buenos Aires Ante and the McMurdo Station Ante. Ante puzzles are concealed among all of the other data for the round they are hidden in and their answers are the identity of a SPIES agent and the location of the next round. Our hunt was shorter than we expected, but most of the people I talked to seemed to have had a lot of fun solving it. And I have plenty of puzzle ideas left for next time (knock wood)...

In my best news, I am now married to Lark-Aeryn Speyer, perviously known as Erin Ruth Larkspur, the lovely lady pictured above. We will be adding photos of the wedding to this page.

Papers:

All of my papers that are in a reasonably polished state can be found here on the arXiv . (With the exception of my first paper, "Every tree is 3-equitable" with Zsuzsanna Szansiszlo and my thesis, which will be broken into several papers for publication.) The arXiv version is often not completely final -- some papers have minor improvements in the published version.

Here is a complete annotated listing of my papers as of June 24, 2008.

  • A non-crossing standard monomial theory with Kyle Petersen and Pavlo Pylyavskyy

    One of the most classical topics in combinatorial commutative 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 varieteis and realted spaces, and of LeClerc and Zelevinsky's weakly seperated sets.


  • Sortable elements in infinite Coxeter groups with Nathan Reading

    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, to appear.

    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 (in the simply-laced case) 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.


  • Uniformizing Tropical Curves I: Genus Zero and One

    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

    This paper returns to themes I was thinking about in 2002, when I wrote the first octahedron and cube recurrence 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 he 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.

    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
    JEMS, to appear.

    Let W be a Coxeter group of finite type and c a Coxeter element. In a series of papers (see 1, 2 and 3), Reading 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

    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 zero.

    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 Miller
    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 Larkspur
    New Britain Herald December 3, 2005 p. C8

    Erin and I announce the beginning of a collaboration.

  • Cyclically Orientable Graphs

    In Cluster 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.

  • Computing Tropical 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 0.2.

  • Tropical Geometry

    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.

    The final 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 original dissertation.

  • Tropical Linear Spaces
    SIAM Journal on Discrete Mathematics to appear
    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 with Nick Proudfoot
    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 complex.

  • Tropical Mathematics with Bernd Sturmfels

    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 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. 189-210

    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 tropicalization.

  • Horn's Problem, 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.

  • Reconstructing Trees 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.

  • The Tropical Grassmannian with Bernd Sturmfels
    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, to appear

    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.

  • Every tree is 3-equitable (link may require academic access) with Zsuzsanna Szansiszlo
    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.

    Software:


    I occasionally write Mathematica notebooks to aid in studying combinatorial problems. I ll use this section of my website to post notebooks that I think are of general interest and well enough commented to be useful to others.

  • SerParCore This note book lists the series-parallel matroids of given rank and number of elements. The number of such matroids is Sloane sequence A115594.

    I have some notebooks which compute random groves and enumerate groves in various settings. I'm not posting them right now because they are poorly commented and I think all of their functionality is subsumed by Gabriel Carroll's GrovePak software. If you think that you need something that GrovePak can't do, though, send me a note and I'll see if mine can.