Networks and chain coverings in partial orders and their products

For an arbitrary poset P, subposets {P _i : 1ik} form a transitive basis of P if P is the transitive closure of their union. Let u be the minimum size of a covering of P by chains within posets of the basis, s the maximum size of a family of elements with no pair comparable in any basis poset, and a the maximum size of an antichain in P. Define a dense covering to be a collection D of chains within basis posets such that each element belongs to a chain in D within each basis poset and is the top of at least k-1 chains and the bottom of at least k-1 chains in D. Dense coverings generalize ordinary chain coverings of poset. Let d=min {|D|–(k–1)|P|}. For an arbitrary poset and transitive basis, a convenient network model for dense coverings yields the following: Theorem 1: da, with equality iff P has a minimum chain decomposition in which every pair of consecutive elements on each chain are comparable in some basis poset. Theorem 2: usda. Theorem 3: s=d iff s=a. The most interesting special case is where the transitive basis expresses P as the product of two posets, in which case u and s measure the minimum and maximum sizes of unichain coverings and semiantichains.     

Posets with large dimension and relatively few critical pairs

The dimension of a poset (partially ordered set)P=(X, P) is the minimum number of linear extensions ofP whose intersection isP. It is also the minimum number of extensions ofP needed to reverse all critical pairs. Since any critical pair is reversed by some extension, the dimensiont never exceeds the number of critical pairsm. This paper analyzes the relationship betweent andm, when 3tmt+2, in terms of induced subposet containment. Ifmt+1 then the poset must containS _t , the standard example of at-dimensional poset. The analysis form=t+2 leads to dimension products and David Kelly's concept of a split. Whent=3 andm=5, the poset must contain eitherS ₃, or the 6-point poset called a chevron, or the chevron's dual. Whent4 andm=t+2, the poset must containS _t , or the dimension product of the Kelly split of a chevron andS _t–3, or the dual of this product.     

The free \mathfrak{m} -lattice on the poset H

Let H={a ₀, a ₁, a ₂, b ₀, b ₁, b ₂} be the poset defined by a ₀<a ₂<a ₁, b ₀<b ₂<b ₁, a ₀<b ₁, and b ₀<a ₁. For an infinite regular cardinal , we describe the free -lattice on H. This continues the work of I. Rival and R. Wille who accomplished the same for =. In subsequent papers, we show how to apply this result to describe the free -lattice on a poset for a large class of posets, called slender posets.     

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.     

Games of Chains and Cutsets in the Boolean Lattice II

Let 2 ^[n] denote the poset of all subsets of [n]={1,2,...,n} ordered by inclusion. Following Gutterman and Shahriari (Order 14, 1998, 321–325) we consider a game G _n (a,b,c). This is a game for two players. First, Player I constructs a independent maximal chains in 2 ^[n]. Player II will extend the collection to a+b independent maximal chains by finding another b independent maximal chains in 2 ^[n]. Finally, Player I will attempt to extend the collection further to a+b+c such chains. The last Player who is able to complete her move wins. In this paper, we complete the analysis of G _n (a,b,c) by considering its most difficult instance: when c=2 and a+b+2=n. We prove, the rather surprising result, that, for n7, Player I wins G _n (a,n–a–2,2) if and only if a3. As a consequence we get results about extending collections of independent maximal chains, and about cutsets (collections of subsets that intersect every maximal chain) of minimum possible width (the size of largest anti-chain).     

Constructing a perfect duality in infinite programming

One version of the infinite Farkas Lemma states the equivalence of two conditions, (1)yb 0 wheneverya ^j 0 forj=1,2,.. and (2)b cl C, whereb and alla ^j are inR ⁿ andC is the convex cone spanned by all thea ^j 's. In this paper an ascent vector specifies a direction along which an arbitrarily small movement fromb with enterC. A Fredholm type theorem of the alternative characterizes the set of all ascent vectors associated with an arbitrary system of linear inhomogeneous inequalities in a finite number of variables. As a consequence, a pair of infinite programs is constructed which is in perfect duality in the sense that (p1) if one program is consistent and has finite value, then the other is consistent and (p2) if both programs are consistent, then they have the same finite value. The duality is sharp in that the set of all feasible perturbations along rays is determined.This research was supported by NSF Grants GK-31833 and ENG76-05191. The paper is a revision of an earlier report of June 1975.     

