Publications
 The Mathematics of ChipFiring (Book)
Published by CRC Press.
The Mathematics of ChipFiring provides an introduction and overview of the fast growing area of chipfiring. The book aims to give the reader an appreciation for the richness and diversity of chipfiring and a solid foundation to enter the field as a researcher.
 Flowfiring processes with Pedro Felzenszwalb.
We consider a discrete nondeterministic flowfiring process for rerouting flow on the edges of a planar complex. The process is an instance of higherdimensional chipfiring. In the flowfiring process, flow on the edges of a complex is repeatedly diverted across the faces of the complex. For nonconservative initial configurations we show this process never terminates. For conservative initial flows we show the process terminates after a finite number of rerouting steps, but there are many possible final configurations reachable from a single initial state. Finally, for conservative initial flows around a topological hole we show the process terminates at a unique final configuration. In this case the process exhibits global confluence despite not satisfying local confluence.
 On the topology of no kequal spaces with Yuliy Baryshnikov and Nicholas Kosar.
Submitted for Publication.
We consider the topology of real no kequal spaces via the theory of cellular spanning trees. Our main theorem proves that the rank of the (k2)dimensional homology of the no kequal subspace of R is equal to the number of facets in a kdimensional spanning tree of the kskeleton of the ndimensional hypercube.

On the connectivity of threedimensional tilings with Juliana Freire, Pedro H. Milet and Nicolau C. Saldanha.
Submitted for Publication.
We consider domino tilings of threedimensional cubiculated manifolds with or without boundary, including subsets of Euclidean space and threedimensional tori. In particular, we are interested in the connected components of the space of tilings of such regions under local moves. Building on the work of the third and fourth authors, we allow two possible local moves, the flip and trit. These moves are considered with respect to two topological invariants, the twist andflux. Our main result proves that, up to refinement, Two tilings are connected by flips and trits if and only if they have the same flux. Two tilings are connected by flips alone if and only if they have the same flux and twist.

The Partitionability Conjecture with Art Duval and Jeremy Martin.
Notices of the AMS, 64(2), 117122, 2017.
In 1979 Richard Stanley made the following conjecture: Every CohenMacaulay simplicial complex is partitionable. Motivated by questions in the theory of face numbers of simplicial complexes, the Partitionability Conjecture sought to connect a purely combinatorial condition (partitionability) with an algebraic condition (CohenMacaulayness). The algebraic combinatorics community widely believed the conjecture to be true, especially in light of related stronger conjectures and weaker partial results. Nevertheless, in a 2016 paper, the three of us (Art, Carly, and Jeremy), together with Jeremy’s graduate student Bennet Goeckner, constructed an explicit counterexample. Here we tell the story of the significance and motivation behind the Partitionability Conjecture and its resolution. The key mathematical ingredients include relative simplicial complexes, nonshellable balls, and a surprise appearance by the pigeonhole principle. More broadly, the narrative of the Partitionability Conjecture highlights a general theme of modern algebraic combinatorics: to understand discrete structures through algebraic, geometric, and topological lenses.

Chip firing on Dynkin diagrams and McKay Quivers with G. Benkart and V. Reiner.
To appear: Mathematische Zeitschrift 2018.
Two classes of avalanchefinite matrices and their critical groups (integer cokernels) are studied from the viewpoint of chipfiring/sandpile dynamics, namely, the Cartan matrices of finite root systems and the McKayCartan matrices for finite subgroups G of general linear groups. In the root system case, the recurrent and superstable configurations are identified explicitly and are related to minuscule dominant weights. In the McKayCartan case for finite subgroups of the special linear group, the cokernel is related to the abelianization of the subgroup G. In the special case of the classical McKay correspondence, the critical group and the abelianization are shown to be isomorphic.

Directed rooted forests in higher dimension with O. Bernardi.
The Electronic Journal of Combinatorics, 23(4), 2016.
For a graph G, the generating function of rooted forests, counted by the number of connected components, can be expressed in terms of the eigenvalues of the graph Laplacian. We generalize this result from graphs to cell complexes of arbitrary dimension. This requires generalizing the notion of rooted forest to higher dimension. We also introduce orientations of higher dimensional rooted trees and forests. These orientations are discrete vector fields which lead to open questions concerning expressing homological quantities combinatorially.

Chipfiring on general invertible matrices with J. Guzman.
SIAM Journal on Discrete Mathematics, 30(2), 2016.
We propose a generalization of the graphical chipfiring model allowing for the redistribution dynamics to be governed by any invertible integer matrix while maintaining the long term critical, superstable, and energy minimizing behavior of the classical model.

Simplicial and Cellular Trees with A. Duval and J. Martin.
Book chapter in the IMA volume "Recent Trends in Combinatorics" 2015.
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.

