n-distributivity,dimension and Carathéodory's theorem

A. Huhn proved that the dimension of Euclidean spaces can be characterized through algebraic properties of the lattices of convex sets. In fact, the lattice of convex sets of isn+1-distributive but notn-distributive. In this paper his result is generalized for a class of algebraic lattices generated by their completely join-irreducible elements. The lattice theoretic form of Carathéodory's theorem characterizesn-distributivity in such lattices. Several consequences of this result are studied. First, it is shown how infiniten-distributivity and Carathéodory's theorem are related. Then the main result is applied to prove that for a large class of lattices beingn-distributive means being in the variety generated by the finiten-distributive lattices. Finally,n-distributivity is studied for various classes of lattices, with particular attention being paid to convexity lattices of Birkhoff and Bennett for which a Helly type result is also proved.Presented by J. Sichler.     

Closed convex sets and their best simultaneous approximation properties with applications

We develop a theory of best simultaneous approximation for closed convex sets in a conditionally complete lattice Banach space X with a strong unit. We study best simultaneous approximation in X by elements of closed convex sets, and give necessary and sufficient conditions for the uniqueness of best simultaneous approximation. We give a characterization of simultaneous pseudo-Chebyshev and quasi-Chebyshev closed convex sets in X. Also, we present various characterizations of best simultaneous approximation of elements by closed convex sets in terms of the extremal points of the closed unit ball B _X* of X*.     

Boolean Hierarchies of Partitions over a Reducible Base

The Boolean hierarchy of partitions was introduced and studied by Kosub and Wagner, primarily over the lattice of NP-sets. Here, this hierarchy is treated over lattices with the reduction property, showing that it has a much simpler structure in this instance. A complete characterization is given for the hierarchy over some important lattices, in particular, over the lattices of recursively enumerable sets and of open sets in the Baire space.     

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.     

A note on essentially convex orders

In this note, we determine precisely which partially ordered sets (posets) have the property that, whenever they occur as subposets of a larger poset, they occur there convexly, i.e., as convex subposets. As a corollary, we also determine which lattices have the property that, if they occur as sublattices of a finite distributive lattice L, then they also occur as closed intervals in L. Throughout, all sets will be finite.Dedicated to the memory of Ivan RivalReceived May 5, 2003; accepted in final form October 3, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Linear Inequalities for Rank 3 Geometric Lattices

The flag Whitney numbers (also referred to as the flag f-numbers) of a geometric lattice count the number of chains of the lattice with elements having specified ranks. We give a collection of inequalities which imply all the linear inequalities satisfied by the flag Whitney numbers of rank 3 geometric lattices. We further describe the smallest closed convex set containing the flag Whitney numbers of rank 3 geometric lattices as well as the smallest closed convex set containing the flag Whitney numbers of those lattices corresponding to oriented matroids.     

Doubling convex sets in lattices and a generalized semidistributivity condition

A useful construction for lattices is doubling a convex subsetI of a latticeL, i.e., replacingI byI×2. It is shown that this construction preserves a generalized semidistributivity condition (C). Varieties of lattices in which every lattice satisfies (C) are characterized equationally.This research was supported in part by the NSF (Nation) and NSERC (Day).     

Reducible classes of finite lattices

In this paper we study a notion of reducibility in finite lattices. An element x of a (finite) lattice L satisfying certain properties is deletable if L-x is a lattice satisfying the same properties. A class of lattices is reducible if each lattice of this class admits (at least) one deletable element (equivalently if one can go from any lattice in this class to the trivial lattice by a sequence of lattices of the class obtained by deleting one element in each step). First we characterize the deletable elements in a pseudocomplemented lattice what allows to prove that the class of pseudocomplemented lattices is reducible. Then we characterize the deletable elements in semimodular, modular and distributive lattices what allows to prove that the classes of semimodular and locally distributive lattices are reducible. In conclusion the notion of reducibility for a class of lattices is compared with some other notions like the notion of order variety.     

On lattices of convex sets in {\mathbb{R}}^{n}

Properties of several sorts of lattices of convex subsets of are examined. The lattice of convex sets containing the origin turns out, for n > 1, to satisfy a set of identities strictly between those of the lattice of all convex subsets of and the lattice of all convex subsets of The lattices of arbitrary, of open bounded, and of compact convex sets in all satisfy the same identities, but the last of these is join-semidistributive, while for n > 1 the first two are not. The lattice of relatively convex subsets of a fixed set satisfies some, but in general not all of the identities of the lattice of “genuine” convex subsets of To the memory of Ivan RivalReceived April 22, 2003; accepted in final form February 16, 2005.This revised version was published online in August 2005 with a corrected cover date.     

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     

The isodiametric problem with lattice-point constraints

In this paper, the isodiametric problem for centrally symmetric convex bodies in the Euclidean d-space \Bbb R^d{\Bbb R}^d containing no interior non-zero point of a lattice L is studied. It is shown that the intersection of a suitable ball with the Dirichlet-Voronoi cell of 2L is extremal, i.e., it has minimum diameter among all bodies with the same volume. It is conjectured that these sets are the only extremal bodies, which is proved for all three dimensional and several prominent lattices.     

