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.     

First order properties of random posets

Let =(n,p) be a binary relation on the set [n]={1, 2, ..., n} such that (i,i) for every i and (i,j) with probability p, independently for each pair i,j [n], where i<j. Define as the transitive closure of and denote poset ([n], ) by R(n, p). We show that for any constant p probability of each first order property of R(n, p) converges as n .     

Transversals of families in complete lattices,and torsion in product modules

Suppose L is a complete lattice containing no copy of the power-set 2 and no uncountable well-ordered chains. It is shown that for any family of nonempty subsets , one can choose elements p _i X _i so that _A p _i majorizes all elements of all but finitely many of the X _i . Ring-theoretic consequences are deduced: for instance, the direct product of a family of torsion modules over a commutative Noetherian integral domain R is torsion if and only if some element of R annihilates all but finitely many of the modules.     

Fine Analysis of the Quasi-Orderings on the Power Set

We pursue the fine analysis of the quasi-orderings and on the power set of a quasi-ordering (Q,). We set X Y if every xX is majorized in by some yY, and X Y if every yY is minorized in by some xX. We show that both these quasi-orderings are -wqo if and only if the original quasi-ordering is ( )-wqo. For this holds also restricted to finite subsets, thus providing an example of a finitary operation on quasi-orderings which does not preserve wqo but preserves bqo.     

Transfinite interpolation on the medians of a triangle and best L 1-approximation

Let be a triangle in and let be the set of its three medians. We construct interpolants to smooth functions using transfinite (or blending) interpolation on The interpolants are of type f(₁)+g(₂)+h(₃), where (₁,₂,₃) are the barycentric coordinates with respect to the vertices of . Based on an error representation formula, we prove that the interpolant is the unique best L¹-approximant by functions of this type subject the function to be approximated is from a certain convexity cone in C³().Received: 17 December 2003     

Gray codes from antimatroids

We show three main results concerning Hamiltonicity of graphs derived from antimatroids. These results provide Gray codes for the feasible sets and basic words of antimatroids.For antimatroid (E, ), letJ( ) denote the graph whose vertices are the sets of , where two vertices are adjacent if the corresponding sets differ by one element. DefineJ( ;k) to be the subgraph ofJ( )² induced by the sets in with exactlyk elements. Both graphsJ( ) andJ( ;k) are connected, and the former is bipartite.We show that there is a Hamiltonian cycle inJ( )×K ₂. As a consequence, the ideals of any poset % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf% gDOfdaryqr1ngBPrginfgDObYtUvgaiuaacqWFpepuaaa!414C!\[\mathcal{P}\] may be listed in such a way that successive ideals differ by at most two elements. We also show thatJ( ;k) has a Hamilton path if (E, ) is the poset antimatroid of a series-parallel poset.Similarly, we show thatG( )×K ₂ is Hamiltonian, whereG( ) is the basic word graph of a language antimatroid (E, ). This result was known previously for poset antimatroids.Research supported in part by NSERC.Research supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A3379.     

Comparing different classes of absolutely summing multilinear operators

Let C denote the composition operator defined on the standard Hardy spaces H^p as where is an analytic self-map of the unit disk in the complex plane. In this paper we discuss those invariant subspaces of C in H^p which are invariant under the shift operator, We restrict our attention to the case where is an inner function. Our main result characterises these invariant subspaces. We also consider C when restricted to such an invariant subspace and we describe the structure of the operator and find a formula for the essential spectral radius.Received: 27 January 2004     

Approximation in the mean by bounded analytic functions

Let 1<p< and . LetC _q denote the Bessel capacity in the plane. Let be the set of homomorphisms ofH (G) such that (z)= and letNP denote the set of points in G for which is not a peak set forH (G). In this note, we show that ifC _q (NP)=0, thenH (G) is dense inL _a ^p (G), the Bergman space overG.Partially supported by NSF DMS-9401234     

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.     

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.     

Random graphs and covering graphs of posets

For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n ^-1+(n) ,where (n) is bounded away from 0, then there is a constant k ₀>0 such that, for a.e. G _p , c(G _p )k ₀ n ¹⁺⁽ⁿ⁾ .In other words, to make G _p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n ^-1+(n) , where (n)0, thenc(G _p )=o(n ¹⁺⁽ⁿ⁾ ), almost surely.Partially supported by MCS Grant 8104854.     

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.     

Maximum antichains in the product of chains

