The affine representation theorem for abstract convex geometries

A convex geometry is a combinatorial abstract model introduced by Edelman and Jamison which captures a combinatorial essence of “convexity” shared by some objects including finite point sets, partially ordered sets, trees, rooted graphs. In this paper, we introduce a generalized convex shelling, and show that every convex geometry can be represented as a generalized convex shelling. This is “the representation theorem for convex geometries” analogous to “the representation theorem for oriented matroids” by Folkman and Lawrence. An important feature is that our representation theorem is affine-geometric while that for oriented matroids is topological. Thus our representation theorem indicates the intrinsic simplicity of convex geometries, and opens a new research direction in the theory of convex geometries.     

Going down in (semi)lattices of finite moore families and convex geometries

In this paper we first study what changes occur in the posets of irreducible elements when one goes from an arbitrary Moore family (respectively, a convex geometry) to one of its lower covers in the lattice of all Moore families (respectively, in the semilattice of all convex geometries) defined on a finite set. Then we study the set of all convex geometries which have the same poset of join-irreducible elements. We show that this set—ordered by set inclusion—is a ranked join-semilattice and we characterize its cover relation. We prove that the lattice of all ideals of a given poset P is the only convex geometry having a poset of join-irreducible elements isomorphic to P if and only if the width of P is less than 3. Finally, we give an algorithm for computing all convex geometries having the same poset of join-irreducible elements.      

Join-semidistributive lattices and convex geometries

We introduce the notion of a convex geometry extending the notion of a finite closure system with the anti-exchange property known in combinatorics. This notion becomes essential for the different embedding results in the class of join-semidistributive lattices. In particular, we prove that every finite join-semidistributive lattice can be embedded into a lattice S_P(A) of algebraic subsets of a suitable algebraic lattice A. This latter construction, S_P(A), is a key example of a convex geometry that plays an analogous role in hierarchy of join-semidistributive lattices as a lattice of equivalence relations does in the class of modular lattices. We give numerous examples of convex geometries that emerge in different branches of mathematics from geometry to graph theory. We also discuss the introduced notion of a strong convex geometry that might promise the development of rich structural theory of convex geometries.     

The max-flow min-cut property of two-dimensional affine convex geometries

In a matroid, (X,e) is a rooted circuit if X is a set not containing element e and X∪{e} is a circuit. We call X a broken circuit of e. A broken circuit clutter is the collection of broken circuits of a fixed element. Seymour [The matroids with the max-flow min-cut property, J. Combinatorial Theory B 23 (1977) 189-222] proved that a broken circuit clutter of a binary matroid has the max-flow min-cut property if and only if it does not contain a minor isomorphic to Q₆. We shall present an analogue of this result in affine convex geometries. Precisely, we shall show that a broken circuit clutter of an element e in a convex geometry arising from two-dimensional point configuration has the max-flow min-cut property if and only if the configuration has no subset forming a ‘Pentagon’ configuration with center e.Firstly we introduce the notion of closed set systems. This leads to a common generalization of rooted circuits both of matroids and convex geometries (antimatroids). We further study some properties of affine convex geometries and their broken circuit clutters.     

On Scattered Convex Geometries

A convex geometry is a closure space satisfying the anti-exchange axiom. For several types of algebraic convex geometries we describe when the collection of closed sets is order scattered, in terms of obstructions to the semilattice of compact elements. In particular, a semilattice Ω(η), that does not appear among minimal obstructions to order-scattered algebraic modular lattices, plays a prominent role in convex geometries case. The connection to topological scatteredness is established in convex geometries of relatively convex sets.     

Representation of convex geometries by circles on the plane

Convex geometries are closure systems satisfying the anti-exchange axiom. Every finite convex geometry can be embedded into a convex geometry of finitely many points in an $n$-dimensional space equipped with a convex hull operator, by the result of Kashiwabara et al. (2005). Allowing circles rather than points, as was suggested by Czédli (2014), may presumably reduce the dimension for representation. This paper introduces a property, the Weak 2 × 3-Carousel rule, which is satisfied by all convex geometries of circles on the plane, and we show that it does not hold in all finite convex geometries. This raises a number of representation problems for convex geometries, which may allow us to better understand the properties of Euclidean space related to its dimension.     

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.     

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.     

Rank functions of strict cg-matroids

A matroid-like structure defined on a convex geometry, called a cg-matroid, is defined by Fujishige et al. [Matroids on convex geometries (cg-matroids), Discrete Math. 307 (2007) 1936-1950]. A cg-matroid whose rank function is naturally defined is called a strict cg-matroid. In this paper, we give characterizations of strict cg-matroids by their rank functions.     

Realization of abstract convex geometries by point configurations

The Edelman–Jamison problem is to characterize those abstract convex geometries that are representable by a set of points in the plane. We show that some natural modification of the Edelman–Jamison problem is equivalent to the well known NP-hard order type problem. The relation to the realizability of oriented matroids is clarified.     

Quotients of incidence geometries

We develop a theory for quotients of geometries and obtain sufficient conditions for the quotient of a geometry to be a geometry. These conditions are compared with earlier work on quotients, in particular by Pasini and Tits. We also explore geometric properties such as connectivity, firmness and transitivity conditions to determine when they are preserved under the quotienting operation. We show that the class of coset pregeometries, which contains all flag-transitive geometries, is closed under an appropriate quotienting operation.     

