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.     

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.     

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.     

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.     

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.     

Exact bounds on the order of torsion points of curves of genus 1

Let k be an algebraic number field of degree n on ₂; and , respectively, the curves on k; let, and _m, '_m be the bases of groups of all points of order m on and g, respectively. A proof of the following theorem is sketched: let p>3 be prime; if, then (p^t)6n; if k, then (p^t)4n. The resulting bounds are unimprovable.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 151, pp. 57–65, 1986.     

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.     

One-third-integrality in the max-cut problem

Given a graphG = (V, E), the metric polytopeS (G) is defined by the inequalitiesx(F) – x(CF) |F| – 1 for , |F| odd,C cycle ofG, and 0 x _e 1 fore E. Optimization overS (G) provides an approximation for the max-cut problem. The graphG is called 1/d-integral if all the vertices ofS(G) have their coordinates in{i/d 0 i d}. We prove that the class of 1/d-integral graphs is closed under minors, and we present several minimal forbidden minors for 1/3-integrality. In particular, we characterize the 1/3-integral graphs on seven nodes. We study several operations preserving 1/d-integrality, in particular, thek-sum operation for 0 k 3. We prove that series parallel graphs are characterized by the following stronger property. All vertices of the polytopeS (G) {x x u} are 1/3-integral for every choice of 1/3-integral bounds, u on the edges ofG. Research by this author was partially done at CWI in Amsterdam.Research by this author was done at the Institut für Diskrete Mathematik of Bonn, supported by the A. von Humboldt Foundation.Deceased on April 2nd, 1995.     

Lipschitz and darbo conditions for the superposition operator in ideal spaces

Summary In this paper we give necessary and sufficient conditions for the superposition operator Fx(s)=f(s, x(s)) to satisfy a Lipschitz condition Fx₁ - Fx₂kx₁ - x₂ or a Darbo condition (FN)k(N) in ideal spaces of measurable functions, where is the Hausdorff measure of noncompactness. Moreover, we characterize a large class of spaces in which the above mentioned two conditions are equivalent.

---

Sunto In questo lavoro diamo delle condizioni necessarie e sufficienti perchè l'operatore di sovrapposizione Fx(s)=f (s, x(s)) soddisfi alla condizione di Lipschitz Fx₁–Fx₂ kx₁–x₂ o quella di Darbo (FN)k(N) in spazi ideali di funzioni misurabili, ove è la misura di non compattezza di Hausdorff. Inoltre, caratterizziamo un'ampia classe di spazi in cui le suddette due condizioni sono equivalenti.

     

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

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.     

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.     

Quasi-additive functions

Summary Let 0 < 1 and letX, Y be real normed spaces. In this paper we consider the following functional inequality:f(x + y) – f(x) – f(y) min{f(x + y), f(x) + f(y)} forx, y R, wheref: X Y. Mainly continuous solutions are investigated. In the case whereY = R some necessary and some sufficient conditions for this inequality are given.Let 0 <1. The following functional inequality has been considered in [5]:f(x + y) – f(x) – f(y) min{f(x + y), f(x) + f(y)} forx, y R, wheref: R R. It appeared that the solutions of this inequality have properties very similar to those of additive functions (cf. [1], [2], [3]). The inequality under consideration seems to be interesting also because of its physical interpretation (cf. [5]). In this paper we shall consider this inequality in a more general case, wheref is defined on a real normed space and takes its values in another real normed space.The first part of the paper concerns the general case; in the second part we assume that the range off is inR.     

Approximation by infinitely divisible distributions in the multidimensional case

Let be the collection of parallelepipeds in R with edges parallel with the coordinate axes and let be the collection of closed sets in R. Let (G, H)=inf {G{A}H{A}+, H{A}G{A}+ for any; L(G, H)= inf {G{A}H{A}+, H{A}G{A}+ for any, where G, H are distributions in . In the paper one gives the proofs of results announced earlier by the author (Dokl. Akad. Nauk SSSR,253, No. 2, 277–279 (1980)). One considers the problem of the approximation of the distributions of sums of independent random vectors with the aid of infinitely divisible distributions. One obtains estimates for the distances (·, ·), L(·, ·) and. It is proved that, where 0p_i1, ; E is the distribution concentrated at zero; V_i(i=1, ..., n) are arbitrary distributions; the products and the exponentials are understood in the sense of convolution.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 130, pp. 89–103, 1983.     

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.     

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.

     

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.     

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.     

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.     

On very weak entire solutions of nonlinear partial differential equations

Let us consider the variational equation in R ⁿ