Dirac’s Theorem on Simplicial Matroids

We introduce the notion of k-hyperclique complexes, i.e., the largest simplicial complexes on the set [n] with a fixed k-skeleton. These simplicial complexes are a higher-dimensional analogue of clique (or flag) complexes (case k = 2) and they are a rich new class of simplicial complexes. We show that Dirac’s theorem on chordal graphs has a higher-dimensional analogue in which graphs and clique complexes get replaced, respectively, by simplicial matroids and k-hyperclique complexes. We prove also a higher-dimensional analogue of Stanley’s reformulation of Dirac’s theorem on chordal graphs.      

Law of large numbers for Betti numbers of homogeneous and spatially independent random simplicial complexes

The Linial–Meshulam complex model is a natural higher dimensional analog of the Erd?s–Rényi graph model. In recent years, Linial and Peled established a limit theorem for Betti numbers of Linial–Meshulam complexes with an appropriate scaling of the underlying parameter. The present article aims to extend that result to more general random simplicial complex models. We introduce a class of homogeneous and spatially independent random simplicial complexes, including the Linial–Meshulam complex model and the random clique complex model as special cases, and we study the asymptotic behavior of their Betti numbers. Moreover, we obtain the convergence of the empirical spectral distributions of their Laplacians. A key element in the argument is the local weak convergence of simplicial complexes. Inspired by the work of Linial and Peled, we establish the local weak limit theorem for homogeneous and spatially independent random simplicial complexes.     

Symmetry,oriented matroids and two conjectures of Michel Las Vergnas

The paper has two parts. In the first part we survey the existing results on the cube conjecture of Las Vergnas. This conjecture claims that the orientation of the matroid of the cube is determined by the symmetries of the underlying matroid. The second part deals with Euclidean representations of matroids as geometric simplicial complexes defined by symmetry properties abstracting those of zonotopes. Both sections involve arguments concerning simplicial regions illustrating, once more, the fundamental importance of the simplex conjecture of Las Vergnas.     

Quaternionic geometry of matroids

Building on a recent paper [8], here we argue that the combinatorics of matroids are intimately related to the geometry and topology of toric hyperkähler varieties. We show that just like toric varieties occupy a central role in Stanley’s proof for the necessity of McMullen’s conjecture (or g-inequalities) about the classification of face vectors of simplicial polytopes, the topology of toric hyperkähler varieties leads to new restrictions on face vectors of matroid complexes. Namely in this paper we will give two proofs that the injectivity part of the Hard Lefschetz theorem survives for toric hyperkähler varieties. We explain how this implies the g-inequalities for rationally representable matroids. We show how the geometrical intuition in the first proof, coupled with results of Chari [3], leads to a proof of the g-inequalities for general matroid complexes, which is a recent result of Swartz [20]. The geometrical idea in the second proof will show that a pure O-sequence should satisfy the g-inequalities, thus showing that our result is in fact a consequence of a long-standing conjecture of Stanley.     

Skew partial fields,multilinear representations of matroids,and a matrix tree theorem

We extend the notion of representation of a matroid to algebraic structures that we call skew partial fields. Our definition of such representations extends Tutte?s definition, using chain groups. We show how such representations behave under duality and minors, we extend Tutte?s representability criterion to this new class, and we study the generator matrices of the chain groups. An example shows that the class of matroids representable over a skew partial field properly contains the class of matroids representable over a skew field. Next, we show that every multilinear representation of a matroid can be seen as a representation over a skew partial field. Finally we study a class of matroids called quaternionic unimodular. We prove a generalization of the matrix tree theorem for this class.     

Chorded complexes and a necessary condition for a monomial ideal to have a linear resolution

In this paper we extend one direction of Fröberg?s theorem on a combinatorial classification of quadratic monomial ideals with linear resolutions. We do this by generalizing the notion of a chordal graph to higher dimensions with the introduction of d-chorded and orientably-d-cycle-complete simplicial complexes. We show that a certain class of simplicial complexes, the d-dimensional trees, correspond to ideals having linear resolutions over fields of characteristic 2 and we also give a necessary combinatorial condition for a monomial ideal to be componentwise linear over all fields.     

Differential graded versus simplicial categories

