Publications of Jeremy L. Martin
This page includes the full abstract of each paper. For
bibliographic information alone, see the brief
list.
You may also want to read descriptions
of some of my papers in plain English.
Look me up on
MathSciNet,
the arXiv,
Google Scholar,
or the Math Genealogy Project.

Chromatic symmetric functions and polynomial invariants of trees
(with José AlistePrieto, Jennifer Wagner, and José Zamora)
Preprint.

Abstract:
Stanley asked whether a tree is determined up to isomorphism by its chromatic symmetric function.
We approach Stanley's problem by studying the relationship between the chromatic symmetric function and other invariants.
First, we prove Crew's conjecture that the chromatic symmetric function of a tree determines its generalized degree sequence, which enumerates vertex subsets by cardinality and the numbers of internal and external edges.
Second, we prove that the restriction of the generalized degree sequence to subtrees contains exactly the same information as the subtree polynomial, which enumerates subtrees by cardinality and number of leaves.
Third, we construct arbitrarily large families of trees sharing the same subtree polynomial, proving and generalizing a conjecture of Eisenstat and Gordon.

Full paper (2/19/23):
PDF  arXiv:2402.10333

Unbounded matroids
(with Jonah Berggren and
José A. Samper)
Preprint.

Abstract:
A matroid base polytope is a polytope in which each vertex has 0,1
coordinates and each edge is parallel to a difference of two coordinate
vectors. Matroid base polytopes are described combinatorially by
integral submodular functions on a boolean lattice, satisfying the unit
increase property. We define a more general class of unbounded
matroids, or Umatroids, by replacing the boolean lattice with
an arbitrary distributive lattice. Umatroids thus serve as a
combinatorial model for polyhedra that satisfy the vertex and edge
conditions of matroid base polytopes, but may be unbounded. Like
polymatroids, Umatroids generalize matroids and arise as a special case
of submodular systems. We prove that every Umatroid admits a canonical
largest extension to a matroid, which we call the generous
extension; the analogous geometric statement is that every Umatroid
base polyhedron contains a unique largest matroid base polytope. We
show that the supports of vertices of a Umatroid base polyhedron span a
shellable simplicial complex, and we characterize Umatroid basis
systems in terms of shelling orders, generalizing Björner's and Gale's
criteria for a simplicial complex to be a matroid independence complex.
Finally, we present an application of our theory to subspace
arrangements and show that the generous extension has a natural
geometric interpretation in this setting.

Full paper (12/5/23):
PDF  arXiv:2312.02040

Simplicial effective resistance and enumeration of spanning trees
(with Art M. Duval,
Woong Kook, and KangJu Lee)
Preprint; to appear in Israel Journal of Mathematics.

Abstract:
A graph can be regarded as an electrical network in which each edge is a
resistor. This point of view relates combinatorial quantities, such as
the number of spanning trees, to electrical ones such as effective
resistance. The second and third authors have extended the
combinatorics/electricity analogy to higher dimension and expressed the
simplicial analogue of effective resistance as a ratio of weighted tree
enumerators. In this paper, we first use that ratio to prove a new
enumeration formula for colorshifted complexes, confirming a conjecture
by Aalipour and the first author, and generalizing a result of Ehrenborg
and van Willigenburg on Ferrers graphs. We then use the same technique
to recover an enumeration formula for shifted complexes, first proved by
Klivans and the first and fourth authors. In each case, we add facets
one at a time, and give explicit expressions for simplicial effective
resistances of added facets by constructing highdimensional analogues
of currents and voltages (respectively homological cycles and
cohomological cycles).

Full paper (6/6/22):
PDF  arXiv:2206.02182

A Hopf monoid of set families
(with Kevin Marshall)
Preprint.

Abstract:
A grounded set family on \(I\) is a subset
\(\mathcal{F}\subseteq2^I\) such that \(\emptyset\in\mathcal{F}\). We
study a linearized Hopf monoid SF on grounded set families, with
restriction and contraction inspired by the corresponding operations for
antimatroids. Many known combinatorial species, including simplicial
complexes and matroids, form Hopf submonoids of SF, although not
always with the "standard" Hopf structure (for example, our
contraction operation is not the usual contraction of matroids). We use
the topological methods of Aguiar and Ardila to obtain a
cancellationfree antipode formula for the Hopf submonoid of lattices of
order ideals of finite posets. Furthermore, we prove that the Hopf
algebra of lattices of order ideals of chain gangs extends the Hopf
algebra of symmetric functions, and that its character group extends the
group of formal power series in one variable with constant term 1 under
multiplication.

