Preprint.
-
On the spectra of simplicial rook graphs
(with Jennifer D. Wagner)
Preprint. - 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 (9/16/12): PDF | arXiv:1209.3493
-
Cuts and flows of cell complexes
(with Art M. Duval and
Caroline J. Klivans)
Preprint. - 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/3/12): PDF | arXiv:1206.6157
-
Critical groups of simplicial complexes
(with Art M. Duval and
Caroline J. Klivans)
Annals of Combinatorics 17 (2013), 53-70.
- 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), 1-12.
- 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 graph-theoretic 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), 555-570; 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), 247--274. - Abstract: We prove a Matrix-Tree 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 Matrix-Tree Theorem together with a result of Kook, Reiner and Stanton.
- Full paper (5/5/10): PDF | arXiv:0908.1956
-
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 pattern-avoidance 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 node-based and stem-based 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 "tree-thinking" 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: stem-based trees and node-based 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. Stem-based and node-based 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 stem-based and node-based trees clarified, we argue for a distinction between types of trees and types of names. Node-based and stem-based 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 stem-based tree, one should employ stem-based names, whereas for a given node-based tree, one should use node-based names, but applying a node-based name to a stem-based tree is not logical because node-based names cannot exist on a stem-based tree and visa versa. Authors might use node-based and stem-based 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 (open-access) (11/22/10) Full article on the PLoS website
-
Simplicial matrix-tree theorems
(with Art M. Duval and
Caroline J. Klivans)
Transactions of the American Mathematical Society 361 (2009), no. 11, 6073--6114. - Abstract: We generalize the definition and enumeration of spanning trees from the setting of graphs to that of arbitrary-dimensional simplicial complexes \(\Delta\), 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 \(\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), 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 = \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 |
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_{12}\) and the \(M_{13}\)-game
(with John H. Conway and Noam D. Elkies)
Experimental Mathematics 15, no. 2 (2006), 223--236.
See also my undergraduate thesis.
- Abstract: We study a construction of the Mathieu group \(M_{12}\) using a game reminiscent of Loyd's "15-puzzle." 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 | 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 \(\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 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 \(\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 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(\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ös-Ré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 | 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_\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 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 \(\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 | 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_{12},m_{13},\dots,m_{n-1,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 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.
- 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).
- 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
-
Book review of Euler's Gem by David S. Richeson (Princeton U. Press, 2008)
Notices of the American Mathematical Society 57, no. 11 (2010), 1448-1450.
Here are some additional publications, first published on April 1, 2005.
Jeremy Martin's home page
Last updated Mon 3/4/13
Non-research publications