PUBLICATIONS
- The Mathematics of Chip-Firing (Book & Resources)
Published by CRC Press 2019.
The Mathematics of Chip-Firing provides an
introduction and overview of the fast growing area
of chip-firing. The book aims to give the reader
an appreciation for the richness and diversity of
chip-firing and a solid foundation to enter the
field as a researcher.
- Domino Tilings Beyond 2D with Nicolau Saldanha
To appear in the proceedings of the British Combinatorial Conference 2026.
Talk slides from Colloquium presentations Talk slides
- The Arboricity Polynomial with Felix Breuer
Preprint
We introduce a new matroid (graph) invariant, the arboricity polynomial. Given a matroid, the arboricity polynomial enumerates the number of covers of the ground set by disjoint independent sets. We establish the polynomiality of the counting function as a special case of a scheduling polynomial, i.e. both in terms of quasisymmetric functions and via Ehrhart theory of the normal fan of the matroid base polytope. We show basic properties of the polynomial and demonstrate that it is not a Tutte invariant. Namely, the arboricity polynomial does not satisfy a contraction / deletion recursion.
- Piecewise-exponential functions and Ehrhart fans with Melody Chan, Emily Clader and Dustin Ross
Preprint
This paper studies rings of integral piecewise-exponential functions on rational fans. Motivated by lattice-point counting in polytopes, we introduce a special class of unimodular fans called Ehrhart fans, whose rings of integral piecewise-exponential functions admit a canonical linear functional that behaves like a lattice-point count. In particular, we verify that all complete unimodular fans are Ehrhart and that the Ehrhart functional agrees with lattice-point counting in corresponding polytopes, which can otherwise be interpreted as holomorphic Euler characteristics of vector bundles on smooth toric varieties. We also prove that all Bergman fans of matroids are Ehrhart and that the Ehrhart functional in this case agrees with the Euler characteristic of matroids, introduced recently by Larson, Li, Payne, and Proudfoot. A key property that we prove about the Ehrharticity of fans is that it only depends on the support of the fan, not on the fan structure, thus providing a uniform framework for studying K-rings and Euler characteristics of complete fans and Bergman fans
- A Three-Regime Theorem for Flow Firing with Sarah Brauner, Galen Dorpalen-Barry, Selvi Kara, Lisa Schneider
The Electronic Journal of Combinatorics, Vol. 32, Issue 2, 2025.
Graphical chip-firing is a discrete dynamical system where chips are placed on the vertices of a graph and exchanged via simple firing moves. Recent work has sought to generalize chip-firing on graphs to higher dimensions, wherein graphs are replaced by cellular complexes and chip firing becomes flow-rerouting along the faces of the complex. Given such a system, it is natural to ask (1) whether this firing process terminates and (2) if it terminates uniquely (e.g. is confluent). In the graphical case, these questions were definitively answered by Bjorner--Lovasz--Shor, who developed three regimes which completely determine if a given system will terminate. Building on the work of Duval--Klivans--Martin and Felzenszwalb-Klivans, we answer these questions in a context called flow-firing, where the cellular complexes are 2-dimensional.
- Move and Configuration Posets with Patrick Liscio
Submitted for Publication
Lower Locally Distributive (LLD) lattices are a class of lattices that describe many types of combinatorial processes. While LLD lattices are traditionally defined in terms of their join-irreducibles, we provide a new characterization of LLD lattices in terms of S-colorings, or saturated L-colorings. S- and L-colorings color the edges of an LLD lattice's Hasse diagram in a way that has a natural interpretation in terms of moves of a locally confluent process. We show that each color of an S-coloring corresponds to the ``j^{th} move a given type'' in a process, allowing us to prove results about locally confluent processes by instead proving them in the context of LLD lattices. We use LLD lattice-based methods to prove new results on root system central-firing, as well as providing novel proofs of key results in labeled chip-firing and domino tilings.
- On the topology of no k-equal spaces with Yuliy Baryshnikov and Nicholas Kosar.
Advances in Applied Mathematics, Vol. 149, 2023.
We consider the topology of real no k-equal spaces via the theory of
cellular spanning trees. Our main theorem proves that the rank of the
(k-2)-dimensional homology of the no k-equal subspace of R is
equal to the number of facets in a k-dimensional spanning tree of the
k-skeleton of the n-dimensional hypercube.
- Eigenvalues and Critical Groups of Adinkras with Kevin Iga, Jordan Kostiuk and Chi Ho Yuen
Advances in Applied Mathematics vol. 143, 2022.
Adinkras are signed graphs used to study supersymmetry in physics. We provide an introduction to these objects, and study the properties of their signed adjacency and signed Laplacian matrices. These matrices each have exactly two distinct eigenvalues (of equal multiplicity), making Adinkras closely related to the notions of strongly regular graphs. We also study the critical groups of Adinkras, and in particular determine their odd components. A novel technique of independent interest is used which considers critical groups over polynomial rings.
- Supersymmetry and Representation Theory in Low Dimensions with Mathew Calkins and S. James Gates Jr.
Submitted for Publication.
Beginning from a discussion of the known most fundamental dynamical structures of the Standard Model of physics, extended into the realms of mathematics and theory by the concept of "supersymmetry" or "SUSY," an introduction to efforts to develop a complete representation theory is given. Techniques drawing from graph theory, coding theory, Coxeter Groups, Riemann surfaces, and computational approaches to the study of algebraic varieties are briefly highlighted as pathways for future exploration and progress.
- Clustering with Semidefinite Programming and Fixed Point Iteration with Pedro Felzenszwalb and Alice Paul.
Journal of Machine Learning Research, 23 (190) 2022.
We introduce a novel method for clustering using a semidefinite
programming (SDP) relaxation of the Max k-Cut problem. The
approach is based on a new methodology for rounding the solution
of an SDP relaxation using iterated linear optimization. We show the
vertices of the Max k-Cut SDP relaxation correspond to
partitions of the data into at most k sets. We also show the
vertices are attractive fixed points of iterated linear
optimization. Each step of this iterative procedure solves a
relaxation of the closest
vertex problem and leads to a new clustering problem where
the underlying clusters are more clearly defined.
Our experiments show that using fixed point
iteration for rounding the Max k-Cut SDP relaxation leads to
significantly better results when compared to randomized rounding.
- Iterated linear optimization with Pedro Felzenszwalb and Alice Paul.
Quarterly of Applied Mathematics, May 2021.
We introduce a fixed point iteration process built on optimization of a linear function over a compact domain. We prove the process always converges to a fixed point and explore the set of fixed points in various convex sets. In particular, we consider elliptopes and derive an algebraic characterization of their fixed points. We show that the attractive fixed points of an elliptope are exactly its vertices. Finally, we discuss how fixed point iteration can be used for rounding the solution of a semidefinite programming relaxation.
- Domino tilings and flips in dimensions 4 and higher with Nicolau Saldanha.
Algebraic Combinatorics, Vol. 5, no. 1, 2022.
Additional materials for the computations in this paper can be found here: source code
In this paper we consider domino tilings
of bounded regions in dimension n \geq 4. We define the twist of such a tiling,
an elements of ZZ/(2),
and prove it is invariant under flips,
a simple local move in the space of tilings.
We investigate which regions D are regular, i.e. whenever two
tilings t_0 and t_1 of D \times [0,N] have the same twist
then t_0 and t_1 can be joined by a sequence of flips provided
some extra vertical space is allowed. We prove that all boxes are regular except D = [0,2]^3.
Furthermore, given a regular region D,
we show that there exists a value M
(depending only on D) such that
if t_0 and t_1 are tilings of equal twist of D \times [0,N]
then the corresponding tilings can be joined
by a finite sequence of flips in D \times [0,N+M].
As a corollary we deduce that, for regular D and large N,
the set of tilings of D \times [0,N]
has two twin giant components under flips,
one for each value of the twist.
- Confluence in Labeled Chip-Firing with Patrick Liscio.
Journal of Combinatorial Theory, Series A, vol. 186, 2022
Extended abstract appeared in FPSAC 2020. Poster
In 2016, Hopkins, McConville, and Propp proved that labeled
chip-firing on a line always leaves the chips in sorted order if the
number of chips is even. We present a novel proof of this
result. We then apply our methods to resolve a number of related
conjectures concerning the confluence of labeled chip-firing
systems.
- Flow-firing processes with Pedro Felzenszwalb.
Journal of Combinatorial Theory, Series A, vol. 177, 2021
We consider a discrete non-deterministic flow-firing process
for rerouting flow on the edges of a planar complex. The process is
an instance of higher-dimensional chip-firing. In the flow-firing
process, flow on the edges of a complex is repeatedly diverted across
the faces of the complex. For non-conservative 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 connectivity of three-dimensional tilings with Juliana Freire, Pedro H. Milet and Nicolau C. Saldanha.
Transactions of the American Mathematical Society, Vol. 375, No. 3, 2022.
We consider domino tilings of three-dimensional cubiculated manifolds
with or without boundary,
including subsets of Euclidean space and three-dimensional 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.
-
Chip firing on Dynkin diagrams and McKay Quivers with G. Benkart and V. Reiner.
Mathematische Zeitschrift, 290(1-2), 2018.
Two classes of avalanche-finite matrices and their critical groups
(integer cokernels) are studied from the viewpoint of
chip-firing/sandpile dynamics, namely, the Cartan matrices of
finite root systems and the McKay-Cartan 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 McKay-Cartan
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.
-
The Partitionability Conjecture with Art Duval and Jeremy Martin.
Notices of the AMS, 64(2), 117-122, 2017.
In 1979 Richard Stanley made the following
conjecture: Every Cohen-Macaulay 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
(Cohen-Macaulayness). 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.
-
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.
-
Chip-firing on general invertible matrices with J. Guzman.
SIAM Journal on Discrete Mathematics, 30(2), 2016.
We propose a generalization of the graphical chip-firing 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
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.
-
A non-partitionable Cohen-Macaulay simplicial complex with A. Duval, B. Goeckner and J. Martin.
Advances in Mathematics, Vol. 299, 2016.
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.
-
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 three-dimensional 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.
-
Chip-firing and energy minimization on M-matrices with J. Guzman.
Journal of Combinatorial Theory, Series A, Volume 132, May 2015, Pages 14-31.
We consider chip-firing dynamics defined by arbitrary M-matrices.
M-matrices 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 M-matrix, we show that there exists a unique
energy minimizing configuration in each equivalence class defined by
the matrix.
We define the class of z-superstable configurations which satisfy
a strictly stronger stability requirement than superstable
configurations (equivalently G-parking functions or reduced divisors). We
prove that for any M-matrix, the z-superstable configurations
coincide with the energy minimizing configurations. Moreover, we
prove that the z-superstable configurations are in simple duality
with critical configurations. Thus for all avalanche-finite systems
(including all directed graphs with a global sink) there exist unique
critical, energy minimizing and z-superstable configurations. The critical configurations are
in simple duality with energy minimizers which coincide with z-superstable 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 Billera-Jia-Reiner 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 non-commuting 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 h-vector 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 h-vector of the scheduling polynomial.
-
A Cheeger-Type 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 Cheeger-type 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, 1-31, 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 h-vector 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 Billera-Jia-Reiner quasisymmetric function all as
special instances.
-
A conjecture on G-parking functions and G-Shi 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 G-Shi hyperplane
arrangement of an arbitrary graph G, and compare the regions of the
complement of this arrangement to G-parking functions, a well-studied
generalization of parking functions to arbitrary graphs. In
particular, while the Pak-Stanley labels of regions are no longer
necessarily unique, we conjecture that the set of different
Pak-Stanley labels of regions of the G-Shi 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
i-dimensional simplicial spanning trees of D. We present
two interpretations of higher critical groups: one as higher-dimensional 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 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.
-
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
0-dimensional projections. This work is also of interest for the field
of order-restricted 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 three-dimensional 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 NP-hard 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 vertex-to-facet degree sequences, by considering arbitrary
face-to-flag and flag-to-flag degree sequences. In particular, these may be
viewed as natural refinements of the flag f-vector 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 matrix-tree 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 top-dimensional 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 Matrix-Tree 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 k-families (or k-uniform
hypergraphs) and shifted k-families. The first part collects for the first
time in one place, various implications such as: Threshold implies Uniquely
Realizable implies Degree-Maximal implies Shifted, which are equivalent
concepts for 2-families (=simple graphs), but strict implications for
k-families with k > 2. The implication that uniquely realizable implies
degree-maximal 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 2-families. It then introduces two
generalizations which are characterizations of shifted k-families. The
third part recalls the connection between degree sequences of k-families of
size m and the plethysm of elementary symmetric functions e_m[e_k]. It then
uses highest weight theory to explain how shifted k-families 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), 577-591.
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_{n-2}, 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), 38-49.
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, 535-545, 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 f-vector 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 f-vectors.
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.