Publications of Jeremy L. Martin

This page includes the full abstract of each paper. For bibliographic information alone, see the brief list. You can also look at descriptions of my papers in plain English.

Simplicial matrix-tree theorems (with Art M. Duval and Caroline J. Klivans)
Submitted for publication.

Abstract: We generalize the definition and enumeration of spanning trees from the setting of graphs to that of arbitrary-dimensional simplicial complexes Δ, extending an idea due to G. Kalai. We prove a simplicial version of the Matrix-Tree Theorem that counts simplicial spanning trees, weighted by the squares of the orders of their top-dimensional integral homology groups, in terms of the Laplacian matrix of Δ. As in the graphic case, one can obtain a more finely weighted generating function for simplicial spanning trees by assigning an indeterminate to each vertex of Δ and replacing the entries of the Laplacian with Laurent monomials. When Δ is a shifted complex, we give a combinatorial interpretation of the eigenvalues of its weighted Laplacian and prove that they determine its set of faces uniquely, generalizing known results about threshold graphs and unweighted Laplacian eigenvalues of shifted complexes.

Full paper (2/18/08): PDF | arXiv:0802.2576 Talk slides from KUMUNU VIII: PDF

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.

Abstract: Let T be an unrooted tree. The chromatic symmetric function X_T, introduced by Stanley, is a sum of monomial symmetric functions corresponding to proper colorings of T. The subtree polynomial S_T, first considered under a different name by Chaudhary and Gordon, is the bivariate generating function for subtrees of T by their numbers of edges and leaves. We prove that S_T = <Φ,X_T>, where <·,·> is the Hall inner product on symmetric functions and Φ is a certain symmetric function that does not depend on T. Thus the chromatic symmetric function is a stronger isomorphism invariant than the subtree polynomial. As a corollary, the path and degree sequences of a tree can be obtained from its chromatic symmetric function. As another application, we exhibit two infinite families of trees (spiders and some caterpillars), and one family of unicyclic graphs (squids) whose members are determined completely by their chromatic symmetric functions.

Full paper (6/8/07): PDF | PS | arXiv:math.CO/0609339
Talk slides from FPSAC 2006: PDF
Relevant Maple worksheets and data files, including computational evidence for two conjectures
Link to Li-Yang Tan's source code mentioned in the paper
Note: An extended abstract of this paper (under a different title, with one fewer author, and a weaker main result) appears in the FPSAC'06 proceedings. Please cite only the full version.

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

Abstract: Motivated by Gauss's first proof of the Fundamental Theorem of Algebra, we study the topology of harmonic algebraic curves. By the maximum principle, a harmonic curve has no ovals; its topology is determined by the combinatorial data of a noncrossing matching. Similarly, every complex polynomial gives rise to a related combinatorial object that we call a basketball, consisting of a pair of noncrossing matchings satisfying one additional constraint. We prove that every noncrossing matching arises from some harmonic curve, and deduce from this that every basketball arises from some polynomial.

Full paper (3/29/06): PDF | PS | arXiv:math.CO/0511248
Talk slides (12/6/05): PDF | PS
Related Maple worksheets

The Mathieu group M₁₂ and the M₁₃ game (with Noam D. Elkies and John H. Conway)
Experimental Mathematics 15, no. 2 (2006), 223--236.
See also my undergraduate thesis.

Abstract: We study a construction of the Mathieu group M₁₂ using a game reminiscent of Loyd's "15-puzzle." The elements of M₁₂ are realized as permutations on twelve of the thirteen points of the finite projective plane of order three. There is a natural extension to a "pseudogroup" M₁₃ acting on all thirteen points, which exhibits a limited form of sextuple transitivity. Another corollary of the construction is a metric structure on both M₁₂ and M₁₃. Our methods involve relating certain extensions of the game to the ternary Golay code and to 12 x 12 Hadamard matrices.

Full paper (12/29/05): PDF | PS | DVI | arXiv:math.GR/0508630

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

