Πέμπτη 25 Ιουλίου 2019

Avoiding Brooms, Forks, and Butterflies in the Linear Lattices

Abstract

Let n be a positive integer, q a power of a prime, and \(\mathcal {L}_{n}({q})\) the poset of subspaces of an n-dimensional vector space over a field with q elements. This poset is a normalized matching poset and the set of subspaces of dimension ⌊n/2⌋ or those of dimension ⌈n/2⌉ are the only maximum-sized antichains in this poset. Strengthening this well-known and celebrated result, we show that, except in the case of \(\mathcal {L}_{3}({2})\) , these same collections of subspaces are the only maximum-sized families in \(\mathcal {L}_{n}({q})\) that avoid both a ∧ and a ∨ as a subposet. We generalize some of the results to brooms and forks, and we also show that the union of the set of subspaces of dimension k and k + 1, for k = ⌊n/2⌋ or k = ⌈n/2⌉ − 1, are the only maximum-sized families in \(\mathcal {L}_{n}({q})\) that avoid a butterfly  (definitions below).

On Lattice Representations with Dcc Posets

Abstract

In this paper, we investigate the class of lattices representable with posets satisfying the DCC condition. We describe a way to decide whether a finite lattice is in this class. We also give a necessary condition for an arbitrary lattice to be in this class. This hints at a notion that would be a weaker version of lower boundedness.

Characterizing Subclasses of Cover-Incomparability Graphs by Forbidden Subposets

Abstract

In this paper we continue investigations of cover-incomparability graphs of finite partially ordered sets (see Brešar et al. Order 25:335–347 2008; Brešar et al. Discret. Appl. Math. 158:1752–1759 2010; Brešar et al. Order 32(2):179–187 2015; Brešar et al. 2014 and Maxová et al. Order 26:229–236 2009; Maxová and Turzík Discret. Appl. Math. 161:2095–2100 2013). We consider in some detail the distinction between cover-preserving subsets and isometric subsets of a partially ordered set. This is critical to understanding why forbidden subposet characterizations of certain classes of cover-incomparability graphs in Brešar et al. (Order 25:335–347 2008) and Brešar et al. (Order 32(2):179–187 2015) are not valid as presented. Here we provide examples, investigate the root of the difficulties, and formulate and prove valid revisions of these characterizations.

A Syntactic Approach to the MacNeille Completion of Λ ∗ , the Free Monoid Over an Ordered Alphabet Λ

Abstract

Let Λ be the free monoid of (finite) words over a not necessarily finite alphabet Λ, which is equipped with some (partial) order. This ordering lifts to Λ, where it extends the divisibility ordering of words. The MacNeille completion of Λconstitutes a complete lattice ordered monoid and is realized by the system of “closed” lower sets in Λ (ordered by inclusion) or its isomorphic copy formed of the “closed” upper sets (ordered by reverse inclusion). Under some additional hypothesis on Λ, one can easily identify the closed lower sets as the finitely generated ones, whereas it is more complicated to determine the closed upper sets. For a fairly large class of ordered sets Λ (including complete lattices as well as antichains) one can generate the closure of any upper set of words by means of binary operations (“syntactic rules”) thus obtaining an efficient procedure to test closedness. Closed upper sets of words are involved in an embedding theorem for valuated oriented graphs. In fact, generalized paths (so-called “zigzags”) are encoded by words over an alphabet Λ. Then the valuated oriented graphs which are “isometrically” embeddable in a product of zigzags have the characteristic property that the words corresponding to the zigzags between any pair of vertices form a closed upper set in Λ.

Compatibility of Quasi-Orderings and Valuations: A Baer-Krull Theorem for Quasi-Ordered Rings

Abstract

In 1969, Manis introduced valuations on commutative rings. Recently the class of totally quasi-ordered rings was recently developed. In the present paper, given a quasi-ordered ring (R, ⪯) and a valuation v on R, we establish the notion of compatibility between v and ⪯, leading to a definition of the rank of (R, ⪯). Our main result is a Baer-Krull Theorem for quasi-ordered rings: fixing a Manis valuation v on R, we characterize all v-compatible quasi-orders of Rby lifting the quasi-orders from the residue class domain to R itself. In particular, this approach generalizes to the ring case the results of the paper A Baer-Krull Theorem for Quasi-Ordered Groups (Kuhlmann and Lehéricy 2017).

Maximal d -Elements of an Algebraic Frame

Abstract