The Funk and Hilbert geometries for spaces of constant curvature

The goal of this paper is to introduce and to study analogues of the Euclidean Funk and Hilbert metrics on open convex subsets of the hyperbolic space $\mathbb H ^n$ H n and of the sphere $S^n$ S n . We highlight some striking similarities among the three cases (Euclidean, spherical and hyperbolic) which hold at least at a formal level. The proofs of the basic properties of the classical Funk metric on subsets of $\mathbb R ^n$ R n use similarity properties of Euclidean triangles which of course do not hold in the non-Euclidean cases. Transforming the side lengths of triangles using hyperbolic and circular functions and using some non-Euclidean trigonometric formulae, the Euclidean similarity techniques are transported into the non-Euclidean worlds. We start by giving three representations of the Funk metric in each of the non-Euclidean cases, which parallel known representations for the Euclidean case. The non-Euclidean Funk metrics are shown to be Finslerian, and the associated Finsler norms are described. We then study their geodesics. The Hilbert geometry of convex sets in the non-Euclidean constant curvature spaces $S^n$ S n and $\mathbb H ^n$ H n is then developed by using the properties of the Funk metric and by introducing a non-Euclidean cross ratio. In the case of Euclidean (respectively spherical, hyperbolic) geometry, the Euclidean (respectively spherical, hyperbolic) geodesics are Funk and Hilbert geodesics. This leads to a formulation and a discussion of Hilbert’s Problem IV in the non-Euclidean settings. Projection maps between the spaces $\mathbb R ^n, \mathbb H ^n$ R n , H n and the upper hemisphere establish equivalences between the Hilbert geometries of convex sets in the three spaces of constant curvature, but such an equivalence does not hold for Funk geometries.     

An axiomatic foundation of Cayley-Klein geometries

We present a common axiomatic characterization of Cayley-Klein geometries over fields of characteristic \({\neq 2}\). To this end the axiom system of Bachmann (Aufbau der Geometrie aus dem Spiegelungsbegriff, 2nd edn. Springer, Heidelberg1973) for plane absolute geometry, which allows a common axiomatization of Euclidean, hyperbolic and elliptic geometry, is generalized. The notion of plane absolute geometry is broadened in several aspects. The most important one is that the principle of duality holds: the dual of a Cayley-Klein geometry is also a Cayley-Klein geometry. The various Cayley-Klein geometries are singled out by additional axioms like the Euclidean or hyperbolic parallel axiom or their dual statements.     

Bounds on the convex label number of trees

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that wheneverx, y andz are the labels of vertices on a path of length 2 theny≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a treeT is the smallest integerm such thatT has a convex labelling with no label greater thanm. We prove that every rooted tree (and hence every tree) withn vertices has convex label number less than 4n. We also exhibitn-vertex trees with convex label number 4n/3+o(n), andn-vertex rooted trees with convex label number 2n +o(n). The research by M. B. and A. W. was partly supported by NSF grant MCS—8311422.     

Action potential and weak KAM solutions

For convex superlinear lagrangians on a compact manifold M we characterize the Peierls barrier and the weak KAM solutions of the Hamilton-Jacobi equation, as defined by A. Fathi [9], in terms of their values at each static class and the action potential defined by R. Ma né [14]. When the manifold M is non-compact, we construct weak KAM solutions similarly to Busemann functions in riemannian geometry. We construct a compactification of by extending the Aubry set using these Busemann weak KAM solutions and characterize the set of weak KAM solutions using this extended Aubry set. Received: 13 November 2000 / Accepted: 4 December 2000 / Published online: 25 June 2001     

On representations of the feasible set in convex optimization

We consider the convex optimization problem \({\min_{\mathbf{x}} \{f(\mathbf{x}): g_j(\mathbf{x})\leq 0, j=1,\ldots,m\}}\) where f is convex, the feasible set \({\mathbf{K}}\) is convex and Slater’s condition holds, but the functions g _j ’s are not necessarily convex. We show that for any representation of \({\mathbf{K}}\) that satisfies a mild nondegeneracy assumption, every minimizer is a Karush-Kuhn-Tucker (KKT) point and conversely every KKT point is a minimizer. That is, the KKT optimality conditions are necessary and sufficient as in convex programming where one assumes that the g _j ’s are convex. So in convex optimization, and as far as one is concerned with KKT points, what really matters is the geometry of \({\mathbf{K}}\) and not so much its representation.     

On the topology of the free complexes of convex geometries

We investigate the free complex of a convex geometry. Edelman and Reiner showed that the free complex of a convex geometry is contractible. Moreover, their paper stated a conjecture about the topology of free complexes. This paper proves their conjecture.     

Approximate Efficiency and Scalar Stationarity in Unbounded Nonsmooth Convex Vector Optimization Problems

We deal with extended-valued nonsmooth convex vector optimization problems in infinite-dimensional spaces where the solution set (the weakly efficient set) may be empty. We characterize the class of convex vector functions having the property that every scalarly stationary sequence is a weakly-efficient sequence. We generalize the results obained in the scalar case by Auslender and Crouzeix about asymptotically well-behaved convex functions and improve substantially the few results known in the vector case.