Full paper (5/12/22):
PDF  arXiv:2205.05772
 Ehrhart theory of paving and panhandle matroids
(with Derek Hanely,
Daniel McGinnis,
Dane Miyata,
George D. Nasr,
Andrés R. VindasMeléndez, and
Mei Yin)
Preprint; to appear in Advances in Geometry.

Abstract:
We show that the base polytope \(P_M\) of any paving matroid \(M\) can be obtained from a hypersimplex by slicing off
subpolytopes. The pieces removed are base polytopes of lattice path matroids corresponding to panhandleshaped
Ferrers diagrams, whose Ehrhart polynomials we can calculate explicitly. Consequently, we can write down the
Ehrhart polynomial of \(P_M\), starting with Katzman's formula for the Ehrhart polynomial of a hypersimplex. The
method builds on and generalizes Ferroni's work on sparse paving matroids. Combinatorially, our construction
corresponds to constructing a uniform matroid from a paving matroid by iterating the operation of
stressedhyperplane relaxation introduced by Ferroni, Nasr, and Vecchi, which generalizes the standard
matroidtheoretic notion of circuithyperplane relaxation. We present evidence that panhandle matroids are
Ehrhart positive and describe a conjectured combinatorial formula involving chain gangs and Eulerian numbers from
which Ehrhart positivity of panhandle matroids will follow. As an application of the main result, we calculate
the Ehrhart polynomials of matroids associated with Steiner systems and finite projective planes, and show that
they depend only on their designtheoretic parameters: for example, while projective planes of the same order
need not have isomorphic matroids, their base polytopes must be Ehrhart equivalent.

Full paper (7/25/23):
PDF  arXiv:2201.12442

Hopf monoids of ordered simplicial complexes
(with Federico Castillo and
José A. Samper)
Preprint.

Abstract:
We study pure ordered simplicial complexes (i.e., simplicial complexes
with a linear order on their ground sets) from the Hopftheoretic point
of view. We define a Hopf class to be a family of pure ordered
simplicial complexes that give rise to a Hopf monoid under join and
deletion/contraction. The prototypical Hopf class is the family of
ordered matroids. The idea of a Hopf class allows us to give a
systematic study of simplicial complexes related to matroids, including
shifted complexes, brokencircuit complexes, and unbounded
matroids (which arise from unbounded generalized permutohedra with 0/1
coordinates).
We compute the antipodes in two cases: facetinitial complexes
(a much larger class than shifted complexes) and unbounded ordered
matroids. In the latter case, we embed the Hopf monoid of ordered
matroids into the Hopf monoid of ordered generalized permutohedra,
enabling us to compute the antipode using the topological method of
Aguiar and Ardila. The calculation is complicated by the appearance of
certain auxiliary simplicial complexes that we call Scrope
complexes, whose Euler characteristics control certain coefficients of
the antipode. The resulting antipode formula is multiplicityfree and
cancellationfree.

Full paper (11/23/20):
PDF  arXiv:2011.14955

Interval parking functions
(with Emma Colaric,
Ryan DeMuse, and
Mei Yin)
Advances in Applied Mathematics 123 (2021) 102129.

Abstract:
Interval parking functions (IPFs) are a generalization of ordinary parking functions in which
each car is willing to park only in a fixed interval of spaces. Each interval parking function
can be expressed as a pair \((a,b)\), where \(a\) is a parking function and \(b\) is a dual parking
function. We say that a pair of permutations \((x,y)\) is reachable if there is an IPF
\((a,b)\) such that \(x,y\) are the outcomes of \(a,b\), respectively, as parking functions.
Reachability is reflexive and antisymmetric, but not in general transitive. We prove that its
transitive closure, the pseudoreachability order, is precisely the bubblesort order on
the symmetric group \(\mathfrak{S}_n\), which can be expressed in terms of the normal form of a
permutation in the sense of du~Cloux; in particular, it is isomorphic to the product of chains
of lengths \(2,\dots,n\). It is thus seen to be a special case of Armstrong's sorting order,
which lies between the Bruhat and (left) weak orders.