We establish a connection between differential graded and simplicial categories by constructing a three-step zig-zag of Quillen adjunctions relating the homotopy theories of the two. In an intermediate step, we extend the Dold-Kan correspondence to a Quillen equivalence between categories enriched over non-negatively graded complexes and categories enriched over simplicial modules. As an application, we obtain a simple calculation of Simpson's homotopy fiber, which is known to be a key step in the construction of a moduli stack of perfect complexes on a smooth projective variety.     

Note on binary simplicial matroids

Using an earlier characterization of simplicial hypergraphs we obtain a characterization of binary simplicial matroids in terms of the existence of a special base.     

On the matroids in which all hyperplanes are binary

In this paper, it is shown that, for a minor-closed class of matroids, the class of matroids in which every hyperplane is in is itself minor-closed and has, as its excluded minors, the matroids U_1.1 N such that N is an excluded minor for . This result is applied to the class of matroids of the title, and several alternative characterizations of the last class are given.     

Mutation Polynomials and Oriented Matroids

Several polynomials are of use in various enumeration problems concerning objects in oriented matroids. Chief among these is the Radon catalog. We continue to study these, as well as the total polynomials of uniform oriented matroids, by considering the effect on them of mutations of the uniform oriented matroid. The notion of a ``mutation polynomial' is introduced to facilitate the study. The affine spans of the Radon catalogs and the total polynomials in the appropriate rational vector spaces of polynomials are determined, and bases for the Z -modules generated by the mutation polynomials are found. The Radon polynomials associated with alternating oriented matroids are described; it is conjectured that a certain extremal property, like that held by cyclic polytopes among simplicial polytopes, is possessed by them. Received November 20, 1998, and in revised form August 21, 1999. Online publication May 19, 2000.     

Finite filtrations of modules and shellable multicomplexes

We introduce pretty clean modules, extending the notion of clean modules by Dress, and show that pretty clean modules are sequentially Cohen–Macaulay. We also extend a theorem of Dress on shellable simplicial complexes to multicomplexes.     

Enumerating bases of self-dual matroids

We define involutively self-dual matroids and prove that an enumerator for their bases is the square of a related enumerator for their self-dual bases. This leads to a new proof of Tutte's theorem that the number of spanning trees of a central reflex is a perfect square, and it solves a problem posed by Kalai about higher dimensional spanning trees in simplicial complexes. We also give a weighted version of the latter result.We give an algebraic analogue relating to the critical group of a graph, a finite abelian group whose order is the number of spanning trees of the graph. We prove that the critical group of a central reflex is a direct sum of two copies of an abelian group, and conclude with an analogous result in Kalai's setting.     

Oriented matroids with few mutations

This paper defines a “connected sum” operation on oriented matroids of the same rank. This construction is used for three different applications in rank 4. First it provides nonrealizable pseudoplane arrangements with a low number of simplicial regions. This contrasts the case of realizable hyperplane arrangements: by a classical theorem of Shannon every arrangement ofn projective planes in ℝP ^d-1 contains at leastn simplicial regions and every plane is adjacent to at leastd simplicial regions [17], [18]. We construct a class of uniform pseudoarrangements of 4n pseudoplanes in ℝP³ with only 3n+1 simplicial regions. Furthermore, we construct an arrangement of 20 pseudoplanes where one plane is not adjacent to any simplicial region. Finally we disprove the “strong-map conjecture” of Las Vergnas [1]. We describe an arrangement of 12 pseudoplanes containing two points that cannot be simultaneously contained in an extending hyperplane.     

Polyhedral Finsler spaces with locally unique geodesics

We study Finsler PL spaces, that is simplicial complexes glued out of simplices cut off from some normed spaces. We are interested in the class of Finsler PL spaces featuring local uniqueness of geodesics (for complexes made of Euclidean simplices, this property is equivalent to local CAT(0)). Though non-Euclidean normed spaces never satisfy CAT(0), it turns out that they share many common features. In particular, a globalization theorem holds: in a simply-connected Finsler PL space local uniqueness of geodesics implies the global one. However the situation is more delicate here: some basic convexity properties do not extend to the PL Finsler case.     

Strong Homotopy Types,Nerves and Collapses

