Convex Dimension of Locally Planar Convex Geometries

We prove that convex geometries of convex dimension n that satisfy two properties satisfied by nondegenerate sets of points in the plane, may have no more than 2 ^n-1 points. We give examples of such convex geometries that have n \choose 4 + n \choose 2 + n \choose 0 points. Received June 7, 1999, and in revised form April 18, 2000. Online publication September 22, 2000.     

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.     

Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes

We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f–1)×(f–1) grid. Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3.The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof.     

On the Order Dimension of Outerplanar Maps

Schnyder characterized planar graphs in terms of order dimension. Brightwell and Trotter proved that the dimension of the vertex-edge-face poset P _M of a planar map M is at most four. In this paper we investigate cases where dim(P _M ) ≤ 3 and also where dim(Q _M ) ≤ 3; here Q _M denotes the vertex-face poset of M. We show:

On the Order of Strongly Starlikeness of Convex Functions of Order Alpha

In this work the order of strongly starlikeness of convex functions of order alpha is discussed.     

Orders on Subsets Rationalised by Abstract Convex Geometries

We find conditions on the order on subsets of a finite set which are necessary and sufficient for the relative ranking of any two subsets in this order to be determined by their extreme elements relative to an abstract convex geometry. It turns out that this question is closely related to the rationalisability of path independent choice functions by hyper-relations.      

A Factorization Theorem of Characteristic Polynomials of Convex Geometries

A convex geometry is a closure system whose closure operator satisfies the anti-exchange property. As is described in Sagan’s survey paper, characteristic polynomials factorize over nonnegative integers in several situations. We show that the characteristic polynomial of a 2-tight convex geometry K factorizes over nonnegative integers if the clique complex of the nbc-graph of K is pure and strongly connected. This factorization theorem is new in the sense that it does not belong to any of the three categories mentioned in Sagan’s survey. Received September 25, 2005     

On the Dimension of a Face Exposed by Proper Separation of Convex Polyhedra

Whenever two nonempty convex polyhedra can be properly separated, a separating hyperplane may be chosen to contain a face of either polyhedron. It is demonstrated that, in fact, one or the other of the polyhedra admits such an exposed face having dimension no smaller than approximately half the larger dimension of the two polyhedra. An example shows that the bound on face dimension is optimal, and a linear programming representation of the problem is given.     

Order Types of Convex Bodies

We prove a Hadwiger transversal-type result, characterizing convex position on a family of non-crossing convex bodies in the plane. This theorem suggests a definition for the order type of a family of convex bodies, generalizing the usual definition of order type for point sets. This order type turns out to be an oriented matroid. We also give new upper bounds on the Erdős–Szekeres theorem in the context of convex bodies.     

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.     

Hausdorff Dimension in Convex Bornological Spaces

For non-metrizable spaces the classical Hausdorff dimension is meaningless. We extend the notion of Hausdorff dimension to arbitrary locally convex linear topological spaces and thus to a large class of non-metrizable spaces. This involves a limiting procedure using the canonical bornological structure. In the case of normed spaces the new notion of Hausdorff dimension is equivalent to the classical notion.     

A Discrete Duality Between Nonmonotonic Consequence Relations and Convex Geometries

In this paper we present a duality between nonmonotonic consequence relations and well-founded convex geometries. On one side of the duality we consider nonmonotonic consequence relations satisfying the axioms of an infinitary variant of System P, which is one of the most studied axiomatic systems for nonmonotonic reasoning, conditional logic and belief revision. On the other side of the duality we consider well-founded convex geometries, which are infinite convex geometries that generalize well-founded posets. Since there is a close correspondence between nonmonotonic consequence relations and path independent choice functions one can view our duality as an extension of an existing duality between path independent choice functions and convex geometries that has been developed independently by Koshevoy and by Johnson and Dean.

     

Hyperbolically Convex Functions,Dimension and Capacity

We study a conformal map ? of the unit disk D onto a hyperbolically convex set in D, in particular the behaviour of ? on the preimage T _? = {z ? ?D:|?(z)| = 1} of ?D. The main problem is how much the Hausdorff dimension can increase for sets on T _?. The case that ?(D) is bounded by full circles is treated in more detail. In this case ? can be written as a composition sequence of mappings onto halfplanes.     

Partial Order Embeddings with Convex Range

A careful study is made of embeddings of posets which have a convex range. We observe that such embeddings share nice properties with the homomorphisms of more restrictive categories; for example, we show that every order embedding between two lattices with convex range is a continuous lattice homomorphism. A number of posets are considered; for one of the simplest examples, we prove that every product order embedding σ : ?^? → ?^? with convex range is of the form

