On the automorphism conjecture for products of ordered sets

I. Rival and A. Rutkowski conjectured that the ratio of the number of automorphisms of an arbitrary poset to the number of order-preserving maps tends to zero as the size of the poset tends to infinity. We prove this hypothesis for direct products of arbitrary posets P=S ₁××S _n under the condition that max_i|S_i|=0(n/logn).     

A note on merging

For a finite poset P and x, yP let pr(x>y) be the fraction of linear extensions which put x above y. N. Linial has shown that for posets of width 2 there is always a pair x, y with 1/3 pr(x>y)2/3. The disjoint union C ₁C ₂ of a 1-element chain with a 2-element chain shows that the bound 1/3 cannot be further increased. In this paper the extreme case is characterized: If P is a poset of width 2 then the bound 1/3 is exact iff P is an ordinal sum of C ₁C ₂'s and C ₁'s.     

Real analytic curves in Fréchet spaces and their duals

The following results are presented: 1) a characterization through the Liouville property of those Stein manifoldsU such that every germ of holomorphic functions on xU can be developed locally as a vector-valued Taylor series in the first variable with values inH(U); 2) ifT is a surjective convolution operator on the space of scalar-valued real analytic functions, one can find a solutionu of the equationT u=f which depends holomorphically on the parameterz wheneverf depends in the same manner. These results are obtained as an application of a thorough study of vector-valued real analytic maps by means of the modern functional analytic tools. In particular, we give a tensor product representation and a characterization of those Fréchet spaces or LB-spacesE for whichE-valued real analytic functions defined via composition with functionals and via suitably convergent Taylor series are the same.     

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.     

On the product of sign vectors and unit vectors

