Products of chains with monochromatic maximal chains and antichains

There is a product of two linear orders of size with the property that every subset or complement thereof contains a maximal chain. Furthermore, for regular , there is a product of two linear orders of size ₊₂ that when colored with fewer than colors always has a monochromatic maximal chain. As a corollary, for every uncountable strong limit cardinal , there is an ordered set of cardinality that must be colored with at least colors before no monochromatic maximal chains are present. Duals of these results show that at least as much is true for maximal antichains.Research supported in part by ONR Grant N00014-91-J-1150.     

Decompositions of partially ordered sets into chains and antichains of given size

Every partially ordered set P on at least (1+o(1))n ³ elements can be decomposed into subposets of size n that are almost chains or antichains. This lower bound on P is asymptotically best possible. Similar results are presented for other types of combinatorial structures.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences, grant 1-3-86-264.     

The minimum of the antichains in the factor poset

Denote g(m, n) the minimum of min A, where A is a subset of {1, 2, ..., m} of size n and there do not exist two distinct x and y in A such that x divides y. We use a method of poset to prove that g(m, n)=2 ⁱ for positive integer ilog₃ m and 1+s(m, i–1), where s(m, i) is the number of odd integers x such that m/3 ⁱ .Research was supported by National Science Council of Republic of China under Grant NSC74-0201-M008d-02.     

A companion to Grillet's Theorem on maximal chains and antichains

It is shown that ifP is a poset containing noN, then every minimal cutset inP is an antichain, that the converse also holds whenP is finite, and that this converse fails in general.Research supported by NSERC Grant A-8054.     

Ordered sets with no chains of ideals of a given type

We study the possible order types of chains of ideals in an ordered set. Our main result is this. Given an indecomposable countable order type , there is a finite listA ₁ , ...,A _n of ordered sets such that for every ordered setP the setJ(P) of ideals ofP, ordered by inclusion, contains a chain of type if and only ifP contains a subset isomorphic to one of theA ₁ ^#x03B1; , ...,A _n . The finiteness of the list relies on the notion of better quasi-ordering introduced by Nash-Williams and the properties of scattered chains obtained by Laver.The results presented. here constitute the second chapter of the third cycle thesis presented by the second author before the Claude Bernard University, Lyon (July 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.     

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     

Maximizing antichains in the cube with fixed size of a shadow

In the n-dimensional cube, we determine the maximum size of antichains having a lower shadow of exactly m elements in the k-th level.     

Back-and-forth for systems of antichains

We consider the distributive lattice of all the antichains over a root-system. The main result shows that the first-order theory of the former is determined by that of the latter. It is also shown that this kind of distributive lattices can be thought of as a generalization of that of atomic Boolean algebras.     

Computing on-line the lattice of maximal antichains of posets

We consider the on-line computation of the lattice of maximal antichains of a finite poset . This on-line computation satisfies what we call the linear extension hypothesis: the new incoming vertex is always maximal in the current subposet of . In addition to its theoretical interest, this abstraction of the lattice of antichains of a poset has structural properties which give it interesting practical behavior. In particular, the lattice of maximal antichains may be useful for testing distributed computations, for which purpose the lattice of antichains is already widely used. Our on-line algorithm has a run time complexity of , where |P| is the number of elements of the poset, , |MA(P)| is the number of maximal antichains of and (P) is the width of . This is more efficient than the best off-line algorithms known so far.     

Regressions and monotone chains: A ramsey-type extremal problem for partial orders

Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx ₁<x ₂ <...<x _k such thatg(x ₁)≦g(x ₂)≦...≦g(x _k ). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1) ^k . Dedicated to Paul Erdős on his seventieth birthday Research supported in part by the National Science Foundation under ISP-80-11451.     

On modular lattices generated by chains

We describe the free modular lattice generated by two chains and a single point, under the assumption that there are few meets. Received February 11, 2005; accepted in final form August 11, 2005.     

Infinite antichains in semilattices

In this paper we consider infinite antichains and the semilattices that they generate, mainly in the context of continuous semilattices. Conditions are first considered that lead to the antichain generating a copy of a countable product of the two-element semilattice. Then a special semilattice, called , is defined, its basic properties developed, and it is shown in our main result that a continuous semilattice with an infinite antichain converging to a larger element contains a semilattice copy of . The paper closes with a consideration of countable antichains that converge to a lower element or a parallel element and the kinds of semilattices generated in this context.The first two authors gratefully acknowledge the partial support of the National Science Foundation and the hospitality of Oxford University during the preparation of this paper.     

Inequalities for the greedy dimensions of ordered sets

Every linear extension L: [x ₁<x ₂<...<x _m ] of an ordered set P on m points arises from the simple algorithm: For each i with 0i<m, choose x _i+1 as a minimal element of P–{x _j :ji}. A linear extension is said to be greedy, if we also require that x _i+1 covers x _i in P whenever possible. The greedy dimension of an ordered set is defined as the minimum number of greedy linear extensions of P whose intersection is P. In this paper, we develop several inequalities bounding the greedy dimension of P as a function of other parameters of P. We show that the greedy dimension of P does not exceed the width of P. If A is an antichain in P and |P–A|2, we show that the greedy dimension of P does not exceed |P–A|. As a consequence, the greedy dimension of P does not exceed |P|/2 when |P|4. If the width of P–A is n and n2, we show that the greedy dimension of P does not exceed n ²+n. If A is the set of minimal elements of P, then this inequality can be strengthened to 2n–1. If A is the set of maximal elements, then the inequality can be further strengthened to n+1. Examples are presented to show that each of these inequalities is best possible.Research supported in part by the National Science Foundation under ISP-80110451.Research supported in part by the National Science Foundation under ISP-80110451 and DMS-8401281.     

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.     

On the dimension of the cartesian product of relations and orders

It is known that for incidence structures and , max , wheref dim stands for Ferrers relation. We shall show that under additional assumptions on and , both bounds can be improved. Especially it will be shown that the square of a three-dimensional ordered set is at least four-dimensional.     

About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets

LetP be a finite partially ordered set. The lengthl(x) of an elementx ofP is defined by the maximal number of elements, which lie in a chain withx at the top, reduced by one. Letw(P) (d(P)) be the maximal number of elements ofP which have the same length (which form an antichain). Further let . The numbers and as well as all partially ordered sets for which these maxima are attained are determined.