Caroline (Carly) Klivans

Papers

A Quasisymmetric Function for Generalized Permutahedra
with M. Aguiar and L. Billera.
Talk slides from BIRS pdf

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.

Critical Groups of Simplicial Complexes(As in the chip firing game or abelian sandpile model.)
with A. Duval and J. Martin.
To appear: Annals of Combinatorics pdf
Also presented at FPSAC (Formal Power Series and Algebraic Combinatorics) 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, Vol 46, No. 3. 2011. pdf

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, Vol. 46, special issue in honor of Dennis Stanton, 2011. pdf

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. pdf
(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. pdf

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). pdf

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.
Trans. Amer. Math. Soc. 361 (2009). pdf

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. ps pdf

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. ps pdf

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. ps pdf

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. pdf
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. ps pdf

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. ps pdf

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. ps pdf

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.