Cores and retracts

Theretracts (idempotent, isotone self-maps) of an ordered set are naturally ordered as functions. In this note we characterize the possible ways that one retract can cover another one. This gives some insight into the structure of the ordered set of retracts and leads to a natural generalization of the core of an ordered set.Supported by NSERC Operating Grant 41702.     

A bound of the exterior arcs for a univalent mapping

In this paper we consider the intersection of the circle ¦w|=x with the image of the disc ¦z|&#x2264;r, 0f(z)=z+c₂z²+... which is univalent analytic in ¦z|<1. Earlier I. E. Bazilevich proved that for xc^/er the measure of the above intersection does not exceed the measure of the intersection produced by the functionf ^*(z)=z/(1–z)², ¦=1. In this paper I. E. Bazilevich's ideas are used to strengthen some of his results.Translated from Matematicheskie Zametki, Vol. 18, No. 3, pp. 367–378, September, 1975.     

On the number of nowhere zero points in linear mappings

LetA be a nonsingularn byn matrix over the finite fieldGF _q ,k=n/2,q=p ^a ,a1, wherep is prime. LetP(A,q) denote the number of vectorsx in (GF _q ) ⁿ such that bothx andAx have no zero component. We prove that forn2, and ,P(A,q)[(q–1)(q–3)] ^k (q–2) ^n–2k and describe all matricesA for which the equality holds. We also prove that the result conjectured in [1], namely thatP(A,q)1, is true for allqn+23 orqn+14.     

Two combinatorial problems on posets

Bialostocki proposed the following problem: Let nk2 be integers such that k|n. Let p(n, k) denote the least positive integer having the property that for every poset P, |P|p(n, k) and every Z _k -coloring f: P Z _k there exists either a chain or an antichain A, |A|=n and _aA f(a) 0 (modk). Estimate p(n, k). We prove that there exists a constant c(k), depends only on k, such that (n+k–2)²–c(k) p(n, k) (n+k–2)²+1. Another problem considered here is a 2-dimensional form of the monotone sequence theorem of Erdös and Szekeres. We prove that there exists a least positive integer f(n) such that every integral square matrix A of order f(n) contains a square submatrix B of order n, with all rows monotone sequences in the same direction and all columns monotone sequences in the same direction (direction means increasing or decreasing).     

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.     

Intrinsic metric preserving maps on partially ordered groups

In [11] Pap proved that a surjective mapf from an abelian lattice ordered groupG ₁ onto an abelian Archimedean lattice ordered group G₂ which preserves non-zero intrinsic metricsd ₁, andd ₂ onG ₁ andG ₂, respectively (i.e.d ₁(x,y)=d₁(z, t) implies d₂(f(x)f(y))= d₂(f(z),f(t))) and satisfiesf(0)=0 is a homomorphism and put the question whether that assertion is true in the case that G₂ is a non-Archimedean lattice ordered group. In this paper it is proved that a surjective map from an abelian directedG ₁ onto a directed group G₂ such thatf(0)=0 is a homomorphism if ¦x –y ¦=¦z – t¦ implies ¦f(x) –f(y)¦=¦f(z) –f(t)¦ and it is shown that the answer to the question of Pap is positive.Presented by M. Henriksen.     

Enumeration of order preserving maps

Three results are obtained concerning the number of order preserving maps of an n-element partially ordered set to itself. We show that any such ordered set has at least 2 ^2n/3 order preserving maps (and 2 ² in the case of length one). Precise asymptotic estimates for the numbers of self-maps of crowns and fences are also obtained. In addition, lower bounds for many other infinite families are found and several precise problems are formulated.Supported by ONR Contract N00014-85-K-0769.Supported by NSF Grant DMS-9011850.Supported by NSERC Grants 69-3378 and 69-0259.     

Outer approximation algorithm for nondifferentiable optimization problems