Abstract: Combinatorial rigidity theory seeks to describe the rigidity or flexibility of bar-joint frameworks in R^d in terms of the structure of the underlying graph G. The goal of this article is to broaden the foundations of combinatorial rigidity theory by replacing G with an arbitrary representable matroid M. Many of the constructions of rigidity theory, including the notions of rigidity independence and parallel independence, as well as Laman's and Recski's combinatorial characterizations of 2-dimensional rigidity, can naturally be extended to this wider setting. As we explain, many of these fundamental concepts really depend only on the matroid associated with G (or its Tutte polynomial), and have little to do with the special nature of graphic matroids or the field R. Our main result is a ``nesting theorem'' relating the various kinds of independence. Immediate corollaries include generalizations of Laman's Theorem, as well as the duality between 2-rigidity and 2-parallel independence. A key tool in our study is the photo space of M, a natural algebraic variety whose irreducibility is closely related to the notions of rigidity independence and parallel independence. The number of points on this variety, when working over a finite field, turns out to be an interesting Tutte polynomial evaluation.

Full paper (12/1/05): PDF | PS | DVI | arXiv:math.CO/0503050
Extended abstract for FPSAC 2005 (5/1/05): PDF | PS
Poster for FPSAC 2005 (6/24/05): PDF | PS

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

Abstract: The unit ball random geometric graph G=G^d_p(λ,n) has as its vertices n points distributed independently and uniformly in the unit ball in R^d with two vertices adjacent if and only if their l_p-distance is at most λ. Like its cousin the Erdös-Rényi random graph, G has a connectivity threshold: an asymptotic value for λ in terms of n, above which G is connected and below which G is disconnected (and in fact has isolated vertices in most cases). In the disconnected zone, we discuss the number of isolated vertices. In the connected zone, we determine upper and lower bounds for the graph diameter of G. We employ a combination of methods from probabilistic combinatorics and stochastic geometry.

Full paper (3/22/06): PDF | PS | arXiv:math.CO/0501214

Random geometric graph diameter in the unit disk with l_p metric (Extended Abstract) (with Robert B. Ellis and Catherine Yan)
Lecture Notes in Computer Science 3383 (2005), 167--172.

This is an extended abstract of the full-length paper Random geometric graph diameter in the unit ball, and due to copyright restrictions is available only from the Springer-Verlag website.

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.

Abstract: K. Ding studied a class of Schubert varieties X_λ in type A partial flag manifolds, corresponding to integer partitions λ. He observed that the Schubert cell structure of X_λ is indexed by maximal rook placements on the Ferrers board B_λ, and that the integral cohomology groups H^*(X_λ; Z), H^*(X_μ; Z) are additively isomorphic exactly when the Ferrers boards B_λ, B_μ satisfy the combinatorial condition of rook-equivalence. We classify the varieties X_λ up to isomorphism, distinguishing them by their graded cohomology rings with integer coefficients. The crux of our approach is studying the nilpotence orders of linear forms in the cohomology ring.

Full paper (8/24/04): PDF | PS | arXiv:math.AG/0403530
Talk slides: PDF | PS

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

Abstract: Two naturally occurring matroids representable over Q are shown to be dual: the cyclotomic matroid represented by the nth roots of unity inside the cyclotomic extension Q(ζ), and a direct sum of copies of a certain simplicial matroid, considered originally by Bolker in the context of transportation polytopes. A result of Adin leads to an upper bound for the number of Q-bases for Q(ζ) among the nth roots of unity, which is tight if and only if n has at most two odd prime factors. In addition, we study the Tutte polynomial of the cyclotomic matroid in the case that n has two prime factors.

Full paper (9/15/04): PDF | PS | DVI | arXiv:math.CO/0402206

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

Abstract: Let m₁₂, m₁₃, ..., m_n-1,n be the slopes of the (n choose 2) lines connecting n points in general position in the plane. The ideal I_n of all algebraic relations among the m_ij defines a configuration space called the slope variety of the complete graph. We prove that I_n is reduced and Cohen-Macaulay, give an explicit Gröbner basis for it, and compute its Hilbert series combinatorially. We proceed chiefly by studying the associated Stanley-Reisner simplicial complex, which has an intricate recursive structure. In addition, we are able to answer many questions about the geometry of the slope variety by translating them into purely combinatorial problems concerning enumeration of trees.

Full paper (1/24/06): PDF | PS | DVI | arXiv:math.AG/0302106

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

