Caroline J Klivans

A Three-Regime Theorem for Flow Firing with Sarah Brauner, Galen Dorpalen-Barry, Selvi Kara, Lisa Schneider
Submitted for Publication

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.
To appear Advances in Applied Mathematics 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.

Illustrating Mathematics: AMS book entry with Pedro Felzenszwalb and Martin Skrodzki
Illustrating Mathematics 3D chip-firing: ICERM working group
Three dimensional pulse (Lower image)

In Fall of 2019, ICERM hosted the semester program Illustrating Mathematics.

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.

PUBLICATIONS