The Involutory Dimension of Involution Posets

The involutory dimension, if it exists, of an involution poset P:=(P,,) is the minimum cardinality of a family of linear extensions of , involutory with respect to , whose intersection is the ordering . We show that the involutory dimension of an involution poset exists iff any pair of isotropic elements are orthogonal. Some characterizations of the involutory dimension of such posets are given. We study prime order ideals in involution posets and use them to generate involutory linear extensions of the partial ordering on orthoposets. We prove several of the standard results in the theory of the order dimension of posets for the involutory dimension of involution posets. For example, we show that the involutory dimension of a finite orthoposet does not exceed the cardinality of an antichain of maximal cardinality. We illustrate the fact that the order dimension of an orthoposet may be different from the involutory dimension.     

Homological Dimension of Coalgebras and Crossed Coproducts

Let H be a Hopf k-algebra. We study the global homological dimension of the underlying coalgebra structure of H. We show that gl.dim(H) is equal to the injective dimension of the trivial right H-comodule k. We also prove that if D = C H is a crossed coproduct with invertible , then gl.dim(D) gl.dim(C) + gl.dim(H). Some applications of this result are obtained. Moreover, if C is a cocommutative coalgebra such that C ^* is noetherian, then the global dimension of the coalgebra C coincides with the global dimension of the algebra C ^*.     

Classification of integral trees

A finite poset Q is called integral over a field k if there exists an ASL (algebra with straightening laws) domain on Q{–} over k. We classify all trees (rank one connected posets without cycles) which are integral over an infinite field.     

On Jump-Critical Posets with Jump-Number Equal to Width

We investigate the structure of m-jump-critical posets P with w(P) = m. We prove that the size of such posets satisfies |P| 3m ². For the special when the maximum antichain occurs as the maximal (or minimal) elements, we have the sharp upper bound |P| 3m - k; where k = min {|{Max}(P)|, |{Min}(P)|}. We give examples of posets which illustrate the explored structure of these m-jump-critical posets P with width m.     

Order series of labelled posets

Order series of labelled posets are multi-analogues of the more familiar order polynomials; the corresponding multi-analogues of the related representation polynomials are calledE-series. These series can be used to describe the effect of composition of labelled posets on their order polynomials, whence their interest for us. We give a reciprocity theorem forE-series, and show that for an unlabelled poset the form of theE-series depends only upon the comparability graph of the poset. We also prove that theE-series of any labelled poset is a rational power series (in many indeterminates) and give an algorithm for computing it which runs in polynomial time when the poset is strictly labelled and of bounded width. Finally, we give an explicit product formula for theE-series of strictly labelled interval posets.This research was supported by the Natural Sciences and Engineering Research Council of Canada under operating grant #0105392.     

Small transversals in hypergraphs