We introduce the theory of strong homotopy types of simplicial complexes. Similarly to classical simple homotopy theory, the strong homotopy types can be described by elementary moves. An elementary move in this setting is called a strong collapse and it is a particular kind of simplicial collapse. The advantage of using strong collapses is the existence and uniqueness of cores and their relationship with the nerves of the complexes. From this theory we derive new results for studying simplicial collapsibility with a different point of view. We analyze vertex-transitive simplicial G-actions and prove a particular case of the Evasiveness conjecture for simplicial complexes. Moreover, we reduce the general conjecture to the class of minimal complexes. We also strengthen a result of V. Welker on the barycentric subdivision of collapsible complexes. We obtain this and other results on collapsibility of polyhedra by means of the characterization of the different notions of collapses in terms of finite topological spaces.     

Relations on generalized degree sequences

We study degree sequences for simplicial posets and polyhedral complexes, 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 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. As a corollary, we recover an f-vector inequality on simplicial posets first shown by Stanley.     

Nonrealizability proofs in computational geometry

This paper deals with a class of computational problems in real algebraic geometry. We introduce the concept of final polynomials as a systematic approach to prove nonrealizability for oriented matroids and combinatorial geometries.Hilbert's Nullstellensatz and its real analogue imply that an abstract geometric object is either realizable or it admits a final polynomial. This duality has first been applied by Bokowski in the study of convex polytopes [7] and [11], but in these papers the resulting final polynomials were given without their derivations.It is the objective of the present paper to fill that gap and to describe an algorithm for constructing final polynomials for a large class of nonrealizable chirotopes. We resolve a problem posed in [10] by proving that not every realizable simplicial chirotope admits a solvability sequence. This result shows that there is no easy combinatorial method for proving nonrealizability and thus justifies our final polynomial approach.     

Matching Trees for Simplicial Complexes and Homotopy Type of Devoid Complexes of Graphs

We generalize some homotopy calculation techniques such as splittings and matching trees that are introduced for the computations in the case of the independence complexes of graphs to arbitrary simplicial complexes. We then exemplify their efficiency on some simplicial complexes, the devoid complexes of graphs, \(\mathcal {D}(G;\mathcal {F})\) whose faces are vertex subsets of G that induce \(\mathcal {F}\)-free subgraphs, where G is a multigraph and \(\mathcal {F}\) is a family of multigraphs. Additionally, we compute the homotopy type of dominance complexes of chordal graphs.     

A Decomposition Theorem for Binary Matroids with no Prism Minor

The prism graph is the dual of the complete graph on five vertices with an edge deleted, K ₅\ e. In this paper we determine the class of binary matroids with no prism minor. The motivation for this problem is the 1963 result by Dirac where he identified the simple 3-connected graphs with no minor isomorphic to the prism graph. We prove that besides Dirac’s infinite families of graphs and four infinite families of non-regular matroids determined by Oxley, there are only three possibilities for a matroid in this class: it is isomorphic to the dual of the generalized parallel connection of F ₇ with itself across a triangle with an element of the triangle deleted; it’s rank is bounded by 5; or it admits a non-minimal exact 3-separation induced by the 3-separation in P ₉. Since the prism graph has rank 5, the class has to contain the binary projective geometries of rank 3 and 4, F ₇ and PG(3, 2), respectively. We show that there is just one rank 5 extremal matroid in the class. It has 17 elements and is an extension of R ₁₀, the unique splitter for regular matroids. As a corollary, we obtain Mayhew and Royle’s result identifying the binary internally 4-connected matroids with no prism minor Mayhew and Royle (Siam J Discrete Math 26:755–767, 2012).     

Buchsbaum* complexes

A class of finite simplicial complexes, which we call Buchsbaum* over a field, is introduced. Buchsbaum* complexes generalize triangulations of orientable homology manifolds as well as doubly Cohen-Macaulay complexes. By definition, the Buchsbaum* property depends only on the geometric realization and the field. Characterizations in terms of simplicial homology are given. It is proved that Buchsbaum* complexes are doubly Buchsbaum. Various constructions, among them one which generalizes convex ear decompositions, are shown to yield Buchsbaum* simplicial complexes. Graph theoretic and enumerative properties of Buchsbaum* complexes are investigated.