Full paper (10/28/20):
PDF  arXiv:2006.09321
 A positivity phenomenon in Elser's Gaussiancluster
percolation model
(with Galen DorpalenBarry,
Cyrus Hettle,
David C. Livingston, George Nasr,
Julianne Vega,
and Hays Whitlatch)
Journal of Combinatorial Theory, Series A 179 (2021) 105364.

Abstract:
Veit Elser proposed a random graph model for percolation in which
physical dimension appears as a parameter. Studying this model
combinatorially leads naturally to the consideration of numerical graph
invariants which we call Elser numbers \(\mathsf{els}_k(G)\),
where \(G\) is a connected graph and k a nonnegative integer. Elser had
proven that \(\mathsf{els}_1(G)=0\) for all \(G\). By interpreting the
Elser numbers as Euler characteristics of appropriate simplicial
complexes called nucleus complexes, we prove that for all graphs
\(G\), they are nonpositive when \(k=0\) and nonnegative for \(k\geq2\).
The last result confirms a conjecture of Elser. Furthermore, we give
necessary and sufficient conditions, in terms of the 2connected
structure of \(G\) for the nonvanishing of the Elser numbers.

Full paper (11/4/19):
PDF  arXiv:1905.11330
Note: There is an error in Conjecture 9.1; the first condition should
read "(i) \(U=\emptyset\) and \(k=E(G)V(G)+1\)" (not \(1\)). In addition, Theorems 1.2 and 7.5 should read "has no cutvertex" rather than "is 2connected" (so as to include \(K_2\)).

Enumerating parking completions using Join and Split
(with Ayomikun Adeniran,
Steve Butler,
Galen DorpalenBarry,
Pamela E. Harris,
Cyrus Hettle,
Qingzhong Liang,
and Hayan Nam)
Electronic Journal of Combinatorics 27, no. 2 (2020), #P2.44.

Abstract:
Given a strictly increasing sequence \(\mathbf{t}\) with entries from
\([n]:=\{1,\ldots,n\}\), a parking completion is a sequence
\(\mathbf{c}\) with \(\mathbf{t}+\mathbf{c}=n\) and \(\{t\in
\mathbf{t}\mid t\le i\}+\{c\in \mathbf{c}\mid c\le i\}\ge i\) for all
\(i\) in \([n]\). We can think of \(\mathbf{t}\) as a list of spots
already taken in a street with \(n\) parking spots and \(\mathbf{c}\) as
a list of parking preferences where the \(i\)th car attempts to park in
the \(c_i\)th spot and if not available then proceeds up the street to
find the next available spot, if any. A parking completion corresponds
to a set of preferences \(\mathbf{c}\) where all cars park.
We relate parking completions to enumerating restricted lattice paths
and give formulas for both the ordered and unordered variations of the
problem by use of a pair of operations termed Join and
Split. Our results give a new volume formula for most
PitmanStanley polytopes, and enumerate the signature parking
functions of Ceballos and González D'León.

Full paper (6/12/20)

Increasing spanning forests in graphs and simplicial complexes
(with Joshua Hallam and
Bruce E. Sagan)
European Journal of Combinatorics 76 (2019) 178198.

Abstract:
Let \(G\) be a graph with vertex set \(\{1,\dots,n\}\). A spanning forest \(F\) of \(G\) is {\em increasing} if the sequence of labels on any path
starting at the minimum vertex of a tree of \(F\) forms an increasing sequence. Hallam and Sagan showed that the generating function
\(\textrm{ISF}(G,t)\) for increasing spanning forests of \(G\) has all nonpositive integral roots. Furthermore they proved that, up to a change of
sign, this polynomial equals the chromatic polynomial of \(G\) precisely when \(1,\dots,n\) is a perfect elimination order for \(G\). We give
new, purely combinatorial proofs of these results which permit us to generalize them in several ways. For example, we are able to bound the
coefficients of \(\textrm{ISF}(G,t)\) using broken circuits. We are also able to extend these results to simplicial complexes using the new notion of
a cagefree complex. A generalization to labeled multigraphs is also given.
We observe that the definition of an increasing spanning forest can be formulated in terms of pattern
avoidance, and we end by exploring spanning forests that avoid the
patterns 231, 312 and 321.

Full paper (10/18/16):
PDF  arXiv:1610.05093