For a fixed unit vectora=(a ₁,...,a _n )S ^n-1, consider the 2 ⁿ sign vectors=(₁,..., _n ){±1{ ⁿ and the corresponding scalar products^·a = _n ⁱ⁼¹ = _i a _i . The question that we address is: for how many of the sign vectors must^.a lie between–1 and 1. Besides the straightforward interpretation in terms of the sums ±a ₂ , this question has appealing reformulations using the language of probability theory or of geometry.The natural conjectures are that at least 1/2 the sign vectors yield |.a|1 and at least 3/8 of the sign vectors yield |.a|<1 (the latter excluding the case when |a _i |=1 for somei). These conjectured lower bounds are easily seen to be the best possible. Here we prove a lower bound of 3/8 for both versions of the problem, thus completely solving the version with strict inequality. The main part of the proof is cast in a more general probabilistic framework: it establishes a sharp lower bound of 3/8 for the probability that |X+Y|<1, whereX andY are independent random variables, each having a symmetric distribution with variance 1/2.We also consider an asymptotic version of the question, wheren along a sequence of instances of the problem satisfying ||a||0. Our result, best expressed in probabilistic terms, is that the distribution of .a converges to the standard normal distribution, and in particular the fraction of sign vectors yielding .a between –1 and 1 tends to 68%.This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.     

The poset scheduling problem

Let P and Q be two finite posets and for each pP and qQ let c(p, q) be a specified (real-valued) cost. The poset scheduling problem is to find a function s: PQ such that _pP c(p,s(p)) is minimized, subject to the constraints that p in P implies s(p) in Q. We prove that the poset scheduling problem is NP-hard. This problem with a totally ordered poset Q is proved to be transformable to the closed set problem or the minimum cut problem in a network.This work was done in the fall semester of 1982 when the second author was visiting Cornell University. The first author was his research associate during that period.The first author was supported by National Science Council of Republic of China under Grant NSC73-0208-M008-08 when he wrote the final version of this paper.     

Towards the reconstruction of posets

The reconstruction conjecture for posets is the following: Every finite posetP of more than three elements is uniquely determined — up to isomorphism — by its collection of (unlabelled) one-element-deleted subposets P–{x}:xV(P).We show that disconnected posets, posets with a least (respectively, greatest) element, series decomposable posets, series-parallel posets and interval orders are reconstructible and that N-free orders are recognizable.We show that the following parameters are reconstructible: the number of minimal (respectively, maximal) elements, the level-structure, the ideal-size sequence of the maximal elements, the ideal-size (respectively, filter-size) sequence of any fixed level of the HASSE-diagram and the number of edges of the HASSE-diagram.This is considered to be a first step towards a proof of the reconstruction conjecture for posets.Research partly supported by DAAD.     

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.     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

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 the asymptotic and invariantσ-algebras of random walks on locally compact groups

Summary Consider a random walk of law on a locally compact second countable groupG. Let the starting measure be equivalent to the Haar measure and denote byQ the corresponding Markov measure on the space of pathsG . We study the relation between the spacesL (G , ^a ,Q) andL (G , ⁱ ,Q) where ^a and ⁱ stand for the asymptotic and invariant -algebras, respectively. We obtain a factorizationL (G , ^a ,Q) L (G , ⁱ ,Q)L (C) whereC is a cyclic group whose order (finite or infinite) coincides with the period of the Markov shift and is determined by the asymptotic behaviour of the convolution powers ⁿ.     

Effilement minimal en une singularité isolée de l'équation de Schrödinger et application au principe de Picard

In this paper, the generalized Schrödinger equation (–)u=0 on the punctured unit disk of ² is investigated. If is rotation free and satisfies the Picard principle at the origin, it is shown that if a setE is minimal thin relatively to an extremal harmonic functionh with zero boundary values at {|x|=1}, there exists a sequence (r _n ) converging to zero such that B(O,r _n ) C E. Lete be the -unit. It is proved that if a measure satisfies _\E e h d<, for a minimal thin, relatively toh , setE then the Picard principle is valid for the measure + .

     

3-Interval irreducible partially ordered sets

In this paper we discuss the characterization problem for posets of interval dimension at most 2. We compile the minimal list of forbidden posets for interval dimension 2. Members of this list are called 3-interval irreducible posets. The problem is related to a series of characterization problems which have been solved earlier. These are: The characterization of planar lattices, due to Kelly and Rival [5], the characterization of posets of dimension at most 2 (3-irreducible posets) which has been obtained independently by Trotter and Moore [8] and by Kelly [4] and the characterization of bipartite 3-interval irreducible posets due to Trotter [9].We show that every 3-interval irreducible poset is a reduced partial stack of some bipartite 3-interval irreducible poset. Moreover, we succeed in classifying the 3-interval irreducible partial stacks of most of the bipartite 3-interval irreducible posets. Our arguments depend on a transformationP B(P), such that IdimP=dimB(P). This transformation has been introduced in [2].Supported by the DFG under grant FE 340/2–1.     

Eulerian numbers with fractional order parameters

Summary The aim of this paper is to generalize the well-known Eulerian numbers, defined by the recursion relationE(n, k) = (k + 1)E(n – 1, k) + (n – k)E(n – 1, k – 1), to the case thatn is replaced by . It is shown that these Eulerian functionsE(, k), which can also be defined in terms of a generating function, can be represented as a certain sum, as a determinant, or as a fractional Weyl integral. TheE(, k) satisfy recursion formulae, they are monotone ink and, as functions of , are arbitrarily often differentiable. Further, connections with the fractional Stirling numbers of second kind, theS(, k), > 0, introduced by the authors (1989), are discussed. Finally, a certain counterpart of the famous Worpitzky formula is given; it is essentially an approximation ofx in terms of a sum involving theE(, k) and a hypergeometric function.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

A splitting property of maximal antichains

In anydense posetP (and in any Boolean lattice in particular) every maximal antichainS may be partitioned into disjoint subsetsS ₁ andS ₂, such that the union of the downset ofS ₁ with the upset ofS ₂ yields the entire poset:D(S ₁) U (S ₂) =P. To find a similar splitting of maximal antichains in posets is NP-hard in general.Research was partially carried out when the second author visited the first author in Bielefeld and it was partially supported by OTKA grant T016358     

Counting finite posets and topologies

A refinement of an algorithm developed by Culberson and Rawlins yields the numbers of all partially ordered sets (posets) with n points and k antichains for n11 and all relevant integers k. Using these numbers in connection with certain formulae derived earlier by the first author, one can now compute the numbers of all quasiordered sets, posets, connected posets etc. with n points for n14. Using the well-known one-to-one correspondence between finite quasiordered sets and finite topological spaces, one obtains the numbers of finite topological spaces with n points and k open sets for n11 and all k, and then the numbers of all topologies on n14 points satisfying various degrees of separation and connectedness properties, respectively. The number of (connected) topologies on 14 points exceeds 10²³.     

Upper bound for transversals of tripartite hypergraphs

We prove 2 7/9v for 3-partite hypergraphs. (This is an improvement of the trivial bound 3v.)     

BC-type interpolation Macdonald polynomials and binomial formula for Koornwinder polynomials

We consider 3-parametric polynomialsP ^* (x; q, t, s) which replace theA _n-series interpolation Macdonald polynomialsP ^* (x; q, t) for theBC _n-type root system. For these polynomials we prove an integral representation, a combinatorial formula, Pieri rules, Cauchy identity, and we also show that they do not satisfy any rationalq-difference equation. Ass the polynomialsP ^* (x; q, t, s) becomeP ^* (x; q, t). We also prove a binomial formula for 6-parametric Koornwinder polynomials.     

Some remarks on disjointness preserving operators

In this note we present a simple proof of the following results: if T: E E is a lattice homomorphism on a Banach lattice E, then: i) (T)={1} implies T=I; and ii) r(T–I)<1 implies TZ(E), the center of E.