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.      

Subdifferentiation of monotone functions from semilattices to distributive lattices

An abstract algebraic interpretation of subgradients of real-valued convex functions is presented, and the definition is extended to modal theory. The main result is that a convex (i.e., monotone) function from a semilattice to acomplete distributive lattice is the join of its set of subgradients.     

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.     

Algebraic signatures of convex and non-convex codes

A convex code is a binary code generated by the pattern of intersections of a collection of open convex sets in some Euclidean space. Convex codes are relevant to neuroscience as they arise from the activity of neurons that have convex receptive fields. In this paper, we develop algebraic methods to determine if a code is convex. Specifically, we use the neural ideal of a code, which is a generalization of the Stanley–Reisner ideal. Using the neural ideal together with its standard generating set, the canonical form, we provide algebraic signatures of certain families of codes that are non-convex. We connect these signatures to the precise conditions on the arrangement of sets that prevent the codes from being convex. Finally, we also provide algebraic signatures for some families of codes that are convex, including the class of intersection-complete codes. These results allow us to detect convexity and non-convexity in a variety of situations, and point to some interesting open questions.     

Second order homological obstructions on real algebraic manifolds

Let Y be a compact nonsingular real algebraic set whose homology classes (over Z/2) are represented by Zariski closed subsets. It is well known that every smooth map from a compact smooth manifold to Y is unoriented bordant to a regular map. In this paper, we show how to construct smooth maps from compact nonsingular real algebraic sets to Y not homotopic to any regular map starting from a nonzero homology class of Y of positive degree. We use these maps to obtain obstructions to the existence of local algebraic tubular neighborhoods of algebraic submanifolds of Rn and to study some algebro-homological properties of rational real algebraic manifolds.     

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.     

Poset extensions, convex sets, and semilattice presentations

The paper is devoted to an algebraic and geometric study of the feasible set of a poset, the set of finite probability distributions on the elements of the poset whose weights satisfy the order relationships specified by the poset. For a general poset, this feasible set is a barycentric algebra. The feasible sets of the order structures on a given finite set are precisely the convex unions of the primary simplices, the facets of the first barycentric subdivision of the simplex spanned by the elements of the set. As another fragment of a potential complete duality theory for barycentric algebras, a duality is established between order-preserving mappings and embeddings of feasible sets. In particular, the primary simplices constituting the feasible set of a given finite poset are the feasible sets of the linear extensions of the poset. A finite poset is connected if and only if its barycentre is an extreme point of its feasible set. The feasible set of a (general) disconnected poset is the join of the feasible sets of its components. The extreme points of the feasible set of a finite poset are specified in terms of the disjointly irreducible elements of the semilattice presented by the poset. Semilattices presented by posets are characterised in terms of various distributivity concepts.     

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.     

Convex programming for disjunctive convex optimization

Given a finite number of closed convex sets whose algebraic representation is known, we study the problem of finding the minimum of a convex function on the closure of the convex hull of the union of those sets. We derive an algebraic characterization of the feasible region in a higher-dimensional space and propose a solution procedure akin to the interior-point approach for convex programming. Received November 27, 1996 / Revised version received June 11, 1999?Published online November 9, 1999     

The lattice of convex subsemilattices of a semilattice

The convex subsemilattices of a semilattice E form a lattice Co(E) in the natural way. The purpose of this paper is to study how the properties of this lattice relate to the semilattice itself. For instance, lower semimodularity of the lattice is equivalent, along with various properties, to the semilattice being a tree. When E has more than two elements the lattice does, however, fail many common lattice-theoretic tests. It turns out that it is more fruitful to describe those semilattices E for which every “atomically generated” filter of Co(E) satisfies certain lattice-theoretic properties.     

Obstructions to convexity in neural codes

How does the brain encode spatial structure? One way is through hippocampal neurons called place cells, which become associated to convex regions of space known as their receptive fields: each place cell fires at a high rate precisely when the animal is in the receptive field. The firing patterns of multiple place cells form what is known as a convex neural code. How can we tell when a neural code is convex? To address this question, Giusti and Itskov identified a local obstruction, defined via the topology of a code's simplicial complex, and proved that convex neural codes have no local obstructions. Curto et al. proved the converse for all neural codes on at most four neurons. Via a counterexample on five neurons, we show that this converse is false in general. Additionally, we classify all codes on five neurons with no local obstructions. This classification is enabled by our enumeration of connected simplicial complexes on 5 vertices up to isomorphism. Finally, we examine how local obstructions are related to maximal codewords (maximal sets of neurons that co-fire). Curto et al. proved that a code has no local obstructions if and only if it contains certain “mandatory” intersections of maximal codewords. We give a new criterion for an intersection of maximal codewords to be non-mandatory, and prove that it classifies all such non-mandatory codewords for codes on up to five neurons.     