Counting arithmetical structures on paths and cycles
(with Benjamin Braun,
Hugo Corrales,
Scott Corry,
Luis David García Puente,
Darren Glass,
Nathan Kaplan,
Gregg Musiker, and
Carlos E. Valencia)
Discrete Mathematics 341 (2018), 29492963.

Abstract:
Let \(G\) be a finite, simple, connected graph. An arithmetical structure on \(G\) is a pair of positive integer vectors
\(\mathbf{d},\mathbf{r}\) such that \(({\rm diag}(\mathbf{d})A)\mathbf{r}=0\), where \(A\) is the adjacency matrix of \(G\). We
investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the
cokernels of the matrices \(({\rm diag}(\mathbf{d})A)\)). For paths, we prove that arithmetical structures are enumerated by the
Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical
structures are enumerated by the binomial coefficients \(\binom{2n1}{n1}\), and we obtain refined enumeration results related to
multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

Full paper (7/27/18):
PDF  arXiv:1701.06377

A weighted cellular matrixtree theorem, with applications to complete colorful and cubical complexes
(with Ghodratollah Aalipour,
Art M. Duval,
Woong Kook, and KangJu Lee)
Journal of Combinatorial Theory, Series A 158 (2018), 362386.

Abstract:
We present a version of the weighted cellular matrixtree theorem that is suitable for
calculating explicit generating functions for spanning trees of highly structured families of
simplicial and cell complexes. We apply the result to give weighted generalizations of the tree
enumeration formulas of Adin for complete colorful complexes, and of Duval, Klivans and Martin
for skeleta of hypercubes. We investigate the latter further via a logarithmic generating
function for weighted tree enumeration, and derive another treecounting formula using the
unsigned Euler characteristics of skeleta of a hypercube and the Crapo \(\beta\)invariant of
uniform matroids. Note: This version combines two previous preprints, one by GA, AMD and JLM
and one by WK and KL, with related results and obtained independently.

Full paper (3/14/18):
PDF  arXiv:1510.00033

Oscillation estimates of eigenfunctions via the combinatorics of noncrossing partitions
(with Vera Mikyoung Hur and
Mathew A. Johnson)
Discrete Analysis 2017,
Paper No. 13, 20 pp.

Abstract:
We study oscillations in the eigenfunctions for a fractional Schrödinger operator on the real line. An argument in the spirit of Courant's nodal domain theorem applies to an associated local problem in the upper half plane and provides a bound on the number of nodal domains for the extensions of the eigenfunctions. Using the combinatorial properties of noncrossing partitions, we turn the nodal domain bound into an estimate for the number of sign changes in the eigenfunctions. We discuss applications in the periodic setting and the Steklov problem on planar domains.

Full paper (9/5/17):
PDF  arxiv:1609.02189

Simplicial and Cellular Trees
(with Art M. Duval and
Caroline J. Klivans)
Recent Trends in Combinatorics (A. Beveridge, J. Griggs, L. Hogben, G. Musiker and P.
Tetali, eds.), 713752, IMA Vol. Math. Appl. 159, Springer, 2016.

Abstract:
Much information about a graph can be obtained by studying its spanning trees. On the other hand, a graph can be regarded as a 1dimensional cell complex, raising the question of developing a theory of trees in higher dimension. As observed first by Bolker, Kalai and Adin, and more recently by numerous authors, the fundamental topological properties of a tree  namely acyclicity and connectedness  can be generalized to arbitrary dimension as the vanishing of certain cellular homology groups. This point of view is consistent with the matroidtheoretic approach to graphs, and yields higherdimensional analogues of classical enumerative results including Cayley's formula and the matrixtree theorem. A subtlety of the higherdimensional case is that enumeration must account for the possibility of torsion homology in trees, which is always trivial for graphs. Cellular trees are the starting point for further highdimensional extensions of concepts from algebraic graph theory including the critical group, cut and flow spaces, and discrete dynamical systems such as the abelian sandpile model.

Full chapter (6/22/15):
PDF  arXiv:1506.06819

A nonpartitionable CohenMacaulay simplicial complex
(with Art M. Duval,
Bennet Goeckner and
Caroline J. Klivans)
Advances in Mathematics 299 (2016), 381395.

Abstract:
A longstanding conjecture of Stanley states that every CohenMacaulay simplicial complex is partitionable. We disprove the conjecture by constructing an explicit counterexample. Due to a result of Herzog, Jahan and Yassemi, our construction also disproves the conjecture that the Stanley depth of a monomial ideal is always at least its depth.

