Preprint.
-
Hopf monoids 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 cancellation-free 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
-
Chromatic symmetric functions and polynomial invariants of trees
(with José Aliste-Prieto, Jennifer Wagner, and José Zamora)
Preprint; to appear in Bulletin of the London Mathematical Society. - 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
-
Simplicial effective resistance and enumeration of spanning trees
(with Art M. Duval,
Woong Kook, and Kang-Ju 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 color-shifted 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 high-dimensional analogues of currents and voltages (respectively homological cycles and cohomological cycles).
- Full paper (6/6/22): PDF | arXiv:2206.02182
-
Hopf monoids of ordered simplicial complexes
(with Federico Castillo and
José A. Samper)
International Mathematics Research Notices (2024), no. 20, 13312-13351. - Abstract: We study pure ordered simplicial complexes (i.e., simplicial complexes with a linear order on their ground sets) from the Hopf-theoretic 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, broken-circuit complexes, and unbounded matroids (which arise from unbounded generalized permutohedra with 0/1 coordinates). We compute the antipodes in two cases: facet-initial 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 multiplicity-free and cancellation-free.
- Full paper (11/23/20): PDF | arXiv:2011.14955
- Ehrhart theory of paving and panhandle matroids
(with Derek Hanely,
Daniel McGinnis,
Dane Miyata,
George D. Nasr,
Andrés R. Vindas-Meléndez, and
Mei Yin)
Advances in Geometry 23 (2023), no. 4, 501-526. - 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 panhandle-shaped 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 stressed-hyperplane relaxation introduced by Ferroni, Nasr, and Vecchi, which generalizes the standard matroid-theoretic notion of circuit-hyperplane 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 design-theoretic 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
-
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 bubble-sort 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 Gaussian-cluster
percolation model
(with Galen Dorpalen-Barry,
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 2-connected 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 cut-vertex" rather than "is 2-connected" (so as to include \(K_2\)). -
Enumerating parking completions using Join and Split
(with Ayomikun Adeniran,
Steve Butler,
Galen Dorpalen-Barry,
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 Pitman-Stanley 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) 178-198. - 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 cage-free 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), 2949-2963. - 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{2n-1}{n-1}\), 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 matrix-tree theorem, with applications to complete colorful and cubical complexes
(with Ghodratollah Aalipour,
Art M. Duval,
Woong Kook, and Kang-Ju Lee)
Journal of Combinatorial Theory, Series A 158 (2018), 362-386. - Abstract: We present a version of the weighted cellular matrix-tree 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 tree-counting 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.), 713-752, 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 1-dimensional 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 matroid-theoretic approach to graphs, and yields higher-dimensional analogues of classical enumerative results including Cayley's formula and the matrix-tree theorem. A subtlety of the higher-dimensional 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 high-dimensional 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 non-partitionable Cohen-Macaulay simplicial complex
(with Art M. Duval,
Bennet Goeckner and
Caroline J. Klivans)
Advances in Mathematics 299 (2016), 381-395. - Abstract: A long-standing conjecture of Stanley states that every Cohen-Macaulay 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), 295-325. - 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 skew-symmetric matrix then \(\textrm{pdet}(\partial\partial^t)=\textrm{pdet}(\partial)^2\). Whenever \(\partial\) is the \(k^{th}\) boundary map of a self-dual CW-complex \(X\), this linear-algebraic identity implies that the torsion-weighted generating function for cellular \(k\)-trees in \(X\) is a perfect square. In the case that \(X\) is an antipodally self-dual CW-sphere of odd dimension, the pseudodeterminant of its \(k\)th cellular boundary map can be interpreted directly as a torsion-weighted generating function both for \(k\)-trees and for \((k-1)\)-trees, complementing the analogous result for even-dimensional spheres given by the second author. The argument relies on the topological fact that any self-dual even-dimensional CW-ball can be oriented so that its middle boundary map is skew-symmetric.
-
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), 1589-1611. - 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), 969--999. - 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), 82-106. - Abstract: We study quasipolynomials enumerating proper colorings, nowhere-zero tensions, and nowhere-zero flows in an arbitrary CW-complex \(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,k-1\}\)). We obtain deletion-contraction recurrences and closed formulas for the chromatic, tension and flow quasipolynomials, assuming certain unimodularity conditions. We use geometric methods, specifically Ehrhart theory and inside-out 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), 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
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 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 |
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 |
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), 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 | 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 |
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), 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 | 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 |
arXiv:math.AG/0403530
Talk slides: PDF | -
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 | 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 |
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.
- In citation 11, the author's name is Neil J.A. Sloane, not Nicholas J.A. Sloane.
-
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 |
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 |
arXiv:math.CO/0302213
Talk slides: PDF | -
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 | 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), 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
-
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
-
The Partitionability Conjecture
(with Art M. Duval and
Caroline J. Klivans)
Notices of the American Mathematical Society 64, no. 2 (2017), 117-122. -
Book review of How to Bake \(\pi\) by Eugenia Cheng (Basic Books, 2016)
Notices of the American Mathematical Society 63, no. 9 (2016), 1053-1054. -
Book review of The Cult of Pythagoras by Alberto A. Martínez
(U. Pittsburgh Press, 2012)
The Mathematical Intelligencer 35, no. 4 (2013), 81-82. -
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 10/22/24
Book reviews and expository articles