2 ω-finite automata and sets of obstructions of their languages

Nondeterministic finite Rabin-Scott’s automata without initial and final states (2ω-FA) are considered. In this paper, they are used to define so called sets of obstructions, used also in various algebraic systems, and to consider similar problems for the formal languages theory. Thus, we define sets of obstructions of languages (or, rather, 2ω-languages) of such automata. We obtain that each 2ω-language defined by 2 ω-FA has the set of obstruction being a regular language. And, vice versa, for each regular languageL (containing no proper subword of its another word), there exists a 2ω-FA havingL as the set of obstructions.     

The Lattice of Convex Subsemilattices of a Semilattice

Abstract. The convex subsemilattices of a semilattice E form a lattice C o(E) in the natural way. The purpose of this paper is to study how the properties of this lattice relate to the semilattice itself. For instance, lower semimodularity of the lattice is equivalent, along with various properties, to the semilattice being a tree. When E has more than two elements the lattice does, however, fail many common lattice-theoretic tests. It turns out that it is more fruitful to describe those semilattices E for which every ``atomically generated' filter of C o(E) satisfies certain lattice-theoretic properties.     

Characterizations of the convex geometries arising from the double shellings of posets

We investigate the class of double-shelling convex geometries. A double-shelling convex geometry is the collection of sets represented as the intersection of an ideal and a filter of a poset. The size of the stem of any rooted circuit of a double-shelling convex geometry is 2. We characterize the double-shelling convex geometries by the conditions that the rooted circuits should fulfill. Moreover we also characterize the same class in terms of trace-minimal forbidden minors.     

Convexity theories IV. Klein-Hilbert parts in convex modules

The Klein-Hilbert part relation, which was introduced by Gleason in function algebras and investigated for convex subsets of real vector spaces by Bear and Bauer in [3], [5], [2], is defined for convex modules. It turns out that all results that were proved for convex sets can also be proved for convex modules, which constitute the algebraic theory generated by convex sets and which have a close connection to physics and mathematical economics.     

On the closedness of the algebraic difference of closed convex sets

We characterize in a reflexive Banach space all the closed convex sets C₁ containing no lines for which the condition C₁^∞∩C₂^∞={0} ensures the closedness of the algebraic difference C₁−C₂ for all closed convex sets C₂. We also answer a closely related problem: determine all the pairs C₁, C₂ of closed convex sets containing no lines such that the algebraic difference of any sufficiently small uniform perturbations of C₁ and C₂ remains closed. As an application, we state the broadest setting for the strict separation theorem in a reflexive Banach space.     

On irreducible elements of semilattices

The concept of (join)-irreducible elements works well, especially for distributive lattices. Therefore our definition of elements of a given degree of irreducibility employs the notion of distributivity as much as possible, even if the irreducibility is defined for elements of a (meet)-semilattice. Via the lattice of hereditary subsets of the poset ofk-irreducible elements of a semilattice (wherek is a cardinal) we obtain a new construction of a D1_k-reflection (a sort of free distributive extension) of the semilattice, provided that there are sufficiently manyk-irreducible elements. The last property is satisfied, for example, if the original semilattice is the dual of an algebraic lattice [Dilworth and Crawley, 1960], but this condition is too restrictive for semilattices. It turns out that, under certain limitations, the D1_k-reflection of a semilattice both preserves and reflects the degree of irreducibility.Presented by R. Freese.     

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.     

Maximal and Minimal Semilattices on Ordered Sets

The map which takes an element of an ordered set to its principal ideal is a natural embedding of that ordered set into its powerset, a semilattice. If attention is restricted to all finite intersections of the principal ideals of the original ordered set, then an embedding into a much smaller semilattice is obtained. In this paper the question is answered of when this construction is, in a certain arrow-theoretic sense, minimal. Specifically, a characterisation is given, in terms of ideals and filters, of those ordered sets which admit a so-called minimal embedding into a semilattice. Similarly, a candidate maximal semilattice on an ordered set can be constructed from the principal filters of its elements. A characterisation of those ordered sets that extend to a maximal semilattice is given. Finally, the notion of a free semilattice on an ordered set is given, and it is shown that the candidate maximal semilattice in the embedding-theoretic sense is the free object.     

Convexity preserving interpolation by algebraic curves and surfaces

The problem of interpolation by a convex curve to the vertices of a convex polygon is considered. A natural 1-parameter family ofC algebraic curves solving this problem is presented. This is extended to a solution, of a general Hermite-type problem, in, which the curve also interpolates to one or two prescribedtangents at any desired vertices of the polygon. The construction of these curves is a generalization of well known methods for generatingconic sections. Several properties of this family of algebraic curves are discussed. In addition, the method is generalized to convexC interpolation of strictly convex data sets inR ³ by algebraicsurfaces.