Full paper (5/5/15):
PDF  arXiv:1504.04279
See also the expository article "The Partitionability Conjecture" by Duval, Klivans and myself.

Pseudodeterminants and perfect square spanning tree counts
(with Molly Maxwell, Victor Reiner, and
Scott O. Wilson)
Journal of Combinatorics 6, no. 3 (2015), 295325.

Abstract:
The pseudodeterminant \(\textrm{pdet}(M)\) of a square matrix is the last nonzero coefficient in its characteristic polynomial; for a nonsingular matrix, this is just the determinant. If \(\partial\) is a symmetric or skewsymmetric matrix then \(\textrm{pdet}(\partial\partial^t)=\textrm{pdet}(\partial)^2\). Whenever \(\partial\) is the \(k^{th}\) boundary map of a selfdual CWcomplex \(X\), this linearalgebraic identity implies that the torsionweighted generating function for cellular \(k\)trees in \(X\) is a perfect square. In the case that \(X\) is an antipodally selfdual CWsphere of odd dimension, the pseudodeterminant of its \(k\)th cellular boundary map can be interpreted directly as a torsionweighted generating function both for \(k\)trees and for \((k1)\)trees, complementing the analogous result for evendimensional spheres given by the second author. The argument relies on the topological fact that any selfdual evendimensional CWball can be oriented so that its middle boundary map is skewsymmetric.

Full paper (1/2/15):
PDF  arXiv:1311.6686
Erratum

On the spectra of simplicial rook graphs
(with Jennifer D. Wagner)
Graphs and Combinatorics 31, no. 5 (2015), 15891611.

Abstract:
The simplicial rook graph \(SR(d,n)\) is the graph whose vertices
are the lattice points in the \(n\)th dilate of the standard simplex in
\(\mathbb{R}^d\), with two vertices adjacent if they differ in exactly
two coordinates. We prove that the adjacency and Laplacian matrices of
\(SR(3,n)\) have integral spectrum for every \(n\). The proof proceeds by
calculating an explicit eigenbasis. We conjecture that \(SR(d,n)\) is
integral for all \(d\) and \(n\), and present evidence in support of this
conjecture. For \(n<\binom{d}{2}\), the evidence indicates that the
smallest eigenvalue of the adjacency matrix is \(n\), and that the
corresponding eigenspace has dimension given by the Mahonian numbers,
which enumerate permutations by number of inversions.

Full paper (4/22/14):
PDF  arXiv:1209.3493

Cuts and flows of cell complexes
(with Art M. Duval and
Caroline J. Klivans)
Journal of Algebraic Combinatorics 41 (2015), 969999.

Abstract:
We study the vector spaces and integer lattices of cuts and flows
associated with an arbitrary finite CW complex, and their
relationships to group invariants including the critical group
of a complex. Our results extend to higher dimension the
theory of cuts and flows in graphs, most notably the work of Bacher,
de la Harpe and Nagnibeda. We construct explicit bases for the cut and
flow spaces, interpret their coefficients topologically, and give sufficient
conditions for them to be integral bases of the cut and flow lattices.
Second, we determine the precise relationships between the discriminant
groups of the cut and flow lattices and the higher critical and cocritical
groups with error terms corresponding to torsion (co)homology. As an
application, we generalize a result of Kotani and Sunada to give bounds
for the complexity, girth, and connectivity of a complex in terms of
Hermite's constant.

Full paper (8/12/14):
PDF 
arXiv:1206.6157

Enumerating colorings, tensions and flows in cell complexes
(with Matthias Beck,
Felix Breuer and
Logan Godkin)
Journal of Combinatorial Theory, Series A 122 (2014), 82106.

Abstract:
We study quasipolynomials enumerating proper colorings, nowherezero
tensions, and nowherezero flows in an arbitrary CWcomplex \(X\),
generalizing the chromatic, tension and flow polynomials of a graph.
Our colorings, tensions and flows may be either
modular (with values in \(\mathbb{Z}/k\mathbb{Z}\) for some \(k\))
or integral (with values in \(\{k+1,\dots,k1\}\)).
We obtain deletioncontraction recurrences and closed formulas
for the chromatic, tension and flow quasipolynomials, assuming certain
unimodularity conditions. We use geometric methods, specifically
Ehrhart theory and insideout polytopes, to obtain
reciprocity formulas for the numbers of acyclic and totally cyclic
orientations of \(X\).