$$ \sigma(x)(n)=\left( (x\circ g_{\sigma})+y_{\sigma}\right)(n) ~~~~\text{if}~ n\in K_{\sigma}, $$

(1)

and σ(x)(n) = y _σ (n) otherwise, for all x ∈ ?^?, where K _σ ? ?, g _σ : K _σ → ? is a bijection and y _σ ∈ ?^?. The most complex poset examined here is the quotient of the lattice of Baire measurable functions, with codomain of the form ? ^I for some index set I, modulo equality on a comeager subset of the domain, with its ‘natural’ ordering.

     

Degenerate Convex Hulls On-Line in Any Fixed Dimension

Randomized algorithms have, since the pioneering work of Clarkson and Shor, occupied the front stage of computational geometry. Yet despite their simplicity, they often cannot handle or be extended to cope with degenerate cases. The main goal of this paper is to show how, for the special case of convex hulls, a simple modification of the formulation of an on-line algorithm by Boissonnat et al., based on that of Clarkson and Shor, can handle the case of degenerate sets of points for computing convex hulls on-line in R ^d , for a fixed . At the same time, a standard randomized analysis allows us to prove the expected time complexity to be within , where k is the dimension of the convex hull. The latter bound is always . The analysis uses connections between regions, pivots, flags, and barycentric triangulations. Received May 30, 1998, and in revised form March 26, 1999.     

On Characterization of Absolute Geometries

Starting from a general absolute plane A = (P, L, α, ≡) in the sense of Karzel et al. (Einführung in die Geometrie, p. 96, 1973), Karzel and Marchi introduced the notion of a Lambert–Saccheri quadrangle (L-S quadrangle) in Karzel and Marchi (Le Matematiche LXI:27–36, 2006): A quadruple (a, b, c, d) of points of P, no three collinear, is a L-S quadrangle, if ${\overline{a,d}\bot\overline{a,b}\bot\overline{b,c}\bot\overline{c,d}}$ . Denoting the foot of a on the line ${\overline{c, d}}$ with ${a^{\prime}=\{a\bot\overline{c,d}\}\cap \overline{c,d}}$ , the L-S quadrangle (a, b, c, d) is called rectangle, hyperbolic or elliptic quadrangle if ${a^{\prime}=d,\; a^{\prime}\,{\in}\, ]c,d[}$ or ${a^{\prime}\,{\notin}\, ]c,d[\cup \{d\}}$ respectively. Let LS be the set of all L-S quadrangles and LS _r , LS _h or LS _e the subset of all rectangles, hyperbolic or elliptic L-S quadrangles respectively. In Karzel and Marchi (Le Matematiche LXI:27–36, 2006) it was claimed that either LS =  LS _r or LS =  LS _h or LS =  LS _e . To this classification we add five further classifications of general absolute planes by using “distance” [defined in Karzel and Marchi (Discrete Math 308:220–230, 2008)] or the notions of “interior” and “exterior” angle, introduced in Karzel et al. (Resultate Math 51:61–71, 2007) and considering besides Lambert–Saccheri quadrangles, also triangles in particular right-angled triangles. For Lambert–Saccheri quadrangles (a, b, c, d) the relations between distances of the diagonal points (a, c) and (b, d) or between the “midpoint” ${o:=\overline{a,c}\cap\overline{b,d}}$ , and the corner points a, b, c, d give us possibilities for complete characterizations. Using triangles (a, b, c) and denoting by m and n the midpoints of (a, b) and (a, c) we classify the absolute planes by the relations between the distances |b, c| and 2|m, n|. All our main results are summarized at the end of the introduction.     

Grid Intersection Graphs and Order Dimension

We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Starting from this observation we provide a comprehensive study of classes of graphs between grid intersection graphs and bipartite permutation graphs and the containment relation on these classes. Order dimension plays a role in many arguments.     

A Half-Space Approach to Order Dimension

The aim of the present paper is to investigate the half-spaces in the convexity structure of all quasiorders on a given set and to use them in an alternative approach to classical order dimension. The main result states that linear orders can almost always be replaced by half-space quasiorders in the definition of the dimension of a partially ordered set. The work of the first named author was partially supported by the European Community’s Marie Curie Program (contract MTKD-CT-2004-003006). The second named author’s work was supported by OTKA of Hungary No. T043034.     

On Meet-Complements in Cohn Geometries

Within the frame of projective lattice geometry, the present paper investigates classes of meet-complements in Cohn geometries and especially in Ore and Bezout geometries. The algebraic background of these geometries is given by torsion free modules over domains — in particular Ore and Bezout domains. ¹