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.     

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.     

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.     

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.     

The PT-order and the fixed point property

The PT-order, or passing through order, of a poset P is a quasi order defined on P so that ab holds if and only if every maximal chain of P which passes throug a also passes through b. We show that if P is chain complete, then it contains a subset X which has the properties that (i) each element of X is -maximal, (ii) X is a -antichain, and (iii) X is -dominating; we call such a subset a -good subset of P. A -good subset is a retract of P and any two -good subsets are order isomorphic. It is also shown that if P is chain complete, then it has the fixed point property if and only if a -good subset also has the fixed point property. Since a retract of a chain complete poset is also chain complete, the construction may be iterated transfinitely. This leads to the notion of the core of P (a -good subset of itself) which is the transfinite analogue of the core of a finite poset obtained by dismantling.Research partially supported by grants from the National Natural Science Foundation of China and The Natural Science Foundation of Shaanxi province.Research supported by NSERC grant #69-0982.     

On well-ordered mono-unary algebras

Given a linearly ordered set (A, _R ) and an R-monotone function f: AA, we give a necessary and sufficient condition on A, f, _R , involving generating sets and forbidden subalgebras, for _R to be a well-ordering.Partially supported by Hungarian National Foundation for Scientific Research Grant nr. 1813.     

Interpolation of spectra

By the M.Riesz Convexity Theorem, an operator T on the space of simple integrable functions into the measurable functions (on some measure space) which has continuous extensions to L^p() and L^q() , where 1 p q , also has continuous exten — sions to all L^r () , p r q . It is shown that, whenever (T_p) and (T_q) are o-dimensional (in particular, countable) then the spectra (T_r) (p r q) are pairwise identical. For q = , only w^*-continuous extensions are considered. An example due to Dayanithy shows that the conclusion fails in general.     

Estimation of distribution density

The article investigates the asymptotic properties of the estimators of the density P(x) derived using a sample X₁,...,X _n when the distance of the estimator from p(x) is measured in the metricL _p,2p2.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Institute im. V. A. Steklova AN SSSR, Vol. 98, pp. 61–85, 1980.     

On the postulation of a general projection of a curve inP 3

Summary We say that a curve C in P ³ has maximal rank if for every integer k the restriction map r_c(k):H ⁰(P ³, O_P3(k)) H⁰ (C, O_C(k))has maximal rank. Here we prove the following results. Theorem 1Fix integers g, d with 0g3,dg+3.Fix a curve X of genus g and L Pic^d (X).If g=3and X is hyperelliptic, assume d8. Let _L(X)be the image of X by the complete linear system H ⁰(X, L). Then a general projection of _L(X)into P ³ has maximal rank. Theorem 2For every integer g0,there exists an integer d(g, 3)such that for every dd(g, 3),for every smooth curve X of genus g and every LPic^d (X) the general projection of _L(X)into P ³ has maximal rank.     

An iterative process for nonlinear lipschitzian and strongly accretive mappings in uniformly convex and uniformly smooth Banach spaces

SupposeX is ans-uniformly smooth Banach space (s > 1). LetT: X X be a Lipschitzian and strongly accretive map with constantk (0, 1) and Lipschitz constantL. DefineS: X X bySx=f–Tx+x. For arbitraryx ₀ X, the sequence {x_n} _n=1 is defined byx _n+1=(1– _n)x_n+ _nSy_n,y _n=(1– _n)x_n+ _nSx_n,n0, where {_n} _n=0 , {_n} _n=0 are two real sequences satisfying: (i) 0 _n ^p–1 2^–1s(k+k _n–L ²_n)(w+h)^–1 for eachn, (ii) 0 _n ^p–1 min{k/L², sk/(+h)} for eachn, (iii) _{n n}=, wherew=b(1+L)^s andb is the constant appearing in a characteristic inequality ofX, h=max{1, s(s-l)/2},p=min {2, s}. Then {x_n} _n=1 converges strongly to the unique solution ofTx=f. Moreover, ifp=2, _n=2^–1s(k +k–L²)(w+h)^–1, and _n= for eachn and some 0 min {k/L², sk/(w + h)}, then x_{n + 1}–q ^n/sx₁-q, whereq denotes the solution ofTx=f and=(1 – 4^–1s²(k +k – L ²)²(w + h)^–1 (0, 1). A related result deals with the iterative approximation of Lipschitz strongly pseudocontractive maps inX. SupposeX ism-uniformly convex Banach spaces (m > 1) andc is the constant appearing in a characteristic inequality ofX, two similar results are showed in the cases of L satisfying (1 – c²)(1 + L)^m < 1 + c – cm(l – k) or (1 – c²)L^m < 1 + c – cm(1 – s).     

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.     

Quelques resultats d'entropie sur l'espace de Wiener

One studies three problems related to entropy phenomenon in the classical Wiener space. In particular, the minoration of the Wiener measure for the set {xX/(x)} is given where is a Sobolev norm in the Wiener spaceX.

     

Optimal control for the dam problem

Consider the variational inequality for the rectangular dam problem and assume that fluid can be withdrawn from the bottom at a rate proportional tok(x). Denote byp(x, y) the pressure of the fluid in the dam corresponding to a particular choice ofk. Consideringk(x) as a control variable varying in a class {0k(x)N, k(x)dxM}, we introduce the functionalJ(k)=g(y)p(x, y) whereg(y) is a given positive and monotone nondecreasing function. We characterize the controlsk ₀ which minimizeJ(k). This work is partially supported by National Science Foundation MCS-8300293     

The associativity equation revisited

Summary Consideration of the Associativity Equation,x (y z) = (x y) z, in the case where:I × I I (I a real interval) is continuous and satisfies a cancellation property on both sides, provides a complete characterization of real continuous cancellation semigroups, namely that they are topologically order-isomorphic to addition on some real interval: ( – ,b), ( – ,b], –, +), (a, + ), or [a, + ) — whereb = 0 or –1 anda = 0 or 1. The original proof, however, involves some awkward handling of cases and has defied streamlining for some time. A new proof is given following a simpler approach, devised by Páles and fine-tuned by Craigen.     

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.     