Full paper (10/23/13):
PDF  arXiv:1212.6539

Critical groups of simplicial complexes
(with Art M. Duval and
Caroline J. Klivans)
Annals of Combinatorics 17 (2013), 5370.

Abstract:
We generalize the theory of critical groups from graphs to simplicial
complexes. Specifically, given a simplicial complex, we define a family of
abelian groups in terms of combinatorial Laplacian operators, generalizing the
construction of the critical group of a graph. We show how to realize these
critical groups explicitly as cokernels of reduced Laplacians, and prove that
they are finite, with orders given by weighted enumerators of simplicial
spanning trees. We describe how the critical groups of a complex represent flow
along its faces, and sketch another potential interpretation as analogues of
Chow groups.

Full paper (2/28/11):
PDF 
arXiv:1101.3981
Macaulay2 computations for several examples

Graph varieties in high dimension
(with Thomas Enkosky)
Beiträge zur Algebra und Geometrie 54, no. 1 (2013), 112.

Abstract:
We study the picture space \( \mathcal{X}^d(G) \) of all embeddings
of a finite graph \( G \) in projective \( d \)space, continuing
previous work of the second author on the \( d=2 \) case. The
picture space admits a natural decomposition into smooth
quasiprojective subvarieties called cellules, indexed by partitions
of \( V(G) \), and the irreducible components
of \( \mathcal{X}^d(G) \) correspond to cellules that are maximal
with respect to a partial order on partitions that is in general
weaker than refinement. We study both general properties of this
partial order and its characterization for specific graphs. Our
results include complete combinatorial descriptions of the
irreducible components of the picture spaces of complete graphs and
complete multipartite graphs, for any ambient dimension \( d \). In
addition, we give two graphtheoretic formulas for the minimum
ambient dimension in which the directions of edges in an embedding
of \( G \) are mutually constrained.

Full paper (6/20/11):
PDF 
arxiv:1006.5864

The incidence Hopf algebra of graphs
(with Brandon Humpert)
SIAM Journal on Discrete Mathematics 26, no. 2 (2012), 555570; published online 5/3/12.

Abstract:
The graph algebra is a commutative,
cocommutative, graded, connected incidence Hopf algebra, whose basis
elements correspond to finite simple graphs and whose Hopf product
and coproduct admit simple combinatorial descriptions. We give a
new formula for the antipode in the graph algebra in terms of
acyclic orientations; our formula contains many fewer terms than
Takeuchi's and Schmitt's more general formulas for the antipode in
an incidence Hopf algebra. Applications include several formulas
(some old and some new) for evaluations of the Tutte polynomial.

Full paper (3/14/12):
PDF 
arXiv:1012.4786

Cellular spanning trees and Laplacians of cubical complexes
(with Art M. Duval and
Caroline J. Klivans)
>Advances
in Applied Mathematics 46 (2011), 247274.

Abstract:
We prove a MatrixTree Theorem enumerating the spanning trees of a cell
complex in terms of the eigenvalues of its cellular Laplacian operators,
generalizing a previous result for simplicial complexes. As an application, we
obtain explicit formulas for spanning tree enumerators and Laplacian
eigenvalues of cubes; the latter are integers. We prove a weighted version of
the eigenvalue formula, providing evidence for a conjecture on weighted
enumeration of cubical spanning trees. We introduce a cubical analogue of
shiftedness, and obtain a recursive formula for the Laplacian eigenvalues of
shifted cubical complexes, in particular, these eigenvalues are also integers.
Finally, we recover Adin's enumeration of spanning trees of a complete colorful
simplicial complex from the cellular MatrixTree Theorem together with a result
of Kook, Reiner and Stanton.

Full paper (5/5/10):
PDF 
arXiv:0908.1956
Erratum

Updown numbers and the initial monomials of the slope variety
(with Jennifer D. Wagner)
Electronic Journal of Combinatorics 16, no. 1 (2009), Research Paper R82.

