On trees and tree dimension of ordered sets

We call an ordered set (X, ) a tree if no pair of incomparable elements ofX has an upper bound. It is shown that there is a natural way to associate a tree (T, ) with any ordered set (X, ), and (T, ) can be characterized by a universal property. We define the tree dimensiontd(X, ) of an ordered set as the minimal number of extensions of (X, ) which are trees such that the given order is the intersection of those tree orders. We give characterizations of the tree dimension, relations between dimension and tree dimension, and removal theorems.     

Universal correlations in finite posets

Posets A, BX×X, with X finite, are said to be universally correlated (AB) if, for all posets R over X, (i.e., all posets RY×Y with XY), we have P(RA) P(RB)P(RAB) P(R). Here P(RA), for instance, is the probability that a randomly chosen bijection from Y to the totally ordered set with |Y| elements is a linear extension of RA. We show that AB iff, for all posets R over X, P(RA) P(RB)P(RAB) P(R(AB)).Winkler proved a theorem giving a necessary and sufficient condition for AB. We suggest an alteration to his proof, and give another condition equivalent to AB.Daykin defined the pair (A, B) to be universally negatively correlated (A B) if, for all posets R over X, P(RA) P(RB)P(RAB) P(R(AB)). He suggested a condition for AB. We give a counterexample to that conjecture, and establish the correct condition. We write AB if, for all posets R over X, P(RA) P(RB)P(RAB) P(R). We give a necessary and sufficient condition for AB.We also give constructive techniques for listing all pairs (A, B) satisfying each of the relations AB, AB, and AB.     

Homogeneity in finite ordered sets

A tower in an ordered set (X, ) is defined to be a subsetS ofX which has the property that for everysS there is a maximal chainC in {xX|xs} which is wholly contained inS. An ordered set (X, ) is called tower-homogeneous if every order isomorphism between towers in (X, ) can be extended to an automorphism of (X, ). It is shown that a finite ordered set is tower-homogeneous if and only if it can be built up from singletons stepwise by constructions of three different types.     

Greene-Kleitman's theorem for infinite posets

It is proved that if (P) is a poset with no infinite chain and k is a positive integer, then there exist a partition of P into disjoint chains C _i and disjoint antichains A ₁, A ₂, ..., A _k, such that each chain C _i meets min (k, |C _i|) antichains A _j. We make a dual conjecture, for which the case k=1 is: if (P) is a poset with no infinite antichain, then there exist a partition of P into antichains A _i and a chain C meeting all A _i. This conjecture is proved when the maximal size of an antichain in P is 2.     

Lawless order

R. Baer asked whether the group operation of every (totally) ordered group can be redefined, keeping the same ordered set, so that the resulting structure is an Abelian ordered group. The answer is no. We construct an ordered set (G, ) which carries an ordered group (G, , ) but which islawless in the following sense. If (G, *, ) is an ordered group on the same carrier (G, ), then the group (G, *) satisfies no nontrivial equational law.Research partially supported by NSERC of Canada Grants #A4044 and A3040.Research partially supported by NSERC of Canada Grant #U0075.Research partially supported by a grant from the BSF.     

Infinite ordered sets spanned by finitely many chains

