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.     

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).     

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.     

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.     

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.     

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.     

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.     

Multiplicative posets

A functionf from the posetP to the posetQ is a strict morphism if for allx, y P withx we havef(x). If there is such a strict morphism fromP toQ we writeP Q, otherwise we writeP Q. We say a posetM is multiplicative if for any posetsP, Q withP M andQ M we haveP ×Q M. (Here (p ₁,q ₁)<(p ₂,q ₂) if and only ifp ₁<p ₂ andq ₁<q ₂.) This paper proves that well-founded trees with height are multiplicative posets.This research was supported in part by NSERC Grant #69-1325.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

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.     

A separation theorem for semicontinuous functions on preordered topological spaces

Suppose that X is a topological space with preorder , and that –g, f are bounded upper semicontinuous functions on X such that g(x) f(y) whenever x y. We consider the question whether there exists a bounded increasing continuous function h on X such that g h f, and obtain an existence theorem that gives necessary and sufficient conditions. This result leads to an extension theorem giving conditions that allow a bounded increasing continuous function defined on an open subset of X to be extended to a function of the same type on X. The application of these results to extremally disconnected locally compact spaces is studied.Received: 26 May 2004     

Certain embedding theorems

We obtain necessary and sufficient conditions such that, for f(x) from LP(0, 1), the integral ₀ ¹ ¦f (x)¦qdx (0<p<1,p<q<p(1 –p)^–1) is convergent, or for f LP[0, 1] for all p 1, the integral ₀ ¹ e¦f(x)¦dx is convergent.Translated from Matematicheskie Zametki, Vol. 19, No. 2, pp. 187–200, February, 1976.     

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.     

Finding normal solutions in piecewise linear programming

Letf: ⁿ (–, ] be a convex polyhedral function. We show that if any standard active set method for quadratic programming (QP) findsx(t)= arg min _x ¦x¦²/2+t f(x) for somet> 0, then its final working set defines a simple equality QP subproblem, whose Lagrange multiplier can be used both for testing ift is large enough forx(t) to coincide with the normal minimizer off, and for increasingt otherwise. The QP subproblem may easily be solved via the matrix factorizations used for findingx(t). This opens up the way for efficient implementations. We also give finite methods for computing the whole trajectory {x(t)} _t 0, minimizingf over an ellipsoid, and choosing penalty parameters inL ₁QP methods for strictly convex QP.This research was supported by the State Committee for Scientific Research under Grant 8S50502206.     

Nonexistence of a Kruskal-Katona Type Theorem for Subword Orders

We consider the poset SO(n) of all words over an n-element alphabet ordered by the subword relation. It is known that SO(2) falls into the class of Macaulay posets, i. e. there is a theorem of Kruskal–Katona type for SO(2). As the corresponding linear ordering of the elements of SO(2) the vip-order can be chosen.Daykin introduced the V-order which generalizes the vip-order to the n2 case. He conjectured that the V-order gives a Kruskal–Katona type theorem for SO(n).We show that this conjecture fails for all n3 by explicitly giving a counterexample. Based on this, we prove that for no n3 the subword order SO(n) is a Macaulay poset.     

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 〈?〉.     

A note on maximal antichains in ordered sets

We examine the question of when two consecutive levels in a product of -chains form an ordered set such that for any antichain, there is a maximal antichain disjoint from it. We characterize the pairs of consecutive levels in the product of t2 -chains that have this property. We also show that there is no upper bound on the heights of ordered sets having this property.The graph of an ordered set is the graph whose points are the elements of the ordered set, and whose edges are the ordered set's 2-element maximal antichains. We construct a class of ordered sets of all widths at least three such that the graph of each ordered set is a path, and we construct an ordered set of infinite width having a connected graph.Research supported by NSERC undergraduate student summer research fellowship, and by NSERC operating grant 69-3378Research supported by ONR contract N00014-85-K-0769     

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.