A nonpartitionable CohenMacaulay simplicial complex with A. Duval, B. Goeckner and J. Martin.
Advances in Mathematics, Vol. 299, 2016.
A longstanding 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.

Coxeter arrangements in three dimensions (or Springer Share version ) with R. Ehrenborg and N. Reading.
Beitrage zur Algebra and Geometrie / Contributions to Algebra and Geometry. 2016.
Let A be a finite real linear hyperplane arrangement in three dimensions. Suppose further that all the regions of A are isometric. We prove that A is necessarily a Coxeter arrangement. As it is well known that the regions of a Coxeter arrangement are isometric, this characterizes threedimensional Coxeter arrangements precisely as those arrangements with isometric regions. It is an open question whether this suffices to characterize Coxeter arrangements in higher dimensions. We also present the three families of affine arrangements in the plane which are not reflection arrangements, but in which all the regions are isometric.

Chipfiring and energy minimization on Mmatrices with J. Guzman.
Journal of Combinatorial Theory, Series A, Volume 132, May 2015, Pages 1431.
We consider chipfiring dynamics defined by arbitrary Mmatrices. Mmatrices generalize graph Laplacians and were shown by Gabrielov to yield avalanche finite systems. Building on the work of Baker and Shokrieh, we extend the concept of energy minimizing chip configurations. Given an Mmatrix, we show that there exists a unique energy minimizing configuration in each equivalence class defined by the matrix. We define the class of zsuperstable configurations which satisfy a strictly stronger stability requirement than superstable configurations (equivalently Gparking functions or reduced divisors). We prove that for any Mmatrix, the zsuperstable configurations coincide with the energy minimizing configurations. Moreover, we prove that the zsuperstable configurations are in simple duality with critical configurations. Thus for all avalanchefinite systems (including all directed graphs with a global sink) there exist unique critical, energy minimizing and zsuperstable configurations. The critical configurations are in simple duality with energy minimizers which coincide with zsuperstable configurations.

Scheduling problems with F. Breuer.
Journal of Combinatorial Theory, Series A, Vol. 139, 2016.
We introduce the notion of a scheduling problem which is a boolean function S over atomic formulas of the form x_i < x_j. Considering the x_i as jobs to be performed, an integer assignment satisfying S schedules the jobs subject to the constraints of the atomic formulas. The scheduling counting function counts the number of solutions to S. We prove that this counting function is a polynomial in the number of time slots allowed. Scheduling polynomials include the chromatic polynomial of a graph, the zeta polynomial of a lattice, the BilleraJiaReiner polynomial of a matroid and the newly defined arboricity polynomial of a matroid. To any scheduling problem, we associate not only a counting function for solutions, but also a quasisymmetric function and a quasisymmetric function in noncommuting variables. These scheduling functions include the chromatic symmetric functions of Sagan, Gebhard, and Stanley, and a close variant of Ehrenborg's quasisymmetric function for posets. Geometrically, we consider the space of all solutions to a given scheduling problem. We extend a result of Steingrimsson by proving that the hvector of the space of solutions is given by a shift of the scheduling polynomial. Furthermore, under certain niceness conditions on the defining boolean function, we prove partitionability of the space of solutions and positivity of fundamental expansions of the scheduling quasisymmetric functions and of the hvector of the scheduling polynomial.

A CheegerType inequality on simplicial complexes with J. Steenbergen and S. Mukherjee.
Advances in Applied Mathematics, Vol. 56, 2014.
In this paper, we consider a variation on Cheeger numbers related to the coboundary expanders recently defined by Dotterer and Kahle. A Cheegertype inequality is proved, which is similar to a result on graphs due to Fan Chung. This inequality is then used to study the relationship between coboundary expanders on simplicial complexes and their corresponding eigenvalues, complementing and extending results found by Gundert and Wagner. In particular, we find these coboundary expanders do not satisfy natural Buser or Cheeger inequalities.

Cuts and flows of cell complexes with A. Duval and J. Martin.
Journal of Algebraic Combinatorics, 131, 2014.
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.

A quasisymmetric function for generalized permutahedra with M. Aguiar and L. Billera.
(Talk Slides)
Given a generalized permutahedron, we associate both a quasisymmetric function and a simplicial complex. We prove positivity of the quasisymmetric function in the fundamental basis and positivity of the hvector of the complex. Further we explore the relationship between these two collections extending a result of Steingrimmson to arbitrary subcomplexes of the Coxeter complex. Our framework includes Stanley's chromatic quasisymmetric function, Steingrimsson's coloring complex, and the BilleraJiaReiner quasisymmetric function all as special instances.

