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

An Inequality for the Möbius Function of a Geometric Lattice

An inequality is derived for the Möbius function of a finite geometric lattice L. Equality is characterized by the modularity of certain elements of L. Applications are given to other inequalities involving Whitney numbers, ordered bases, and maximal chains.     

Families of Tight Inequalities for Polytopes

We use the Billera-Liu algebra to show how the flag f-vectors of several special classes of polytopes fit into the closed convex hull of the flag f-vectors of all polytopes. In particular, we describe inequalities that define the faces of the closed convex hull of the flag f-vectors of all d-polytopes that are spanned by the flag f-vectors of simplicial, simple, k-simplicial, and k-simple d-polytopes. We also describe inequalities that define the face of the closed convex hull of the flag f-vectors of all d-zonotopes spanned by the flag f-vectors of cubical d-zonotopes, and give an upper bound on the dimension of the span of the flag f-vectors of k-cubical zonotopes. Finally, we strengthen some previously known inequalities for flag f-vectors of zonotopes.     

The slimmest arrangements of hyperplanes

We show how the results of Dowling and Wilson on Whitney numbers in ‘The slimmest geometric lattices’ imply minimum values for the numbers of k-dimensional flats and d-dimensional cells of a projective d-arrangement of hyperplanes and for the number of d-cells missed by an extra hyperplane. Their theorems also characterize the extremal arrangements. We extend their lattice results to doubly indexed Whitney numbers; thence we obtain minima for the number of k-dimensional cells and the number of pairs of flats with x \(\subseteq\) y and dim x=k, dim y=l. The lower bounds are in terms of the rank and number of points of the geometric lattice, or the dimension d and the number of hyperplanes of the arrangement. The minima for k-cells were conjectured by Grünbaum; R. W. Shannon proved the minima for k-dimensional flats and cells and characterized attainment for the latter by a more strictly geometric, non-latticial technique.     

Doubling Convex Sets in Lattices: Characterizations and Recognition Algorithms

We characterize lattices obtained from another lattice by a doubling of a convex set. This gives rise to a characterization of the class CN of lattices obtained by doublings of connected and convex sets when starting from a two-element lattice, and from this characterization result we derive an efficient recognition algorithm. This algorithm can be directly applied to the recognition of lattices in the subclasses of CN defined by giving some additionnal constraints on the convex sets used in the doublings.     

Enumeration in Convex Geometries and Associated Polytopal Subdivisions of Spheres

We construct CW spheres from the lattices that arise as the closed sets of a convex closure, the meet-distributive lattices. These spheres are nearly polytopal, in the sense that their barycentric subdivisions are simplicial polytopes. The complete information on the numbers of faces and chains of faces in these spheres can be obtained from the defining lattices in a manner analogous to the relation between arrangements of hyperplanes and their underlying geometric intersection lattices.     

A note on the characteristic classes of non-positively curved manifolds

In this expository note, we give a simple conceptual proof of the Hirzebruch proportionality principle for Pontrjagin numbers of non-positively curved locally symmetric spaces. We also establish (non)-vanishing results for Stiefel–Whitney and Pontrjagin numbers of (finite covers of) the Gromov–Thurston examples of compact negatively curved manifolds. A byproduct of our argument gives a constructive proof of a well-known result of Rohlin: every closed orientable 3-manifold bounds orientably. We mention some geometric corollaries: a lower bound for degrees of covers having tangential maps to the non-negatively curved duals and estimates for the complexity of some representations of certain uniform lattices.     

Functional completions of Archimedean vector lattices

We study completions of Archimedean vector lattices relative to any nonempty set of positively homogeneous functions on finite-dimensional real vector spaces. Examples of such completions include square mean closed and geometric mean closed vector lattices, amongst others. These functional completions also lead to a universal definition of the complexification of any Archimedean vector lattice and a theory of tensor products and powers of complex vector lattices in a companion paper.     

A condition for modular lattices