It is known that the problem of minimizing a convex functionf(x) over a compact subsetX of ⁿ can be expressed as minimizing max{g(x, y)|y X}, whereg is a support function forf[f(x) g(x, y), for ally X andf(x)=g(x, x)]. Standard outer-approximation theory can then be employed to obtain outer-approximation algorithms with procedures for dropping previous cuts. It is shown here how this methodology can be extended to nonconvex nondifferentiable functions.This research was supported by the Science and Engineering Research Council, UK, and by the National Science Foundation under Grant No. ECS-79-13148.     

Sur les espaces analytiques quasi-compacts de dimension 1 sur un corps valué complet ultramétrique

Summary We study the structure of the one dimensional analytic quasi-compact spaces over a complete non archimedean valued field. An affinoid open subset U of a one dimensional analytic quasi-compact space X is defined by a meromorphic function f on X;i.e. U is the set of all x in X such that f is holomorphic at x and ¦f(x)¦1.The set of the meromorphic functions on X which are holomorphic on U is dense in the ring of all holomorphic functions on U. An irreducible, one dimensional quasi-compact space is either affinoid, or projective. An analytic reduction of X is defined by a meromorphic invertible function f on X;i.e. the reduction is isomorphic to the reduction associated to the covering ¦f(x)¦1and ¦f(x)¦1.     

An Erdös-Ko-Rado theorem for the subcubes of a cube

LetP be that partially ordered set whose elements are vectors x=(x ₁, ...,x _n ) withx _i ε {0, ...,k} (i=1, ...,n) and in which the order is given byx≦y iffx _i =y _i orx _i =0 for alli. LetN _i (P)={x εP : |{j:x _j ≠ 0}|=i}. A subsetF ofP is called an Erdös-Ko-Rado family, if for allx, y εF it holdsx ≮y, x ≯ y, and there exists az εN ₁(P) such thatz≦x andz≦y. Let ? be the set of all vectorsf=(f ₀, ...,f _n ) for which there is an Erdös-Ko-Rado familyF inP such that |N _i (P) ∩F|=f _i (i=0, ...,n) and let 〈?〉 be its convex closure in the (n+1)-dimensional Euclidean space. It is proved that fork≧2 (0, ..., 0) and \(\left( {0,...,0,\overbrace {i - component}^{\left( {\begin{array}{*{20}c} {n - 1} \\ {i - 1} \\ \end{array} } \right)}k^{i - 1} ,0,...,0} \right)\) (i=1, ...,n) are the vertices of 〈?〉.     

The endomorphism spectrum of an ordered set

Theendomorphism spectrum of an ordered setP, spec(P)={|f(P)|:f End(P)} andspectrum number, sp(P)=max(spec(P)\{|P|}) are introduced. It is shown that |P|>(1/2)n(n – 1) ^{n – 1} implies spec(P) = {1, 2, ...,n} and that if a projective plane of ordern exists, then there is an ordered setP of size 2n ²+2n+2 with spec(P)={1, 2, ..., 2n+2, 2n+4}. Lettingh(n)=max{|P|: sp(P)n}, it follows thatc ₁ n ²h(n)c ₂ n ⁿ⁺¹ for somec ₁ andc ₂. The lower bound disproves the conjecture thath(n)2n. It is shown that if |P| – 1 spec(P) thenP has a retract of size |P| – 1 but that for all there is a bipartite ordered set with spec(P) = {|P| – 2, |P| – 4, ...} which has no proper retract of size|P| – . The case of reflexive graphs is also treated.Partially supported by a grant from the NSERC.Partially supported by a grant from the NSERC.     

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.     

The many faces of circle orders

A finite partially ordered set P is called a circle order if one can assign to each x P a circular disk C _x so that xy iff C _x C _y . It is interesting to observe that many other classes of posets, such as space-time orders, parabola orders, the Loewner order for 2×2 Hermitian matrices, etc. turn out to be exactly circle orders (or their higher dimensional analogues). We give a global proof for these equivalences.Research supported in part by the Office of Naval Research, the Air Force Office of Scientific Research and by DIMACS.     

On the dimensions of ordered sets of bounded degree