A conjecture on Gparking functions and GShi arrangements with A. Duval and J. Martin.
(Talk slides by A. Duval).
This conjecture has since been proved by David Perkinson and Sam Hopkins Bigraphical Arrangements.
Pak and Stanley found a bijection between parking functions on n and regions of the complement of the Shi arrangement. In particular, there is a somewhat natural labeling of the regions such that every region has a different label, and these labels are precisely the parking functions on n. We define a GShi hyperplane arrangement of an arbitrary graph G, and compare the regions of the complement of this arrangement to Gparking functions, a wellstudied generalization of parking functions to arbitrary graphs. In particular, while the PakStanley labels of regions are no longer necessarily unique, we conjecture that the set of different PakStanley labels of regions of the GShi arrangement is precisely the set of (G + v)parking functions, where G + v is the join of G with a single vertex v. We offer some evidence in favor of the conjecture, including a proof that every label is a parking function.

Critical groups of simplicial complexes (Sandpile Groups) with A. Duval and J. Martin.
Annals of Combinatorics. Vol. 17, Issue 1 (2013). Extended abstract appeared in FPSAC 2011.
We generalize the theory of critical groups from graphs to simplicial complexes. We define the higher critical groups K_i(D) of a complex D using simplicial homology, and show how to calculate them in terms of reduced combinatorial Laplacian operators. In particular, K_i(D) is a finite abelian group whose order enumerates the idimensional simplicial spanning trees of D. We present two interpretations of higher critical groups: one as higherdimensional flows, one as discrete analogues of the Chow groups of an algebraic variety.

Projection volumes of hyperplane arrangements with E. Swartz.
Discrete and Computational Geometry. 46, No. 3 (2011).
We prove that for any finite real hyperplane arrangement the average projection volumes of the maximal cones is given by the coefficients of the characteristic polynomial of the arrangement. This settles the conjecture of Drton and Klivans that this held for all finite real reflection arrangements. The methods used are geometric and combinatorial. As a consequence we determine that the angle sums of a zonotope are given by the characteristic polynomial of the order dual of the intersection lattice of the arrangement.

Cellular spanning trees and Laplacians of cubical complexes with A. Duval and J. Martin.
Advances in Applied Mathematics, Special issue in honor of Dennis Stanton, 46, (2011).
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.

A geometric interpretation of the characteristic polynomial of reflection arrangements with M. Drton.
Proceedings of the American Mathematical Society, Vol. 138. No. 8. 2010.
(The main conjecture of this work is solved in the paper "Projection Volumes of Hyperplane Arrangements" above.)
We consider projections of points onto fundamental chambers of finite real reflection groups. Our main result shows that for groups of type A_n, B_n, and D_n, the coefficients of the characteristic polynomial of the reflection arrangement are proportional to the spherical volumes of the sets of points that are projected onto faces of a given dimension. We also provide strong evidence that the same connection holds for the exceptional, and thus all, reflection groups. These results naturally extend those of De Concini and Procesi, Stembridge, and Denham which establish the relationship for 0dimensional projections. This work is also of interest for the field of orderrestricted statistical inference, where projections of random points play an important role.

Visibility constraints on features of 3D objects with R. Basri, P. Felzenszwalb, R. Girshick, and D. Jacobs.
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
To recognize threedimensional objects it is important to model how their appearances can change due to changes in viewpoint. A key aspect of this involves understanding which object features can be simultaneously visible under different viewpoints. Given a limited number of images of an object taken from unknown viewpoints, we would like to determine which subsets of features might be simultaneously visible in other views. This leads to the problem of determining whether a set of images, each containing a set of features, is consistent with a single 3D object. We assume that each feature is visible from a disk of viewpoints on the viewing sphere. In this case we show the problem is NPhard in general, but can be solved efficiently when all views come from a circle on the viewing sphere. We also give iterative algorithms that can handle noisy data and converge to locally optimal solutions in the general case. Our techniques can also be used to recover viewpoint information from the set of features that are visible in different image. We show that these algorithms perform well both on synthetic data and images from the COIL dataset.

Relations on generalized degree sequences with Kathryn Nyman and Bridget Tenner.
Discrete Mathematics, Volume 309, Issue 13 (2009).
We study degree sequences for simplicial and cubical posets, generalizing the well studied graphical degree sequences. Here we extend the more common generalization of vertextofacet degree sequences, by considering arbitrary facetoflag and flagtoflag degree sequences. In particular, these may be viewed as natural refinements of the flag fvector of the poset. We investigate properties and relations of these generalized degree sequences, proving linear relations between flag degree sequences in terms of the composition of rank jumps of the flag.

Simplicial spanning trees and generalized matrixtree theorems with Art Duval and Jeremy Martin.
Transactions of the American Mathematical Society 361 (2009).
We generalize the definition of a spanning tree from graphs to arbitrary simplicial complexes Delta, following G. Kalai. We show that the simplicial spanning trees of a complex can be counted, weighted by the squares of the orders of their topdimensional integral homology groups, using its Laplacian matrix. A more refined count of trees can be obtained be assigning a variable to each vertex of Delta and replacing the Laplacian with a monomial matrix. These results generalize the classical MatrixTree Theorem, and its weighted analogue, from graphs to complexes. 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. Our description of the eigenvalues generalizes previously known results for threshold graphs and for unweighted Laplacian eigenvalues.