We say that an ordered set P is spanned by a family C of chains if P=(P, ) is the transitive closure of {(C, | C) C C. It is shown that there is a function h: such that if P is spanned by k< chains, then P has a finite cutset-number h(k) (i.e. for any xP, there is a finite set F of size |F|h(k)–1, such that the elements of F are incomparable with x and {x}F meets every maximal chain of P). The function h is exponentially bounded but eventually dominates any polynomial function, even if it is only required that there are at most h(k) pairwise disjoint maximal chains in P, whenever P is spanned by k< chains.     

On the congruence problem in infinite dimensional sesquilinear spaces

If two subspaces V and V of a sesquilinear space E are congruent (i.e., there is an isometry : E E with (V)=V) then their corresponding quadratic lattices V(V, E) and V(V, E) are isomorphic. It is shown that the converse holds for important types of sesquilinear spaces E, provided that dim(E) ₃. However, the converse generally fails if dim(E) ₃.     

The crossing number of posets

The purpose of this paper is to investigate some properties of the crossing number (P) of a posetP. We first study the crossing numbers of the product and the lexicographical sum of posets. The results are similar to the dimensions of these posets. Then we consider the problem of what happens to the crossing number when a point is taken away from a poset. We show that ifP is a poset such that P and (P–)1, then 1/2 (P)(P–)(P). We don't know yet how to improve the lower bound. We also determine the crossing numbers of some subposets of the Boolean latticeB _n which consist of some specified ranks. Finally we show that _n is crossing critical where _n is the subposet ofB _n which is restricted to rank 1, rankn–1 and middle rank(s). Some open problems are raised at the end of this paper.     

Finite cutsets and finite antichains

An ordered set (P,) has the m cutset property if for each x there is a set Fx with cardinality less than m, such that each element of Fx is incomparable to x and {x} Fx meets every maximal chain of (P,). Let n be least, such that each element x of any P having the m cutset property belongs to some maximal antichain of cardinality less than n. We specify n for m < w. Indeed, n-1=m= width P for m=1,2,n=5 if m=3 and n₁ if m 4. With the added hypothesis that every bounded chain has a supremum and infimum in P, it is shown that for 4m₀, n=₀. That is, if each element x has a finite cutset Fx, each element belongs to a finite maximal antichain.This work was supported by the NSERC of Canada.     

Automorphism groups of comparability and covering graphs

Let G be a group and H a subgroup of G. It is shown that there exists a partially ordered set (X, ) such that G is isomorphic to the group of all automorphisms of the comparability graph of (X, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (X, ). There also exists a partially ordered set (Y, ) such that G is isomorphic to the group of all automorphisms of the covering graph of (Y, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (Y, ). In this representation X and Y can be taken to be finite if G is finite and of the same cardinality as G if G is infinite.     

Posets with large dimension and relatively few critical pairs

The dimension of a poset (partially ordered set)P=(X, P) is the minimum number of linear extensions ofP whose intersection isP. It is also the minimum number of extensions ofP needed to reverse all critical pairs. Since any critical pair is reversed by some extension, the dimensiont never exceeds the number of critical pairsm. This paper analyzes the relationship betweent andm, when 3tmt+2, in terms of induced subposet containment. Ifmt+1 then the poset must containS _t , the standard example of at-dimensional poset. The analysis form=t+2 leads to dimension products and David Kelly's concept of a split. Whent=3 andm=5, the poset must contain eitherS ₃, or the 6-point poset called a chevron, or the chevron's dual. Whent4 andm=t+2, the poset must containS _t , or the dimension product of the Kelly split of a chevron andS _t–3, or the dual of this product.     

Lower semicontinuity of attractors of gradient systems and applications

Summary For 0₀, let T(t), t0, be a family of semigroups on a Banach space X with local attractors A. Under the assumptions that T₀(t) is a gradient system with hyperbolic equilibria and T(t) converges to T₀(t) in an appropriate sense, it is shown that the attractors {A, 0₀} are lower-semicontinuous at zero. Applications are given to ordinary and functional differential equations, parabolic partial differential equations and their space and time discretizations. We also give an estimate of the Hausdorff distance between A and A₀, in some examples.Research supported by U.S. Army Research Office DAAL-03-86-K-0074 and the National Science Foundation DMS-8507056.     

Some inequalities for partial orders

We establish some inequalities connecting natural parameters of a partial order P. For example, if every interval [a,b] contains at most maximal chains, if some antichain has cardinality v, and if there are ₁ chains whose union is cofinal and coinitial in P, then the chain decomposition number for P is ₁v (Theorem 2.2), and the inequality is sharp in a certain sense (Section 3).This paper was written while the authors were visitors at the Laboratoire d'algèbre ordinale, Département de Mathématiques, Université Claude Bernard, Lyon 1, France.Research supported by NSERC grant # A5198.     

Cross-cuts in the power set of an infinite set

In the power setP(E) of a setE, the sets of a fixed finite cardinalityk form across-cut, that is, a maximal unordered setC such that ifX, Y E satisfyXY, X someX inC, andY someY inC, thenXZY for someZ inC. ForE=, ₁, and ₂, it is shown with the aid of the continuum hypothesis thatP(E) has cross-cuts consisting of infinite sets with infinite complements, and somewhat stronger results are proved for and ₁.The work reported here has been partially supported by NSERC Grant No. A8054.     

Linear extensions of partial orders preserving monotonicity

Given a poset (A, r) and an acyclic r-monotone function f: AA, we prove that r can be extended to a linear order R with xRyf(x)Rf(y) for all x, yA.     

On Tabor's problem concerning a certain quasi-ordering of iterative roots of functions

Summary Using the Isaacs-Zimmermann's theory of iterative roots of functions, we prove a theorem concerning the problemP 250 posed by J. Tabor:Letf: E E be a given mapping. Denote byF the set of all iterative roots off. InF we define the following relation: if and only if is an iterative root of. The relation is obviously reflexive and transitive. The question is: Is it also antisymmetric? If we consider iterative roots of a monotonic function the answer is yes. But in general the question is open.Here we prove that there exists a three-element decomposition { _i ;i = 1, 2, 3} of the setE ^E with blocks _i of the same cardinality 2^cardE such that the functions from ₁ do not possess any proper iterative root, the quasi-ordering is not antisymmetric onF(f) for anyf ₂, and is an ordering onF(f) for anyf ₃. Iff is a strictly increasing continuous self-bijection ofE, then the relation is an ordering onF(f) ifff is different from the identity mapping of the setE.     

Nowhere dense set mappings on the generalized linear continua

A set is free for a set mapping F:XP(X) provided xF(y) for any distinct x, y in A. If F maps the reals R into nowhere dense subsets of R, then Bagemihl proved that there is an everywhere dense free set for F, and assuming CH Hechler showed that such an F does not always admit an uncountable free set. In this paper, we show that Bagemihl's theorem cannot be generalized to the generalized linear continua C for arbitrarily large ordinal , and under GCH we extend Hechler's theorem to C for every .     

A sandwich theorem and Hyers—Ulam stability of affine functions

It is shown that two real functionsf andg, defined on a real intervalI, satisfy the inequalitiesf(x + (1 – )y) g(x) + (1 – )g(y) andg(x + (1 – )y) f(x) + (1 – )f(y) for allx, y I and [0, 1], iff there exists an affine functionh: I such thatf h g. As a consequence we obtain a stability result of Hyers—Ulam type for affine functions.     

Asymptotic behaviour of minimum problems with bilateral obstacles

Summary In this paper we study the asymptotic behaviour (as h) of the solutions of minimum problems for the functional [¦Du¦²+g(x, u)]dx with bilateral obstacles of the type _hu_h, where _h and _h are sequences of arbitrary functions fromR ⁿ into ¯R.     

Finite presentability of Steinberg groups over group rings

LetA be a finitely generated commutative -algebra with Krull dimensiond, and let be an arbitrary finite group. It is proved that the Steinberg groupSt _n (A) is finitely presented whenevern4. If, in addition,nd+3, andK ₁ (A) andK ₂ (A) are finitely generated, thenE _n (A) andGL _n (A) are finitely presented.The Project supported by National Natural Science Foundation of China.