This paper proves that a geometric lattice of rank n is a modular lattice if its every maximal chain contains a modular element of rank greater than 1 and less than n. This result is generalized to a more general lattices of finite rank. The first author is partially supported by the National Natural Science Foundation of China (Grant No. 10471016).     

Zusammenhängende Untergruppen von pro-Lieschen Gruppen

In this paper we consider the lattice G of all closed connected subgroups of pro-Lie groups G, which seems to have in some sense a more geometric nature than the full lattice of all closed subgroups. We determine those pro-Lie groups whose lattice shares one of the elementary geometric lattice properties, such as the existence of complements and relative complements, semi-modularity and its dual, the chain condition, self-duality and related ones. Apart from these results dealing with subgroup lattices we also get two structure theorems, one saying that maximal closed analytic subgroups of Lie groups actually are maximal among all analytic subgroups, the other that each connected abelian pro-Lie group is a direct product of a compact group with copies of the reals.     

A counterexample to the generalization of Sperner's theorem

It has been conjectured that the analog of Sperner's theorem on non-comparable subsets of a set holds for arbitrary geometric lattices, namely, that the maximal number of non-comparable elements in a finite geometric lattice is max w(k), where w(k) is the number of elements of rank k. It is shown in this note that the conjecture is not true in general. A class of geometric lattices, each of which is a bond lattice of a finite graph, is constructed in which the conjecture fails to hold.     

Lattice ordered effect algebras

The purpose of this paper is to discuss some structural properties of lattice ordered effect algebras. We will use these structural properties to find certain lattices and classes of lattices that do not admit an effect algebra structure. Finally, using these structural properties, we will show that if L is the face lattice of a convex polytope in $ R^3 $ with more than 3 vertices, then L does not admit an effect algebra structure.Dedicated to the memory of Gian-Carlo Rota     

A note on the split rank of intersection cuts

In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It is then shown that élog₂ (l)ù{\lceil \log_2 (l)\rceil} is a lower bound on the split rank of the intersection cut, where l is the number of integer points lying on the boundary of the restricted lattice-free set satisfying the condition that no two points lie on the same facet of the restricted lattice-free set. The use of this result is illustrated by obtaining a lower bound of élog₂( n+1) ù{\lceil \log_2( n+1) \rceil} on the split rank of n-row mixing inequalities.     

Exploring the Relationship Between Max-Cut and Stable Set Relaxations

The max-cut and stable set problems are two fundamental -hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.     

Homotopy types of group lattices

In this article, we study group lattices using the ideas of K. S. Brown and D. Quillen of associating a certain topological space to a partially ordered set. We determine the exact homotopy type for the subgroup lattice of PSL(2, 7), find a connection between different group lattices, and obtain some estimates for the Betti numbers of these lattices using the spectral sequence method.     

Consistent lattices and Steinitz spaces

It is well-known that a finite lattice L is isomorphic to the lattice of flats of a matroid if and only if L is geometric. A result due to Edelman (see [1], Theorem 3.3) states that a lattice is meet-distributive if and only if it is isomorphic to the lattice of all closed sets of a convex geometry. In this note we prove that a finite lattice is the lattice of closed sets of a closure space with the Steinitz exchange property if and only if it is a consistent lattice. Received February 28, 1997; accepted in final form February 2, 1998.     

The lattice of closure relations on a poset

In this paper we show that the set of closure relations on a finite posetP forms a supersolvable lattice, as suggested by Rota. Furthermore this lattice is dually isomorphic to the lattice of closed sets in a convex geometry (in the sense of Edelman and Jamison [EJ]). We also characterize the modular elements of this lattice (whenP has a greatest element) and compute its characteristic polynomial.Presented by R. W. Quackenbush.     

Combinatorial representation and convex dimension of convex geometries

We develop a representation theory for convex geometries and meet distributive lattices in the spirit of Birkhoff's theorem characterizing distributive lattices. The results imply that every convex geometry on a set X has a canonical representation as a poset labelled by elements of X. These results are related to recent work of Korte and Lovász on antimatroids. We also compute the convex dimension of a convex geometry.Supported in part by NSF grant no. DMS-8501948.