Inequalities for the h-Vectors and Flag h-Vectors of Geometric Lattices

We prove that the order complex of a geometric lattice has a convex ear decomposition. As a consequence, if (L) is the order complex of a rank (r + 1) geometric lattice L, then for all i r/2 the h-vector of (L) satisfies h_i-1 h_i and h_i h_r-i. We also obtain several inequalities for the flag h-vector of (L) by analyzing the weak Bruhat order of the symmetric group. As an application, we obtain a zonotopal cd-analogue of the Dowling–Wilson characterization of geometric lattices which minimize Whitney numbers of the second kind. In addition, we are able to give a combinatorial flag h-vector proof of h_i-1 h_i when i (2/7)(r + (5/2)).     

Pure O-Sequences and Matroid h-Vectors

We study Stanley’s long-standing conjecture that the h-vectors of matroid simplicial complexes are pure O-sequences. Our method consists of a new and more abstract approach, which shifts the focus from working on constructing suitable artinian level monomial ideals, as often done in the past, to the study of properties of pure O-sequences. We propose a conjecture on pure O-sequences and settle it in small socle degrees. This allows us to prove Stanley’s conjecture for all matroids of rank 3. At the end of the paper, using our method, we discuss a first possible approach to Stanley’s conjecture in full generality. Our technical work on pure O-sequences also uses very recent results of the third author and collaborators.     

Cubical surfaces and congruences

A survey of results of investigations of families of planar curves of third order in three-dimensional projective space is presented.Translated from Itogi Nauki i Tekhniki, Seriya Problemy Geometrii, Vol. 18, pp. 143–164, 1986.     

Neighborly Cubical Polytopes

Neighborly cubical polytopes exist: for any n≥ d≥ 2r+2 , there is a cubical convex d -polytope C _d ⁿ whose r -skeleton is combinatorially equivalent to that of the n -dimensional cube. This solves a problem of Babson, Billera, and Chan. Kalai conjectured that the boundary of a neighborly cubical polytope C _d ⁿ maximizes the f -vector among all cubical (d-1) -spheres with 2 ⁿ vertices. While we show that this is true for polytopal spheres if n≤ d+1 , we also give a counterexample for d=4 and n=6 . Further, the existence of neighborly cubical polytopes shows that the graph of the n -dimensional cube, where n\ge5 , is ``dimensionally ambiguous' in the sense of Grünbaum. We also show that the graph of the 5 -cube is ``strongly 4 -ambiguous.' In the special case d=4 , neighborly cubical polytopes have f ₃ =(f ₀ /4) log ₂ (f ₀ /4) vertices, so the facet—vertex ratio f ₃ /f ₀ is not bounded; this solves a problem of Kalai, Perles, and Stanley studied by Jockusch. Received December 30, 1998. Online publication May 15, 2000.     

Cubical homotopical algebra and cochain algebras

Basic homotopical algebra is developed in a setting consisting of a cubical monad [G3], i.e. a cylinder endofunctor I, equipped with connections g^–, g⁺: I² I, and— possibly—with symmetries extending the reversion r: II and the interchange s:I²I² of the standard topological case. Our study is mostly concerned with the Puppe sequence of a map f and its comparison with the sequence of iterated homotopy cokernels off. As an application, the homotopy structure of cochain algebras is studied in the present frame, through the cubical co-monad of the path functor P and the left adjoint cylinder functor I.Work partially supported by MURST Research Projects.     

The Cubical Matching Complex

Given a bipartite planar graph embedded in the plane, we define its cubical matching complex. By combining results of Kalai and Propp, we show that the cubical matching complex is collapsible. As a corollary, we obtain that a simply connected region R in the plane that can be tiled with lozenges and hexagons satisfies ${f_0 - f_1 + f_2 - \cdots = 1}$ , where f _i is the number of tilings with i hexagons. The same relation holds for a region tiled with dominoes and 2 × 2 squares. Furthermore, we show for a region that can be tiled with dominoes, that each link of the associated cubical complex ${\mathcal{C}(R)}$ is either collapsible or homotopy equivalent to a sphere.     

Weakly Regular Subdivisions

It is shown that 2-dimensional subdivisions can be made regular by moving their vertices within parallel 1-dimensional spaces. As a consequence, any 2-dimensional subdivision is projected from the boundary complex of a 4-polytope.     

Cubical structures, homotopy theory