For each positive integerk, we consider the setA _k of all ordered pairs [a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA _k withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points [a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA _k , identify the last three extreme points ofA ₃, and describeA ₂ completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem.     

Uniformly More Powerful, Two-Sided Tests for Hypotheses about Linear Inequalities

Let Xhave a multivariate, p-dimensional normal distribution (p 2) with unknown mean and known, nonsingular covariance . Consider testing H ₀ : b _i 0, for some i = 1,..., k, and b _i 0, for some i = 1,..., k, versus H ₁ : b _i < 0, for all i = 1,..., k, or b _i < 0, for all i = 1,..., k, where b ₁,..., b _k , k 2, are known vectors that define the hypotheses and suppose that for each i = 1,..., k there is an j {1,..., k} (j will depend on i) such that b _i b _j 0. For any 0 < < 1/2. We construct a test that has the same size as the likelihood ratio test (LRT) and is uniformly more powerful than the LRT. The proposed test is an intersection-union test. We apply the result to compare linear regression functions.     

Spanning trees with bounded degrees

Lets andk be positive integers. We prove that ifG is ak-connected graph containing no independent set withks+2 vertices thenG has a spanning tree with maximum degree at mosts+1. Moreover ifs3 and the independence number (G) is such that (G)1+k(s–1)+c for some0ck thenG has a spanning tree with no more thanc vertices of degrees+1.     

A cuspidal edge of first kind with a point of asymptotic type

We shall say that an analytic surface supports a line with a singularity of order 2 if is a singular line of the surface (the first fundamental form of anyC -parametrization of is degenerate on ) and there exists aC -parametrization(s, v) of the surface such that the second derivative of in the direction orthogonal to is nonzero. We shall assume that has no singular points or points of straightening or flattening, that the Gaussian curvature of is nonpositive, and that the Gaussian curvature of has a finite limita(s) on (s is arc length on ), and the osculating plane of is tangent to in the sense that this plane contains as a half-plane the contingency of at the corresponding point of . Finally supposeb(0)=0,b(s)0 fors0, andb _ss (0)0, whereb(s)=a(s)+ ²(s) and is the torsion of . It is shown that under these hypotheses envelopes the asymptotes of one of the families of. All the asymptotes of the other family are tangent to except the asymptote passing through the points=0 of the singular line.Translated from Ukrainskií Geometricheskií Sbornik, No. 30, 1987, pp. 66–76.     

A chain complete poset with no infinite antichain has a finite core

It is well known that dismantling a finite posetP leads to a retract, called the core ofP, which has the fixed-point property if and only ifP itself has this property. The PT-order, or passing through order, of a posetP is the quasi order defined onP so thatab holds if and only if every maximal chain ofP which passes througha also passes throughb. This leads to a generalization of the dismantling procedure which works for arbitrary chain complete posets which have no infinite antichain. We prove that such a poset also has a finite core, i.e. a finite retract which reflects the fixed-point property forP.This research was written while the first author was visiting the University of Calgary.Research supported by NSERC grant #69-0982.     

Cycles and measure of bifurcation sets for two-dimensional diffeomorphisms

Summary We describe a large class of one-parameter families , {}, , of two-dimensional diffeomorphisms which arestable for <0, exhibit acycle for =0, and thereafter have a bifurcation set of positive but arbitrarily smallrelative measure for in small intervals [0, ]. A main assumption is that the basic sets involved in the cycle havelimit capacities that are not too large.The second author acknowledges hospitality and financial support from IMPA/CNPq during the period this paper was prepared     

An Inequality Involving the Local Eigenvalues of a Distance-Regular Graph

Let denote a distance-regular graph with diameter D 3, valency k, and intersection numbers a _i, b _i, c _i. Let X denote the vertex set of and fix x X. Let denote the vertex-subgraph of induced on the set of vertices in X adjacent X. Observe has k vertices and is regular with valency a ₁. Let _{1 2} ··· _k denote the eigenvalues of and observe ₁ = a ₁. Let denote the set of distinct scalars among ₂, ₃, ..., _k . For let mult denote the number of times appears among ₂, ₃,..., _k . Let denote an indeterminate, and let p ₀, p₁, ...,p _D denote the polynomials in [] satisfying p ₀ = 1 andp _i = c _i+1 p _i+1 + (a _i – c _i+1 + c _i)p _i + b _i p _i–1 (0 i D – 1),where p _–1 = 0. We show where we abbreviate = –1 – b ₁(1+)^–1. Concerning the case of equality we obtain the following result. Let T = T(x) denote the subalgebra of Mat _X ( ) generated by A, E*₀, E*₁, ..., E* _D , where A denotes the adjacency matrix of and E* _i denotes the projection onto the ith subconstituent of with respect to X. T is called the subconstituent algebra or the Terwilliger algebra. An irreducible T-module W is said to be thin whenever dimE* _i W 1 for 0 i D. By the endpoint of W we mean min{i|E* _i W 0}. We show the following are equivalent: (i) Equality holds in the above inequality for 1 i D – 1; (ii) Equality holds in the above inequality for i = D – 1; (iii) Every irreducible T-module with endpoint 1 is thin.     

Arithmetic of Finite Ordered Sets: Cancellation of Exponents,II

Garrett Birkhoff conjectured in 1942 that when A, B, P are finite posets satisfying A ^PB ^P, then AB. We show that this is true. Further, we introduce an operation C(A ^B), related to Garrett Birkhoff's exponentiation, and determine the structure of the algebra of isomorphism types of finite posets under the operations induced by A+B, A×B, and C(A ^B). Every finite +-indecomposable and ×-indecomposable poset A of more than one element is expressible for unique (up to isomorphism) E and P as AC(E ^P) where P is connected and E is indecomposable for all three operations.