Let P be a partially ordered set. Define k = k (P) = max _p |{x P : p < x or p = x}|, i.e., every element is comparable with at most k others. Here it is proven that there exists a constant c (c < 50) such that dim P < ck(log k)². This improves an earlier result of Rödl and Trotter (dim P 2 k ²+2). Our proof is nonconstructive, depending in part on Lovász' local lemma.Supported in part by NSF under Grant No. MCS83-01867 and by a Sloan Research Fellowship.     

On the distribution of square-full and cube-full numbers

There are many results on the distribution of square-full and cube-full numbers. In this article the distribution of these numbers are studied in more detail. Suchk-full numbers (k=2,3) are considered which are at the same time 1-free (1k+2). At first an asymptotic result is given for the numberN _k,1(x) ofk-full and 1-free numbers not exceedingx. Then the distribution of these numbers in short intervals is investigated. We obtain different estimations of the differenceN _k,1(x+h)–N_k,1(x) in the casesk=2, 1=4,5,6,7,18 andk=3, 1=5,6,7, 18.     

A family of (n−1)! Diagonal polynomial orders ofN n

Letn>0 be an element of the setN of nonnegative integers, and lets(x)=x ₁+...+x _n , forx=(x ₁, ...,x _n ) N _n . Adiagonal polynomial order inN _n is a bijective polynomialp:N _n N (with real coefficients) such that, for allx,y N _n ,p(x)<p(y) whenevers(x)<s(y). Two diagonal polynomial orders areequivalent if a relabeling of variables makes them identical. For eachn, Skolem (1937) found a diagonal polynomial order. Later, Morales and Lew (1992) generalized this polynomial order, obtaining a family of 2 ^n–2 (n>1) inequivalent diagonal polynomial orders. Here we present, for eachn>0, a family of (n – 1)! diagonal polynomial orders, up to equivalence, which contains the Morales and Lew diagonal orders.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

Inequalities for the greedy dimensions of ordered sets

Every linear extension L: [x ₁<x ₂<...<x _m ] of an ordered set P on m points arises from the simple algorithm: For each i with 0i<m, choose x _i+1 as a minimal element of P–{x _j :ji}. A linear extension is said to be greedy, if we also require that x _i+1 covers x _i in P whenever possible. The greedy dimension of an ordered set is defined as the minimum number of greedy linear extensions of P whose intersection is P. In this paper, we develop several inequalities bounding the greedy dimension of P as a function of other parameters of P. We show that the greedy dimension of P does not exceed the width of P. If A is an antichain in P and |P–A|2, we show that the greedy dimension of P does not exceed |P–A|. As a consequence, the greedy dimension of P does not exceed |P|/2 when |P|4. If the width of P–A is n and n2, we show that the greedy dimension of P does not exceed n ²+n. If A is the set of minimal elements of P, then this inequality can be strengthened to 2n–1. If A is the set of maximal elements, then the inequality can be further strengthened to n+1. Examples are presented to show that each of these inequalities is best possible.Research supported in part by the National Science Foundation under ISP-80110451.Research supported in part by the National Science Foundation under ISP-80110451 and DMS-8401281.     

A class of archimedean lattice ordered algebras

This paper introduces a new class of lattice ordered algebras. A lattice ordered algebra A will be called a pseudo f-algebra if xy = 0 for all x, y in A such that x y is a nilpotent element in A. Dierent aspects of archimedean pseudo f-algebras are considered in detail. Mainly their integral representations on spaces of continuous functions, as well as their connection with almost f-algebras and f-algebras. Various characterizations of order bounded multiplicators on pseudo f-algebras are given, where by a multiplicator on a pseudo f-algebra A we mean an operator T on A such that xT(y) = yT(x) for all x, y in A. In this regard, it will be focused on the relationship between multiplicators and orthomorphisms on pseudo f-algebras.     

Singular Nonlinear (n − 1,1) Conjugate Boundary Value Problems

Solutions are obtained for the boundary value problem, y ⁽ⁿ⁾ + f(x,y) = 0, y ⁽ⁱ⁾(0) = y(1) = 0, 0 i n – 2, where f(x,y) is singular at y = 0. An application is made of a fixed point theorem for operators that are decreasing with respect to a cone.