The space of maximal d-ideals of C(X) is well-known and is widely studied. It is known that the space of maximal d-ideals is homeomorphic to the Z(X)-ultrafilters, and this space is the minimal quasi F-cover of a compact Tychonoff space X. In the current article we generalize this concept for M-frames, algebraic frames with the finite intersection property. In particular, we explore various properties of the maximal d-elements of a frame L, and their relation with the ultrafilters of \(\mathfrak {K}L^{\perp }\) , the polars of the compact elements of L. On a separate note, we revisit the Lemma on Ultrafilters and establish the correspondence between the minimal prime elements spaces of L with the spaces of ultrafilters of \(\mathfrak {K}L\) . Finally, we show that for complemented frames LMin(L) = Max(dL), a result parallel to the one known for Riesz spaces, W-objects, and topological spaces.

Orthogonal Countable Linear Orders

Abstract

Two linear orderings of a same set are perpendicular if every self-mapping of this set that preserves them both is constant or the identity. Two isomorphy types of linear orderings are orthogonal if there exist two perpendicular orderings of these types. Our main result is a characterisation of orthogonality to ω : a countably infinite type is orthogonal toωif and only if it is scattered and does not admit any embedding into the chain of infinite classes of its Hausdorff congruence. Besides we prove that a countable type is orthogonal toω + n (2 ≤ n < ωif and only if it has infinitely many vertices that are isolated for the order topology. We also prove that a typeτis orthogonal toω + 1 if and only if it has a decomposition of the formτ = τ1 + 1 + τ2withτ1orτ2orthogonal toωor one of them finite nonempty and the other one orthogonal toω + 2. Since it was previously known that two countable types are orthogonal whenever each one has two disjoint infinite intervals, this completes a characterisation of orthogonality of pairs of types of countable linear orderings. It follows that the equivalence relation of indistinguishability for the orthogonality relation on the class of countably infinite linear orders has exactly seven classes : the classes respectively of ωω + 1, ω + 2, ω + ωωω, 3 ⋅ η and η, where η is the type of the ordering of rational numbers and 3 ⋅ η is the lexicographical sum along η of three element linear orders.

Tolerance Orders of Open and Closed Unit Intervals

Abstract

In this paper we combine ideas from tolerance orders with recent work on OC interval orders. We consider representations of posets by unit intervals Iv in which the interval endpoints (L(v) and R(v)) may be open or closed as well as the center point (c(v)). This yields four types of intervals: A (endpoints and center points closed), B (endpoints and center points open), C (endpoints closed, center points open), and D (endpoints open, center points closed). For any non-empty subset S of {ABCD}, we define an S-order as a poset P that has a representation as follows: each element v of P is assigned a unit interval Iv of type belonging to S, and x ≺ y if and only if either (i) R(x) < c(y) or (ii) R(x) = c(y) and at least one of R(x), c(y) is open and at least one of L(y), c(x) is open. We characterize several of the classes of S-orders and provide separating examples between unequal classes. In addition, for each S ⊆{ABCD} we present a polynomial-time algorithm that recognizes S-orders, providing a representation when one exists and otherwise providing a certificate showing it is not an S-order.

Space of Minimal n -Prime Ideals

Abstract

In this paper, we study the concept of an n-prime ideal in 0-distributive lattices. The characterization of minimal n-prime ideals is obtained. Further, the topology on the set \(\mathcal {P}_{n}(L)\) of minimal n-prime ideals of a 0-distributive lattice L is studied and it is shown that \(\mathcal {P}_{n}(L)\) is compact if and only if it is finite.

A Framework for the Systematic Determination of the Posets on n Points with at Least τ ⋅ 2 n Downsets

Abstract

A structural framework is presented which allows the systematic determination of all non-isomorphic posets on n points with at least τ ⋅ 2n downsets, or - equivalently - of all T0-topologies on n points with at least τ ⋅ 2n open sets. The framework is developed by defining the type of a special extension of posets and by defining a partial order on these types. It is shown that this partial order is strictly antitone to the number of downsets of so called simple extensions; additionally the downset number of a simple extension is the maximum of the downset numbers of all extensions having the same type as the simple extension. For non-simple extensions of an important type it is shown that the number of their downsets is ruled by a simple sub-extension contained in them. The approach is used to determine all non-isomorphic posets with at least \( \frac {1}{4} \cdot 2^{n}\) downsets. Finally, a result of Vollert about the structure of downset numbers is refined.

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου

Αρχειοθήκη ιστολογίου