Abstract:
Let \( I_n \) be the ideal of all algebraic relations on the slopes of the
\( \binom{n}{2} \) lines formed by placing \( n \) points in a plane
and connecting each pair of points with a line. Under each of two natural term
orders, the initial ideal \( \mathrm{in}(I_n) \) is generated by monomials corresponding
to permutations satisfying a certain patternavoidance condition. We show bijectively that these
permutations are enumerated by the updown (or Euler) numbers,
thereby obtaining a formula for the number of generators of \( \mathrm{in}(I_n) \) in every degree.

Full paper (7/9/09):
Published version at EJC 
arXiv:0905.4751
Talk slides for AMS Sectional Meeting, Notre Dame, November 2010: PDF

Are nodebased and stembased clades equivalent? Insights from graph theory
(with David C. Blackburn and Edward O. Wiley)
PLOS Currents: Tree of Life,
article published online 11/18/2010.

Abstract:
Despite the prominence of "treethinking" among contemporary systematists and evolutionary biologists, the biological meaning of different mathematical representations of phylogenies may still be muddled. We compare two basic kinds of discrete mathematical models used to portray phylogenetic relationships among species and higher taxa: stembased trees and nodebased trees. Each model is a tree in the sense that is commonly used in mathematics; the difference between them lies in the biological interpretation of their vertices and edges. Stembased and nodebased trees carry exactly the same information and the biological interpretation of each is similar. Translation between these two kinds of trees can be accomplished by a simple algorithm, which we provide. With the mathematical representation of stembased and nodebased trees clarified, we argue for a distinction between types of trees and types of names. Nodebased and stembased trees contain exactly the same information for naming clades. However, evolutionary concepts, such as monophyly, are represented as different mathematical substructures in the two models. For a given stembased tree, one should employ stembased names, whereas for a given nodebased tree, one should use nodebased names, but applying a nodebased name to a stembased tree is not logical because nodebased names cannot exist on a stembased tree and visa versa. Authors might use nodebased and stembased concepts of monophyly for the same representation of a phylogeny, yet, if so, they must recognize that such a representation differs from the graphical models used for computing in phylogenetic systematics.

Full article on PubMed Central (openaccess) (11/22/10)
Full article on the PLoS website

Simplicial matrixtree theorems
(with Art M. Duval and
Caroline J. Klivans)
Transactions of the American
Mathematical Society 361 (2009), no. 11, 60736114.

Abstract:
We generalize the definition and enumeration of spanning trees from the
setting of graphs to that of arbitrarydimensional simplicial complexes
\(\Delta\), extending an idea due to G. Kalai. We prove a simplicial version of
the MatrixTree Theorem that counts simplicial spanning trees, weighted by the
squares of the orders of their topdimensional integral homology groups, in
terms of the Laplacian matrix of \(\Delta\). 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 \(\Delta\) and replacing the
entries of the Laplacian with Laurent monomials. When \(\Delta\) 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 (8/14/08):
Published version on AMS website (requires access) 
PDF preprint 
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), 237253.

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 = \langle\Phi,X_T\rangle \), where
\(\langle\cdot,\cdot\rangle\) is the Hall inner
product on symmetric functions and \(\Phi\) 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 
arXiv:math.CO/0609339
Talk slides from FPSAC 2006:
PDF
Relevant Maple worksheets and data files,
including computational evidence for two conjectures
Link to LiYang 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), 267286.

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 
arXiv:math.CO/0511248
Talk slides (12/6/05):
PDF 
Related Maple worksheets

The Mathieu group \(M_{12}\) and the \(M_{13}\)game
(with John H. Conway and Noam D. Elkies)
Experimental Mathematics 15,
no. 2 (2006), 223236.
See also my undergraduate thesis.

Abstract:
We study a construction of the Mathieu group \(M_{12}\) using
a game reminiscent of Loyd's "15puzzle." The elements of
\(M_{12}\) 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_{13}\) 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_{12}\) and \(M_{13}\). Both
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 
arXiv:math.GR/0508630

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