On finite lattice coverings

We consider finite lattice coverings of strictly convex bodies K. For planar centrally symmetric K we characterize the finite arrangements C _n such that conv , where C _n is a subset of a covering lattice for K (which satisfies some natural conditions). We prove that for a fixed lattice the optimal arrangement (measured with the parametric density) is either a sausage, a so-called double sausage or tends to a Wulff-shape, depending on the parameter. This shows that the Wulff-shape plays an important role for packings as well as for coverings. Further we give a version of this result for variable lattices. For the Euclidean d-ball we characterize the lattices, for which the optimal arrangement is a sausage, for large parameter. Received 19 May 1999.     

A note on non-support points, negligible sets, Gâteaux differentiability and Lipschitz embeddings

This paper first presents a characterization of three classes of negligible closed convex sets (i.e., Gauss null sets, Aronszajn null sets and cube null sets) in terms of non-support points; then gives a generalization of Gâteaux differentiability theorems of Lipschitz mapping from open sets to those closed convex sets admitting non-support points; and as their application, finally shows that a closed convex set in a separable Banach space X can be Lipschitz embedded into a Banach space Y with the Radon–Nikodym property if and only if the closure of its linear span is linearly isomorphic to a closed subspace of Y.     

Some varieties and convexities generated by fractal lattices

We introduce definitions of semifractal, 0–1-fractal, quasifractal and fractal lattices. A variety generated by a fractal lattice is called fractal generated, with analogous terminology for the other variants. We show that a semifractal generated nondistributive lattice variety cannot be of residually finite length. This easily implies that there are exactly continuously many lattice varieties which are not semifractal generated. On the other hand, for each prime field F, the variety generated by all subspace lattices of vector spaces over F is shown to be fractal generated. These countably many varieties and the class of all distributive lattices are the only known fractal generated lattice varieties at present. Four distinct countable distributive fractal lattices are given each of which generates . After showing that each lattice can be embedded in a quasifractal, continuously many quasifractals are given each of which has cardinality and generates the variety of all lattices. Semifractal considerations are applied to construct examples of convexities that include no minimal convexity, thus answering a question of Jakubík. (A convexity is a class of lattices closed under taking homomorphic images, convex sublattices and direct products, a notion due to Ervin Fried.) This research was partially supported by the NFSR of Hungary (OTKA), grant no. T 049433 and K 60148.     

Fully gated graphs: Recognition and convex operations

A graph is fully gated when every convex set of vertices is gated. Doignon posed the problem of characterizing fully gated graphs and in particular of deciding whether there is an efficient algorithm for their recognition. While the number of convex sets can be exponential, we establish that it suffices to examine only the convex hulls of pairs of vertices. This yields an elementary polynomial time algorithm for the recognition of fully gated graphs; however, it does not appear to lead to a simple structural characterization. In this direction, we establish that fully gated graphs are closed under a set of ‘convex’ operations, including a new operation which duplicates the vertices of a convex set (under some well-defined restrictions). This in turn establishes that every bipartite graph is an isometric subgraph of a fully gated graph, thereby severely limiting the potential for a characterization based on subgraphs. Finally, a large class of fully gated graphs is obtained using the presence of bipartite dominators, which suggests that simple convex operations cannot suffice to produce all fully gated graphs.     

Simplicial elimination schemes,extremal lattices and maximal antichain lattices

Fix a partial order P=(X, <). We first show that bipartite orders are sufficient to study structural properties of the lattice of maximal antichains. We show that all orders having the same lattice of maximal antichains can be reduced to one representative order (called the poset of irreducibles by Markowsky [14]). We then define the strong simplicial elimination scheme to characterize orders which have distributive lattice of maximal antichains. The notion of simplicial elimination corresponds to the decomposition process described in [14] for extremal lattices. This notion leads to simple greedy algorithms for distributivity checking, lattice recognition and jump number computation. In the last section, we give several algorithms for lattices and orders.     

Sums, Projections, and Sections of Lattice Sets, and the Discrete Covariogram

Basic properties of finite subsets of the integer lattice ℤⁿ are investigated from the point of view of geometric tomography. Results obtained concern the Minkowski addition of convex lattice sets and polyominoes, discrete X-rays and the discrete and continuous covariogram, the determination of symmetric convex lattice sets from the cardinality of their projections on hyperplanes, and a discrete version of Meyer’s inequality on sections of convex bodies by coordinate hyperplanes.     

Separation in distributive congruence lattices

We define separable sets in algebraic lattices. For a finitely generated congruence distributive variety V \mathcal{V} , we show a close connection between non-separable sets in congruence lattices of algebras in V \mathcal{V} and the structure of subdirectly irreducible algebras in V \mathcal{V} . We apply the general results to some lattice varieties.     

On convex bodies containing a given number of lattice points

Given a convex body K in Euclidean space, a necessary and sufficient condition is established in order that for each n there exists a homothetic copy of K containing exactly n lattice points. Similar theorems are proved for congruent copies of K and for discrete sets other than lattices.