Publications of Jeremy L. Martin

This is an attempt to explain (at least some of) my research in a way that is accessible to intelligent people who are not, or perhaps not yet, professional mathematicians. I've tried to use as little jargon as possible. I'd be delighted to hear from you if you find something here that you either (a) think is interesting or (b) don't understand (so I can clarify it). If you're looking for more technical details, you should probably visit my main publications page.


Simplicial matrix-tree theorems (with Art Duval and Caroline Klivans)
Transactions of the American Mathematical Society 361 (2009), no. 11, 6073--6114.
Cellular spanning trees and Laplacians of cubical complexes (with Art M. Duval and Caroline J. Klivans)
Advances in Applied Mathematics, to appear.

Graphs are neat, but simplicial complexes are neater: instead of restricting yourself to vertices and edges, why not allow yourself triangles, tetrahedra, and higher-dimensional pieces? Many facts about graphs can be generalized to simplicial complexes. Art, Carly and I collaborated on defining what it means for one simplicial complex to be a spanning tree of another one, and generalizing the Matrix-Tree Theorem to count such simplicial spanning trees algebraically. (Our definition and formula are based on an idea originally due to Gil Kalai, and in a slightly different form by Ethan Bolker.) We applied this general result to count the simplicial spanning trees of a particularly nice kind of simplicial complexes called shifted complexes; our result ends up generalizing and unifying several previously known results. Having done that for a while, we started looking at spanning trees of even more general combinatorial-topological objects known as cell complexes. Many of the results about simplicial complexes carry over naturally to the setting of cell complexes, and there turn out to be nice formulas (at least, we think they're nice) for counting spanning trees of cubes of various dimensions.


On distinguishing trees by their chromatic symmetric functions (with Matthew Morin and Jennifer D. Wagner)
Journal of Combinatorial Theory, Series A 115 (2008), 237--253.

A tree is a bunch of points ("vertices") held together by as few lines ("edges") as possible (see also the paper "Factorizations of some spanning tree enumerators" below). How many ways are there to color the vertices of a tree using k different colors so that no two adjacent vertices receive the same color? The answer to this question is well known; it's k(kn-1), where n is the number of vertices. Remarkably, it doesn't depend on which particular tree you pick, just how many vertices it has (and there are a lot of ways to build a tree on n vertices; for example, there are 106 different 10-vertex trees).

However, Richard Stanley came up with a more detailed way to count colorings, called the chromatic symmetric function (essentially, keeping track of how many times each color is used) which preserves much more information about the tree. No one knows whether the chromatic symmetric functions of different trees have to be different. This problem seems to be very hard, but Matthew, Jennifer and I were able to make some progress on it. What we proved is that you can recover a lot of information about a tree from its chromatic symmetric function. For example, you can tell how many vertices are connected to i other vertices for every possible value of i; how many pairs of vertices are j steps apart for every possible value of j; and much more.

In addition, for certain very nice kinds of trees (with catchy names like "spiders" and "caterpillars") the chromatic symmetric function really does determine the tree uniquely. One possible application of all this might be in biology or chemistry, of all things; trees arise from the atomic and molecular structure of things like hydrocarbons and proteins.


Harmonic algebraic curves and noncrossing partitions (with David Savitt and Ted Singer)
Discrete and Computational Geometry 37, no. 2 (2007), 267--286.

A famous fact called the Fundamental Theorem of Algebra states that every polynomial has as many roots as its degree: for instance, there are five real numbers x that satisfy x5+4x-1=0. We don't necessarily know how to find them exactly, but they're out there somewhere. Of course, they might be complex numbers instead of real numbers, but we don't mind that so much. Gauss first proved this theorem in 1799, using a beautiful geometric argument that involved drawing two curves and counting the points where the curves meet. Dave, Ted and I got interested in classifying these curves (which end up looking a lot like the lines on a basketball) more precisely. We ended up showing that any possible basketball does in fact occur for infinitely many polynomials. We'd like to know what the basketball tells you about a polynomial and its roots; we understand the quadratic case (polynomials like x2+4x-1) pretty well, but we don't yet know what information the basketball provides in degrees greater than 2.


The Mathieu group M12 and the M13 game (with Noam D. Elkies and John H. Conway)
Experimental Mathematics 15, no. 2 (2006), 223--236.

Remember the 15-puzzle? It's made of 15 little squares numbered from 1 to 15, placed in a 4x4 grid with one square left empty. The object is to unscramble the numbers.

8 5 10 2
13 7 11
14 6 4 9
12 15 1 3
---->
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

Actually, I lied. It's impossible to unscramble the grid on the left. It turns out that exactly half of all possible scrambled grids can't be unscrambled (in fact, if you swap any two numbers while leaving the others alone, you will toggle the unscrambleability of the grid). The algebraic object behind this phenomenon is something called the alternating group. (By the way, this puzzle was all the rage in about 1880. Famous puzzle master Sam Loyd claimed to have invented it, although this may be an urban legend.)

John Conway had the idea of constructing an analogous puzzle by replacing the 4x4 grid with something called the projective plane of order three, which has thirteen instead of sixteen spots. Instead of the alternating group, the underlying algebraic object controlling this puzzle is something called the Mathieu group. This group is a bit subtle to describe, but Conway's idea gives a more concrete description of it. Noam Elkies, my undergraduate advisor at Harvard, told me about Conway's idea. In my undergraduate thesis, I worked out some of the details of Conway's construction on my own, and used the puzzle as a means to look at the structure of the Mathieu group.


Rigidity theory for matroids (with Mike Develin and Victor Reiner)
Commentarii Mathematici Helvetici 82 (2007), 197--233.


Random geometric graph diameter in the unit ball (with Robert B. Ellis and Catherine Yan)
Algorithmica 47, no. 4 (2007), 421--438.

Throw a bunch of darts at a dartboard. Now tie a string between any two darts that are within an inch of each other. What is the chance that an ant walking along the string bridges can move from any dart to any other dart, and how many bridges might the ant have to cross? (Who cares, you ask? Well, the same model applies whenever you want to study connections between objects in random locations -- such as cell phone networks or GPS systems, or the spread of disease between trees in a forest.) The answer clearly depends on how many darts there are and how big the dartboard is. My coauthors Rob and Catherine, together with Xingde Jia, had looked at this problem previously; what we did in this paper was generalize their results to many more kinds of dartboards. First, the dartboard doesn't have to be circular: it can be a sphere, or a higher-dimensional version of a sphere. Second, you don't have to use the ordinary straight-line distance between two points. For example, you could require that you can only walk north/south and east/west, instead of walking between two points in a straight line, which would increase the distance between two points. (You can measure distance in even weirder ways if you want to.) Our results still apply under these alternate metrics.


Classification of Ding's Schubert varieties: finer rook equivalence (with Mike Develin and Victor Reiner)
Canadian Journal of Mathematics 59, no. 1 (2007), 36--62.


Cyclotomic and simplicial matroids (with Victor Reiner)
Israel Journal of Mathematics 150 (2005), 229--240.


The slopes determined by n points in the plane
Duke Mathematical Journal 131, no. 1 (2006), 119-165.

A perfect matching is a way to group an even number of kids into pairs of buddies. For example, if there are six kids, numbered 1 through 6 in order of age, then there are fifteen ways of pairing them up: e.g., {14, 26, 35} or {13, 25, 46}. How many buddy pairs will include two kids of consecutive ages?

3 pairs: {12, 34, 56}
2 pairs: {12, 36, 45}; {14, 23, 56}; {16, 23, 45}
1 pair: {12, 35, 46}; {15, 23, 46}; {15, 34, 26}; {16, 34, 25}; {13, 26, 45}; {13, 24, 56}
0 pairs: {13, 25, 46}; {13, 26, 45}; {14, 25, 36}; {15, 24, 36}; {16, 24, 35}

I've highlighted each pair of consecutive-age buddies in boldface, and organized the matchings by how many such pairs there are. Counting the numbers of matchings in each row gives the sequence of numbers (1, 3, 6, 5).

Astonishingly, perfect matchings turn out to be related to pictures of points and lines. Those polynomial relations I mentioned earlier, which constrain the directions of the line segments in a picture consisting of points and lines, turn out to have an incredibly nice algebraic structure. For the case of n points, every pair of which is connected by a line segment (making n(n-1)/2 segments in all), I was able to use these polynomials to calculate the size of the space of pictures. That size is encoded by something called its Hilbert series, and for the case of five points the Hilbert series turns out to be -- you guessed it! -- (1, 3, 6, 5). In general, the Hilbert series for n points corresponds to counting consecutive-age buddy pairs in the set of matchings on a group of 2n-4 kids. Simultaneously with the calculation of the Hilbert series, I showed that the space of all pictures is a Cohen-Macaulay variety: this means that while it has singularities (e.g., sharp corners instead of smooth points), it's not too singular --- in fact, it's nearly as nice as a smooth space in many ways.


On the topology of graph picture spaces
Advances in Mathematics 191, no. 2 (2005), 312--338.

What does that space of all point-line arrangements (see the paper "The slopes determined by n points in the plane" above) actually look like? It turns out that it has lots of holes of various sizes. The numbers and sizes of holes are recorded by something called the Poincaré series of the space, and what I was able to prove is that this is determined by something called the Tutte polynomial, which you can calculate if you know how many points you are starting with and which ones are connected with line segments. In summary, if you understand the combinatorics (i.e., you have a list of points and line segments), then you can deduce facts about topology (i.e., the holes). The formula for the Poincaré series works even if you allow pictures to be drawn in 3- or higher-dimensional space (instead of on a piece of paper).


Factorizations of some weighted spanning tree enumerators (with Victor Reiner)
Journal of Combinatorial Theory, Series A 104, no. 2 (2003), 287--300.

A square has four vertices and four edges. If you remove any one of the edges, the vertices are still connected by the remaining three edges, but if you remove a second edge, the vertices fall apart. So there are 4 different ways to connect the vertices with as few edges as possible.

A cube has 8 vertices and 12 edges. It turns out that the fewest number of edges you need to keep the vertices connected is seven, and there are 384 ways to do this. (Each of those ways is called a spanning tree of the cube.)

You can think of a cube as a three-dimensional version of a square. It turns out that you can construct an analogous object, called a hypercube, in any number of dimensions. An n-dimensional hypercube has 2n vertices, and the fewest number of edges you need to keep them connected is 2n-1. Using an algebraic tool called the Matrix-Tree Theorem, you can figure out a fairly nice formula for the number of spanning trees of a hypercube (depending, of course, on what n is).

Unfortunately, the formula says little or nothing about what those trees look like. Vic and I were trying to find a more concrete way of proving the formula. We didn't quite succeed (and the problem still remains unsolved), but we were able to add a lot of detail to the known formula. (An analogy: the old formula just gave the number of students at KU, while our results give information about how many are male, female, math majors, English majors, Kansans, Alaskans, etc.) In attacking this problem, we developed a technique (based on work of Christian Krattenthaler) which could be applied to structures other than hypercubes.


Geometry of graph varieties
Transactions of the American Mathematical Society 355 (2003), 4151-4169.

Take a piece of paper and draw four points. Now connect every two points with a line segment; you will need a total of six segments. (This whole setup is called a picture.) What can you say about the lengths of those line segments? It turns out that if you tell me any five of the lengths, I can figure out the sixth one, even if I have no idea where the points are. One way of rephrasing this is that the six lengths are mutually constrained; another way to look at it is that the structure of points and lines is "rigid" in a certain way. Oddly, if you tell me five of the directions instead of the lengths, then all of this remains true: I can figure out the direction of the sixth line even without knowing the locations of the points.

More generally, you can start by drawing any number of points, connecting some or all of them with line segments, and asking what the mutual constraints are on the lengths or the directions. I was able to figure out exactly what the direction constraints are for any such point-line picture by looking at the (very high-dimensional!) space of all such pictures. The constraints turn out to be a set of polynomial relations on the directions, which you can write down explicitly, and which are indeed intimately connected to the problem of whether the arrangement is rigid (i.e., if you build a physical model of the arrangement out of bars and ball joints, will it hold its shape like a triangle or be floppy like a square, which can be deformed into a rhombus?) One consequence of my results is the fact that every set of line segments have a length constraint if and only if they have a direction constraint. (This was already known, but this approach provides another proof; it never hurts to have more than one way to prove something.)


Ruling out (160,54,18) difference sets in some nonabelian groups (with Jason Alexander, Rajalakshmi Balasubramanian, Kimberly Monahan, Harriet Pollatsek, and Ashna Rubina Sen)
Journal of Combinatorial Designs 8, no. 4 (2000), 221--231.