Abstract:
Combinatorial rigidity theory seeks to describe the rigidity or flexibility of
barjoint frameworks in \(\mathbb{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 2dimensional 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 \(\mathbb{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 2rigidity and 2parallel 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 
arXiv:math.CO/0503050
Extended abstract for FPSAC 2005 (5/1/05):
PDF 
Poster for FPSAC 2005 (6/24/05):
PDF 

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

Abstract:
The unit ball random geometric graph \(G=G^d_p(\lambda,n)\) has as its vertices
\(n\) points distributed independently and uniformly in the unit ball in
\(\mathbb{R}^d\) with two vertices adjacent if and only if their
\(\ell_p\)distance is at most \(\lambda\). Like its cousin the
ErdösRényi random graph, \(G\) has a connectivity
threshold: an asymptotic value for \(\lambda\) 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 
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), 167172.

This is an extended abstract of the fulllength paper Random geometric
graph diameter in the unit ball, and due to copyright restrictions is available only from the
SpringerVerlag website.

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

Abstract:
K. Ding studied a class of Schubert varieties \(X_\lambda\) in type A
partial flag manifolds, corresponding to integer partitions
\(\lambda\). He observed that the Schubert cell structure of
\(X_\lambda\) is indexed by maximal rook placements on the Ferrers
board \(B_\lambda\), and that the integral cohomology groups
\(H^*(X_\lambda;\mathbb{Z})\) and \(H^*(X_\mu;\mathbb{Z})\),
are additively isomorphic exactly when the Ferrers boards
\(B_\lambda\), \(B_\mu\)
satisfy the combinatorial condition of
rookequivalence. 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 
arXiv:math.AG/0403530
Talk slides:
PDF 

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

Abstract:
Two naturally occurring matroids representable over \(\mathbb{Q}\) are shown
to be dual: the cyclotomic matroid represented by the \(n\)th
roots of unity inside the cyclotomic extension \(\mathbb{Q}(\zeta)\)
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 \(\mathbb{Q}\)bases
for \(\mathbb{Q}(\zeta)\) among the \(n\)th 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 
arXiv:math.CO/0402206

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

Abstract:
Let \(m_{12},m_{13},\dots,m_{n1,n}\) be the slopes of the \(\binom{n}{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 CohenMacaulay, give an explicit
Gröbner basis for it, and compute its Hilbert series
combinatorially. We proceed chiefly by studying the associated
StanleyReisner 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 
arXiv:math.AG/0302106
Errata:
 In citation 11, the author's name is Neil J.A. Sloane, not Nicholas J.A. Sloane.
 In the table on p.32, the correct value of \(d(6,3)\) is 195, not 105.

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

Abstract:
We study the space X^{d}(G) of pictures of a graph
G in complex projective dspace. 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 dparallel 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 
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), 287300.

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 
arXiv:math.CO/0302213
Talk slides:
PDF 

Geometry of graph varieties
Transactions of the American
Mathematical Society 355 (2003), 41514169.

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 2V, 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 settheoretically.
 A description of the irreducible components of X(G).
 A proof that V(G) and S(G) are
CohenMacaulay 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 
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

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), 221231.

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_{20} x Z_{2} (for
example, if G = D_{20} x K).
(2) G has a normal 5Sylow subgroup and an elementary abelian 2Sylow
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 2Sylow subgroup S
and 5Sylow 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_{10} 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

The Mathieu Group M_{12} and Conway's
M_{13}Game
Undergraduate thesis, Harvard University, 1996. Advisor: Prof. Noam Elkies.

Summary:
Conway proposed an unusual method of constructing the Mathieu group
M_{12}, which has a natural extension to a "quasigroup"
named M_{13}. We verify Conway's construction by
combining a codetheoretic argument (due to Elkies) and a computer
search. The computergenerated data was useful in examining a metric on
M_{13} induced naturally by Conway's construction, and to
determine the extent to which M_{13} extends the
quintuply transitive action of M_{12} to a sextuply
transitive action.

Full thesis:
PDF
Book reviews and expository articles

The Partitionability Conjecture
(with Art M. Duval and
Caroline J. Klivans)
Notices of the American Mathematical Society
64, no. 2 (2017), 117122.

Book review of How to Bake \(\pi\) by Eugenia Cheng (Basic Books, 2016)
Notices of the American Mathematical Society
63, no. 9 (2016), 10531054.

Book review of The Cult of Pythagoras by Alberto A. Martínez
(U. Pittsburgh Press, 2012)
The Mathematical Intelligencer 35, no. 4 (2013), 8182.

Book review of Euler's Gem by David S. Richeson (Princeton U. Press, 2008)
Notices of the American Mathematical Society
57, no. 11 (2010), 14481450.
Here are some additional
publications, first published on April 1, 2005.
Jeremy Martin's home page
Last updated 2/20/24