Abstract: We study the space X^d(G) of pictures of a graph G in complex projective d-space. The main result is that the homology groups (with integer coefficients) of X^d(G) are completely determined by the Tutte polynomial of G. One application is a criterion in terms of the Tutte polynomial for independence in the d-parallel matroids studied in combinatorial rigidity theory. For certain special graphs called orchards, the picture space is smooth and has the structure of an iterated projective bundle. We give a Borel presentation of the cohomology ring of the picture space of an orchard, and use this presentation to develop an analogue of the classical Schubert calculus.

Full paper (4/28/04): PDF | PS | DVI | arXiv:math.CO/0307405
Published version

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

Abstract: For two classes of graphs, threshold graphs and Cartesian products of complete graphs, full or partial factorizations are given for spanning tree enumerators that keep track of fine weights related to degree sequences and edge directions.

Full paper: PDF | PS | DVI | arXiv:math.CO/0302213
Talk slides: PDF | PS

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

Abstract: A picture P of a graph G = (V,E) consists of a point P(v) for each vertex v in V and a line P(e) for each edge e in E, all lying in the projective plane over a field k and subject to containment conditions corresponding to incidence in G. A graph variety is an algebraic set whose points parametrize pictures of G. We consider three kinds of graph varieties: the picture space X(G) of all pictures; the picture variety V(G), an irreducible component of X(G) of dimension 2|V|, defined as the closure of the set of pictures on which all the P(v) are distinct; and the slope variety S(G), obtained by forgetting all data except the slopes of the lines P(e). We use combinatorial techniques (in particular, the theory of combinatorial rigidity) to obtain the following geometric and algebraic information on these varieties:

1. A description and combinatorial interpretation of equations defining each variety set-theoretically.
2. A description of the irreducible components of X(G).
3. A proof that V(G) and S(G) are Cohen-Macaulay when G satisfies a sparsity condition, rigidity independence.

In addition, our techniques yield a new proof of the equality of two matroids studied in rigidity theory.

Full paper: PDF | PS | DVI | arXiv:math.CO/0302089

Graph Varieties
Ph.D. thesis, University of California, San Diego, June 2002. Advisor: Prof. Mark Haiman.

The material is essentially that of the papers "Geometry of graph varieties" and "The slopes determined by n points in the plane".

The whole thing: PDF | PS

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.

Abstract: We prove the following theorems.

• Theorem A. Let G be a group of order 160 satisfying one of the following conditions. (1) G has an image isomorphic to D₂₀ x Z₂ (for example, if G = D₂₀ x K). (2) G has a normal 5-Sylow subgroup and an elementary abelian 2-Sylow subgroup. (3) G has an abelian image of exponent 2, 4, 5, or 10 and order greater than 20. Then G cannot contain a (160,54,18) difference set.
• Theorem B. Suppose G is a nonabelian group with 2-Sylow subgroup S and 5-Sylow subgroup T and contains a (160,54,18) difference set. Then we have one of three possibilities. (1) T is normal, |φ(S)| = 8, and one of the following is true: (a) G = S x T and S is nonabelian; (b) G has a D₁₀ image; or (c) G has a Frobenius image of order 20. (2) G has a Frobenius image of order 80. (3) G is of index 6 in AGL(1,16).

To prove the first case of Theorem A, we find the possible distribution of a putative difference set with the stipulated parameters among the cosets of a normal subgroup using irreducible representations of the quotient; we show that no such distribution is possible. The other two cases are due to others. In the second case (due to Pott) irreducible representations of the elementary abelian quotient of order 32 give a contradiction. In the third case (due to an anonymous referee), the contradiction derives from a theorem of Lander together with Dillon's "dihedral trick." Theorem B summarizes the open nonabelian cases based on this work.

Full paper: PDF | PS | DVI

The Mathieu Group M₁₂ and Conway's M₁₃-Game
Undergraduate thesis, Harvard University, 1996. Advisor: Prof. Noam Elkies.

Summary: Conway proposed an unusual method of constructing the Mathieu group M₁₂, which has a natural extension to a "quasigroup" named M₁₃. We verify Conway's construction by combining a code-theoretic argument (due to Elkies) and a computer search. The computer-generated data was useful in examining a metric on M₁₃ induced naturally by Conway's construction, and to determine the extent to which M₁₃ extends the quintuply transitive action of M₁₂ to a sextuply transitive action.

Full thesis: PDF | DVI

Here are some additional publications, as of April 1, 2005.