Let P be the poset k ₁ × ... × k _n , which is a product of chains, where n1 and k ₁ ... k _n 2. Let . P is known to have the Sperner property, which means that its maximum ranks are maximum antichains. Here we prove that its maximum ranks are its only maximum antichains if and only if either n=1 or M1. This is a generalization of a classical result, Sperner's Theorem, which is the case k ₁= ... =k _n =2. We also determine the number and location of the maximum ranks of P.Research supported in part by the National Science Foundation 10/25/83.     

Some generalizations of Property B and the splitting property

The set system satisfiesProperty B if there exists a partitionX ₁X ₂=X such that any element of intersects both classes. Here, we study the following problem: We are givenk set systems on the underlying setX, and we are seeking ak-partition ofX such that any element of theith set system intersectsX _i for everyi.The paper received its final form when the author enjoyed the hospitality of L.A. Székely of the University of South Carolina, Columbia, South Carolina, USA. The research was partially supported by the Hungarian Scientific Fund, Grant no. T16358.     

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.     

On context patterns associated with concept lattices

In this paper, we consider the following reconstruction problem: Given two ordered sets (G, ) and (M, ) representing join- and meet-irreducible elements, respectively together with three relationsJ,, onG×M modelling comparability (gm) and maximal noncomparability with respect tog (gm, butgm*) and with respect tom (gm, butgm*). We determine necessary and sufficient conditions for the existence of a finite latticeL and injections :GJ(L) and :MM(L) such that the given order relations and the abstract relations coincide with the one induced by the latticeL.     

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

Large-Scale Regularities of Lattice Embeddings of Posets

Let N denote the set of natural numbers and let P =(N ^k , ) be a countably infinite poset on the k-dimensional lattice N ^k . Given x N ^k , we write max(x) (min(x)) for the maximum (minimum) coordinate of x. Let be the directed-incomparability graph of P which is defined to be the graph with vertex set equal to N ^k and edge set equal to the set of all (x, y) such that max(x) max(y) and x and y not comparable in P. For any subset D N ^k , we let P _D and _D denote the restrictions of P and to D. Points x N ^k with min(x) = 0 will be called boundary points. We define a geometrically natural notion of when a point is interior to P or relative to the lattice N ^k , and an analogous notion of monotone interior with respect to or _D . We wish to identify situations where most of these interior points are exposed to the boundary of the lattice or, in the case of monotone interior points, not concealed very much from the boundary. All of these ideas restrict to finite sublattices F ^k and/or infinite sublattices E ^k of N ^k . Our main result shows that for any poset P and any arbitarily large integer M > 0, there is an F E with F = M where, relative to the sublattices F ^k E ^k , the ideal situation of total exposure of interior points and very little concealment of monotone interior points must occur. Precisely, we prove that for any P =(N ^k , ) and any integer M > 0, there is an infinite E N and a finite D F ^k with F E and F = M such that (1) every interior vertex of P _{E k} or _{E k} is exposed and (2) there is a fixed set C E, C k ^k , such that every monotone-interior point of _D belonging to F ^k has its monotone concealment in the set C. In addition, we show that if P ¹ =(N ^k , ₁),..., P ^r =(N ^k , _r ) is any sequence of posets, then we can find E,D, and F so that the properties (1) and (2) described above hold simultaneously for each P ⁱ . We note that the main point of (2) is that the bound k ^k depends only on the dimension of the lattice and not on the poset P. Statement (1) is derived from classical Ramsey theory while (2) is derived from a recent powerful extension of Ramsey theory due to H. Friedman and shown by Friedman to be independent of ZFC, the usual axioms of set theory. The fact that our result is proved as a corollary to a combinatorial theorem that is known to be independent of the usual axioms of mathematics does not, of course, mean that it cannot be proved using ZFC (we just couldn"t find such a proof). This puts our geometrically natural combinatorial result in a somewhat unusual position with regard to the axioms of mathematics.     

On computing the number of subgroups of a finite Abelian group

We consider the numberN _A (r) of subgroups of orderp ^r ofA, whereA is a finite Abelianp-group of type =₁,₂,..., _l ()), i.e. the direct sum of cyclic groups of order ⁱⁱ. Formulas for computingN _A (r) are well known. Here we derive a recurrence relation forN _A (r), which enables us to prove a conjecture of P. E. Dyubyuk about congruences betweenN _A (r) and the Gaussian binomial coefficient .     

A Minkowski-type theorem for covering minima in the plane

For a convex bodyKE ² and a latticeLE ² let _i (K, L),i=1, 2, denote its covering minima introduced by Kannan and Lovasz. We show ₁(K, L) ₂(K, L)V(K)3/4 det(L), whereV denotes the area. This inequality is tight and there are five different cases of equality.