Balancing pairs and the cross product conjecture

In a finite partially ordered set, Prob (x>y) denotes the proportion of linear extensions in which elementx appears above elementy. In 1969, S. S. Kislitsyn conjectured that in every finite poset which is not a chain, there exists a pair (x,y) for which 1/3Prob(x>y)2/3. In 1984, J. Kahn and M. Saks showed that there exists a pair (x,y) with 3/11x>y)<8/11, but the full 1/3–2/3 conjecture remains open and has been listed among ORDER's featured unsolved problems for more than 10 years.In this paper, we show that there exists a pair (x,y) for which (5–5)/10Prob(x>y)(5+5)/10. The proof depends on an application of the Ahlswede-Daykin inequality to prove a special case of a conjecture which we call the Cross Product Conjecture. Our proof also requires the full force of the Kahn-Saks approach — in particular, it requires the Alexandrov-Fenchel inequalities for mixed volumes.We extend our result on balancing pairs to a class of countably infinite partially ordered sets where the 1/3–2/3 conjecture isfalse, and our bound is best possible. Finally, we obtain improved bounds for the time required to sort using comparisons in the presence of partial information.An extended abstract of an earlier version of this paper appears as [6]. The results here are much stronger than in [6], and this paper has been written so as to overlap as little as possible with that version.     

Generalizations of Tarski's fixed point theorem for order varieties of complete meet semilattices

A poset P is -conditionally complete ( a cardinal) if every set X P all of whose subsets of cardinality < have an upper bound has a least upper bound. For we characterize the subposets of a -complete poset which can occur as the set of fixed points of some montonic function on P. This yields a generalization of Tarski's fixed point theorem. We also show that for every the class of -conditionally complete posets forms an order variety and we exhibit a simple generating poset for each such class.Research supported in part by NSERC while the author was visiting Professor Ivo Rosenberg at the Université de Montreal.Research supported in part by NSF-grant DMS-8703743.     

The Second Lacuna in the Orders of Movement Groups of the Spaces U n

We prove the nonexistence of symmetrically linearly connected spaces of hyperplane elements admitting a movement group G _r with n ² - n + 2 r n² - 1, n 5.     

On stationary queue length distributions for G/M/s/r queues

Consider aG/M/s/r queue, where the sequence{A _n } _n=– of nonnegative interarrival times is stationary and ergodic, and the service timesS _n are i.i.d. exponentially distributed. (SinceA _n =0 is possible for somen, batch arrivals are included.) In caser < , a uniquely determined stationary process of the number of customers in the system is constructed. This extends corresponding results by Loynes [12] and Brandt [4] forr= (with=ES₀/EA₀<s) and Franken et al. [9], Borovkov [2] forr=0 ors=. Furthermore, we give a proof of the relation min(i, s)¯p(i)=p(i–1), 1ir + s, between the time- and arrival-stationary probabilities¯p(i) andp(i), respectively. This extends earlier results of Franken [7], Franken et al. [9].     

Transversally bounded lattices

A problem stemming from a boundedness question for torsion modules and its translation into ideal lattices is explored in the setting of abstract lattices. Call a complete lattice L transversally bounded (resp., uniformly transversally bounded) if for all families (X _i)_iIof nonempty subsets of L with the property that {x _iiI}<1 for all choices of x _iX _i, almost all of the sets X _ihave join smaller than 1 (resp., _jJ X _jhas join smaller than 1 for some cofinite subset J of I). It is shown that the lattices which are transversally bounded, but not uniformly so, correspond to certain ultrafilters with peculiar boundedness properties similar to those studied by Ramsey. The prototypical candidates of the two types of lattices which one is led to construct from ultrafilters (in particular the lattices arising from what will be called Ramsey systems) appear to be of interest beyond the questions at stake.