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
XT, introduced by Stanley, is a sum of monomial symmetric
functions corresponding to proper colorings of T. The subtree polynomial
ST, 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 ST =
<Φ,XT>, 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 M12 and the M13
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 M12 using
a game reminiscent of Loyd's "15-puzzle." The elements of
M12 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" M13 acting on
all thirteen points, which exhibits a limited form of sextuple
transitivity. Another corollary of the construction is a metric
structure on both M12 and M13. 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 Rd 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=Gdp(λ,n) has as its vertices
n points distributed independently and uniformly in the unit ball in
Rd with two vertices adjacent if and only if their
lp-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 lp 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 m12, m13, ...,
mn-1,n be the slopes of the (n choose
2) lines connecting n points in general position in the
plane. The ideal In of all algebraic relations among
the mij defines a configuration space called the
slope variety of the complete graph. We prove that
In 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 Xd(G) of pictures of a graph
G in complex projective d-space. The main result is that
the homology groups (with integer coefficients) of
Xd(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:
- A description and combinatorial interpretation of equations
defining each variety set-theoretically.
- A description of the irreducible components of X(G).
- 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 D20 x Z2 (for
example, if G = D20 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 D10 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 M12 and Conway's
M13-Game
Undergraduate thesis, Harvard University, 1996. Advisor: Prof. Noam Elkies.
-
Summary:
Conway proposed an unusual method of constructing the Mathieu group
M12, which has a natural extension to a "quasigroup"
named M13. 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
M13 induced naturally by Conway's construction, and to
determine the extent to which M13 extends the
quintuply transitive action of M12 to a sextuply
transitive action.
-
Full thesis:
PDF |
DVI
Here are some additional
publications, as of April 1, 2005.