Shifted set families, degree sequences, and plethysm with Vic Reiner.
The Electronic Journal of Combinatorics, Vol. 15(1), 2008.
We study, in three parts, degree sequences of kfamilies (or kuniform hypergraphs) and shifted kfamilies. The first part collects for the first time in one place, various implications such as: Threshold implies Uniquely Realizable implies DegreeMaximal implies Shifted, which are equivalent concepts for 2families (=simple graphs), but strict implications for kfamilies with k > 2. The implication that uniquely realizable implies degreemaximal seems to be new. The second part recalls Merris and Roby's reformulation of the characterization due to Ruch and Gutman for graphical degree sequences and shifted 2families. It then introduces two generalizations which are characterizations of shifted kfamilies. The third part recalls the connection between degree sequences of kfamilies of size m and the plethysm of elementary symmetric functions e_m[e_k]. It then uses highest weight theory to explain how shifted kfamilies provide the ``top part'' of these plethysm expansions, along with offering a conjecture about a further relation.

Threshold graphs, shifted complexes, and graphical complexes
Discrete Mathematics, vol. 307, no. 21, 2007.
We consider a variety of connections between threshold graphs, shifted complexes, and simplicial complexes naturally formed from a graph. These graphical complexes include the independent set, neighborhood, and dominance complexes. We present a number of structural results and relations among them including new characterizations of the class of threshold graphs.

The positive Bergman complex of an oriented matroid with Federico Ardila and Lauren Williams.
European Journal of Combinatorics, 27 (2006), 577591.
We study the positive Bergman complex B+(M) of an oriented matroid M, which is a certain subcomplex of the Bergman complex B(M) of the underlying unoriented matroid. The positive Bergman complex is defined so that given a linear ideal I with associated oriented matroid M_I, the positive tropical variety associated to I is equal to the fan over B+(M_I). Our main result is that a certain ``fine" subdivision of B+(M) is a geometric realization of the order complex of the proper part of the Las Vergnas face lattice of M. It follows that B+(M) is homeomorphic to a sphere. For the oriented matroid of the complete graph K_n, we show that the face poset of the ``coarse" subdivision of B+(K_n) is dual to the face poset of the associahedron A_{n2}, and we give a formula for the number of fine cells within a coarse cell.

The Bergman complex of a matroid and phylogenetic trees with Federico Ardila.
Journal of Combinatorial Theory, Series B, 96 (2006), 3849.
Also presented at FPSAC 2004.
We study the Bergman complex B(M) of a matroid M: a polyhedral complex which arises in algebraic geometry, but which we describe purely combinatorially. We prove that a natural subdivision of the Bergman complex of M is a geometric realization of the order complex of its lattice of flats. In addition, we show that the Bergman fan B'(K_n) of the graphical matroid of the complete graph K_n is homeomorphic to the space of phylogenetic trees T_n.

Shifted matroid complexes
preprint.
In this paper, we study the class of matroids whose independent set complexes are shifted. We prove two characterization theorems, one of which is constructive. In addition, we show this class is closed under taking minors and duality. Finally, we show results on shifted broken circuit complexes.

Obstructions to shiftedness
Discrete and Computational Geometry, vol 33, no. 3, 535545, 2005.
In this paper we show results on the combinatorial properties of shifted simplicial complexes. We prove two intrinsic characterization theorems for this class. The first theorem is in terms of a generalized vicinal preorder. It is shown that a complex is shifted if and only if the preorder is total. Building on this we characterize obstructions to shiftedness and prove there are finitely many in each dimension. In addition, we give results on the enumeration of shifted complexes and a connection to totally symmetric plane partitions.

Combinatorial Properties of Shifted
Complexes
Ph.D. Thesis, MIT, 2003.
A simplicial complex on n nodes is shifted if there exists a labelling of the nodes by 1 through n such that for any face, replacing any node of the face with a node of smaller label results in a collection which is also a face. A primary motivation for considering shifted complexes is a procedure called shifting. Shifting associates a shifted complex to any simplicial complex in a way which preserves meaningful information, while simplifying the structure of the complex. For example, shifting preserves the fvector of a complex but always reduces the topology to a wedge of spheres. Shifting has proved to be a successful tool for answering questions regarding fvectors. While most of the previous results on shifted complexes are algebraic or topological in nature, we explore the combinatorics of shifted complexes. We give intrinsic characterization theorems for shifted complexes and shifted matroid complexes. In addition, we show results on the enumeration of shifted complexes and connections to various combinatorial structures.