Maximal dimensional partially ordered sets III: a characterization of Hiraguchi's inequality for interval dimension

Dushnik and Miller defined the dimensions of a partially ordered set X,denoted dim X, as the smallest positive integer t for which there exist t linear extensions of X whose intersection is the partial ordering on X. Hiraguchi proved that if n ≥2 and |X| ≤2n+1, then dim X ≤ n. Bogart, Trotter and Kimble have given a forbidden subposet characterization of Hiraguchi's inequality by determining for each n ≥ 2, the minimum collection of posets ?_n such that if |X| ?2n+1, the dim X < n unless X contains one of the posets from ?_n. Although |?₃|=24, for each n ≥ 4, ?_n contains only the crown S⁰_n — the poset consisting of all 1 element and n ? 1 element subsets of an n element set ordered by inclusion. In this paper, we consider a variant of dimension, called interval dimension, and prove a forbidden subposet characterization of Hiraguchi's inequality for interval dimension: If n ≥2 and |X 2n+1, the interval dimension of X is less than n unless X contains S⁰_n.     

On a fixed point theorem for partially ordered sets

An elementary combinatorial proof is presented of the following fixed point theorem: Let P be a finite partially ordered set with a cut-set X. If every subset of X has either a meet or a join, then P has the fixed point property. This theorem is strengthened to include a certain class of infinite partially ordered sets, as well.     

Maximal dimensional partially ordered sets II. characterization of 2n-element posets with dimension n

In this paper, we show that if a partially ordered set has 2n elements and has dimension n, then it is isomorphic to the set of n?1 element subsets and 1element subsets of a set, ordered by inclusion, or else it has six elements and is isomorphic to a partially ordered set we call the chevron or to its dual.     

Spectral partially ordered sets

We examine some topics related to (gold)spectral partially ordered sets, i.e., those that are order isomorphic to (Goldman) prime spectra of commutative rings. Among other results, we characterize the partially ordered sets that are isomorphic to prime spectra of rings satisfying the descending chain condition on radical ideals, and we show that a dual of a tree is isomorphic to the Goldman prime spectrum of a ring if and only if every chain has an upper bound. We also give some new methods for constructing (gold)spectral partially ordered sets.     

Component partially ordered sets

Properties of component partially ordered sets (i.e., dense subsets of Boolean algebras) are used to construct mappings of Boolean algebras generalizing the idea of homomorphisms; the properties of a minimal Boolean algebra generated by a given component partially ordered set are investigated.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 275–283, March, 1971.     

Algorithms over partially ordered sets

We here study some problems concerned with the computational analysis of finite partially ordered sets. We begin (in § 1) by showing that the matrix representation of a binary relationR may always be taken in triangular form ifR is a partial ordering. We consider (in § 2) the chain structure in partially ordered sets, answer the combinatorial question of how many maximal chains might exist in a partially ordered set withn elements, and we give an algorithm for enumerating all maximal chains. We give (in § 3) algorithms which decide whether a partially ordered set is a (lower or upper) semi-lattice, and whether a lattice has distributive, modular, and Boolean properties. Finally (in § 4) we give Algol realizations of the various algorithms.     

A generalization of Hiraguchi's: Inequality for posets

For a poset X, Dim(X) is the smallest positive integer t for which X is isomorphic to a subposet of the cartesian product of t chains. Hiraguchi proved that if | X | ? 4, then Dim(X) ? [| X |/2]. For each k ? 2, we define Dim_k(X) as the smallest positive integer t for which X is isomorphic to a subposet of the cartesian product of t chains, each of length k. We then prove that if | X | ? 5, Dim₃(X) ? {| X |/2} and if | X | ? 6, then Dim₄(X) ? [| X |/2].     

Quasimartingales on partially ordered sets

The concept of a quasimartingale, and therefore also of a function of bounded variation, is extended to processes with a regular partially ordered index set V and with values in a Banach space. We show that quasimartingales can be described by their associated measures, defined on an inverse limit space $\text{S × Ω}$ containing $\text{V × Ω}$, furnished with the σ-algebra $\text{P}$ of the predictable sets. With the help of this measure, a Rao-Krickeberg and a Riesz decomposition is obtained, as well as a convergence theorem for quasimartingales. For a regular quasimartingale X it is proven that the spaces ($\text{S × Ω}$, $\text{P}$) and the measures associated with X are unique up to isomorphisms. In the case V = $\text{R}$₊ⁿ we prove a duality between classical (right-) quasimartingales and left-quasimartingales.     

Countable homogeneous partially ordered sets

It is shown that there are only countably many countable homogeneous partially ordered sets, thereby affirming a conjecture of Henson [2]. A classification of these partially ordered sets is given. Research partially supported by NSF Grant MCS76-07258. Presented by B. Jónsson.     

Representation of partially ordered sets

It is well known [1] that any distributive poset (short for partially ordered set) has an isomorphic representation as a poset (Q, (–) such that the supremum and the infimum of any finite setF ofp correspond, respectively, to the union and intersection of the images of the elements ofF. Here necessary and sufficient conditions are given for similar isomorphic representation of a poset where however the supremum and infimum of also infinite subsetsI correspond to the union and intersection of images of elements ofI. Presented by R. Freese.     

Topologies on products of partially ordered sets I: Interval topologies

Given a certain construction principle assigning to each partially ordered setP some topology θ(P) onP, one may ask under what circumstances the topology θ(P) of a productP = ?_j∈J P _j of partially ordered setsP _i agrees with the product topology ?_j∈Jθ(P _i) onP. We shall discuss this question for several types ofinterval topologies (Part I), forideal topologies (Part II), and fororder topologies (Part III). Some of the results contained in this first part are listed below:

1. Let θ_i(P) denote thesegment topology. For any family of posetsP _j ?_j∈Jθ_s(P_j)=θ_s(?_j∈JP_i) iff at most a finite number of theP _j has more than one element (1.1).
2. Let θ_cs(P) denote theco-segment topology (lower topology). For any family of lower directed posetsP _j ?_j∈Jθ_cs(P_i)=θ_cs(?_j∈JP_i) iff eachP _j has a least element (1.5).
3. Let θ_i(P) denote theinterval topology. For a finite family of chainsP _j,P _j ?_j∈Jθ_i(P_i)=θ_i(?_j∈JP_i) iff for allj∈k, P _j has a greatest element orP _k has a least element (2.11).
4. Let θ_ni(P) denote thenew interval topology. For any family of posetsP _j,P _j ?_j∈Jθ_ni(P_j)=θ_ni(?_j∈JP_j) whenever the product space is ab-space (i.e. a space where the closure of any subsetY is the union of all closures of bounded subsets ofY) (3.13).

In the case oflattices, some of the results presented in this paper are well-known and have been shown earlier in the literature. However, the case of arbitraryposets often proved to be more difficult.     

Arithmetic progressions in partially ordered sets

Van der Waerden's arithmetic sequence theorem—in particular, the density version of Szemerédi—is generalized to partially ordered sets in the following manner. Let w and t be fixed positive integers and >0. Then for every sufficiently large partially ordered set P of width at most w, every subset S of P satisfying |S||P| contains a chain a ₁, a ₂,..., a ₁ such that the cardinality of the interval [a _i, a _i+1] in P is the same for each i.Research supported by NSF grant DMS 8401281.Research supported by ONR grant N00014-85-K-0769.