We investigate the categories of semi-cubical complexes with or without degeneracies. We prove that the Kan condition does not imply that a semi-cubical complex admits degeneracies and that, unlike the simplicial case, there is no cubical approximation theorem while we prove such a theorem for semi-cubical complexes with degeracies. Entrata in Redazione il 1 settembre 1998. Ricevuta versione finale il 3 maggio 1999.     

Subdivisions of Transitive Tournaments

We prove that, for r ≥ 2 andn ≥ n(r), every directed graph with n vertices and more edges than the r -partite Turán graph T(r, n) contains a subdivision of the transitive tournament on r + 1 vertices. Furthermore, the extremal graphs are the orientations ofT (r, n) induced by orderings of the vertex classes.     

Subdivisions in apex graphs

The Kelmans-Seymour conjecture states that every 5-connected nonplanar graph contains a subdivided K ₅. Certain questions of Mader propose a “plan” towards a possible resolution of this conjecture. One part of this plan is to show that every 5-connected nonplanar graph containing K^-₄K^{-}_{4} or K _2,3 as a subgraph has a subdivided K ₅. Recently, Ma and Yu showed that every 5-connected nonplanar graph containing K^-₄K^{-}_{4} as a subgraph has a subdivided K ₅. We take interest in K _2,3 and prove that every 5-connected nonplanar apex graph containing K _2,3 as a subgraph contains a subdivided K ₅. The result of Ma and Yu can be used in a short discharging argument to prove that every 5-connected nonplanar apex graph contains a subdivided K ₅; here we propose a longer proof whose merit is that it avoids the use of discharging and employs a more structural approach; consequently it is more amenable to generalization.     

Lower Bounds for Cubical Pseudomanifolds

It is verified that the number of vertices in a d-dimensional cubical pseudomanifold is at least 2 ^d+1. Using Adin’s cubical h-vector, the generalized lower bound conjecture is established for all cubical 4-spheres, as well as for some special classes of cubical spheres in higher dimensions.     

Subdivisions,parity and well-covered graphs

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm) characterization of the class called 3-separable graphs. Also we consider parity graphs studied by Finbow and Hartnell and answer the question posed by them (Ars. Combin. 40 (1995)) by proving, among other results, that the decision problem: “given a graph G which is a parity graph, is G also well-covered graph?” is in the class CO-NPC. In addition we supply some complexity results that answer some problems due to Plummer (Quaestiones Math. 16 (1993)) and Finbow, Hartnell, and Whitehead (Discrete Math. 125 (1994)). © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 85–94, 1997     

Cubical 4-Polytopes with Few Vertices

A cubical polytope is a convex polytope all of whose facets are conbinatorial cubes. A d-polytope Pis called almost simple if, in the graph of P, each vertex of Pis d-valent of (d+ 1)-valent. It is known that, for d> 4, all but one cubical d-polytopes with up to 2^d+1vertices are almost simple, which provides a complete enumeration of all the cubical d-polytopes with up to 2^d+1vertices. We show that this result is also true for d=4.     

Subdivisions of Toric Complexes

We introduce toric complexes as polyhedral complexes consisting of rational cones together with a set of integral generators for each cone, and we define their associated face rings. Abstract simplicial complexes and rational fans can be considered as toric complexes, and the face ring for toric complexes extends Stanley and Reisner’s face ring for abstract simplicial complexes [20] and Stanley’s face ring for rational fans [21]. Given a toric complex with defining ideal I for the face ring we give a geometrical interpretation of the initial ideals of I with respect to weight orders in terms of subdivisions of the toric complex generalizing a theorem of Sturmfels in [23]. We apply our results to study edgewise subdivisions of abstract simplicial complexes.     

Zonotopal Subdivisions of Cyclic Zonotopes

The cyclic zonotope (n, d) is the zonotope in ^d generated by any n distinct vectors of the form (1, t, t ²,..., t ^d–1). It is proved that the refinement poset of all proper zonotopal subdivisions of (n, d) which are induced by the canonical projection : (n, d) (n, d), in the sense of Billera and Sturmfels, is homotopy equivalent to a sphere and that any zonotopal subdivision of (n, d) is shellable. The first statement gives an affirmative answer to the generalized Baues problem in a new special case and refines a theorem of Sturmfels and Ziegler on the extension space of an alternating oriented matroid. An important ingredient in the proofs is the fact that all zonotopal subdivisions of (n, d) are stackable in a suitable direction. It is shown that, in general, a zonotopal subdivision is stackable in a given direction if and only if a certain associated oriented matroid program is Euclidean, in the sense of Edmonds and Mandel.