共查询到20条相似文献,搜索用时 15 毫秒
1.
Aleksander Rutkowski 《Order》1985,2(1):61-67
Sufficient conditions for the fixed point property for products of two partially ordered sets are proved. These conditions are formulated in terms of multifunctions (functions with non-empty sets as values). 相似文献
2.
Aleksander Rutkowski 《Order》1989,6(1):1-14
There exist exactly eleven (up to isomorphism and duality) ordered sets of size 10 with the fixed point property and containing no irreducible elements.The great part of the work presented here has been done when the author was visiting Ivan Rival at the University of Ottawa, Department of Computer Science. 相似文献
3.
A simply polynomial time algorithm is given for computing the setup number, or jump number, of an ordered set with fixed width. This arises as an interesting application of a polynomial time algorithm for solving a more general weighted problem in precedence constrained scheduling. 相似文献
4.
It is shown that, if an ordered set P contains at most k pairwise disjoint maximal chains, where k is finite, then every finite family of maximal chains in P has a cutset of size at most k. As a corollary of this, we obtain the following Menger-type result that, if in addition, P contains k pairwise disjoint complete maximal chains, then the whole family, M
(P), of maximal chains in P has a cutset of size k. We also give a direct proof of this result. We give an example of an ordered set P in which every maximal chain is complete, P does not contain infinitely many pairwise disjoint maximal chains (but arbitrarily large finite families of pairwise disjoint maximal chains), and yet M
(P) does not have a cutset of size <x, where x is any given (infinite) cardinal. This shows that the finiteness of k in the above corollary is essential and disproves a conjecture of Zaguia. 相似文献
5.
It is shown that every partially ordered set with the fixed point property and with ten or fewer elements actually has the strong fixed point property.Supported by NSERC Operating Grant A7884.Supported by NSERC Operating Grant 41702. 相似文献
6.
The partially ordered set P is an (, , ) ordered set if the width of P, the length of any chain of P and the cut-set number . We will prove that if P is an (, , ) ordered set then P contains a simple (, , ) ordered set and use this result to prove that if P has the 3 cutset property, then width of P length of P+3. 相似文献
7.
When does the fixed point property of a finite ordered set imply its dismantlability by irreducible elements? For instance, if it has width two. Although every finite ordered set is dismantlable by retractible (not necessarily irreducible) elements, surprisingly, a finite, dimension two ordered set, need not be dismantlable by irreducible elements. If, however, a finite ordered set with the fixed point property is N-free and of dimension two, then it is dismantlable by irreducibles. A curious consequence is that every finite, dimension two ordered set has a complete endomorphism spectrum. 相似文献
8.
We show that the fixed point property is comparability invariant for finite ordered sets; that is, if P and Q are finite ordered sets with isomorphic comparability graphs, then P has the fixed point property if and only if Q does. In the process we give a characterization of comparability invariants which can also be used to give shorter proofs of some known results. 相似文献
9.
It is NP-complete to determine whether a given ordered set has a fixed point free order-preserving self-map. On the way to this result, we establish the NP-completeness of a related problem: Given ordered sets P and Q with t-tuples (p 1, ... , p t) and (q 1, ... , q t) from P and Q respectively, is there an order-preserving map f: P→Q satisfying f(p i)≥q i for each i=1, ... , t? 相似文献
10.
John Ginsburg 《Order》1986,3(1):21-38
An ordered set P is said to have the 2-cutset property if for every element x of P there is a subset S of P whose elements are noncomparable to x, such that |S|2 and such that every maximal chain in P meets {x}S. It is shown that if P has the 2-cutset property and has width n then P contains a ladder of length [1/2(n–3)]. 相似文献
11.
This problem motivates the present work: If ordered sets X and Y both have the fixed point property for order preserving maps has their product as well? Here we present a related condition — the so-called strong fixed point property — which arises from naive attempts to solve the problem. We are concerned with determining the nature and extent of this property. Several questions are raised concerning its relation to the fixed point property and other conditions such as dismantlability and contractibility. 相似文献
12.
Dwight Duffus 《Order》1984,1(1):83-92
Recently there has been significant progress in the study of powers of ordered sets. Much of this work has concerned cancellation laws for powers and uses these two steps. First, logarithmic operators are introduced to transform cancellation problems for powers into questions involving direct product decompositions. Second, refinement theorems for direct product decompositions are brought to bear. Here we present two results with the aim of highlighting these steps.Supported by NSF grant MCS 83-02054 相似文献
13.
Zbigniew Lonc 《Order》1994,11(2):149-158
We show that in an ordered setP of width 3 there always exists a fibre (i.e., a subset intersecting each maximal nontrivial antichain) of size at most 11/18|P|. This improves previously known results.Research supported by Polish KBN Grant 2 2037 92 03. 相似文献
14.
The PT-order, or passing through order, of a poset P is a quasi order defined on P so that ab holds if and only if every maximal chain of P which passes throug a also passes through b. We show that if P is chain complete, then it contains a subset X which has the properties that (i) each element of X is -maximal, (ii) X is a -antichain, and (iii) X is -dominating; we call such a subset a -good subset of P. A -good subset is a retract of P and any two -good subsets are order isomorphic. It is also shown that if P is chain complete, then it has the fixed point property if and only if a -good subset also has the fixed point property. Since a retract of a chain complete poset is also chain complete, the construction may be iterated transfinitely. This leads to the notion of the core of P (a -good subset of itself) which is the transfinite analogue of the core of a finite poset obtained by dismantling.Research partially supported by grants from the National Natural Science Foundation of China and The Natural Science Foundation of Shaanxi province.Research supported by NSERC grant #69-0982. 相似文献
15.
Van der Waerden's arithmetic sequence theorem—in particular, the density version of Szemerédi—is generalized to partially ordered sets in the following manner. Let w and t be fixed positive integers and >0. Then for every sufficiently large partially ordered set P of width at most w, every subset S of P satisfying |S||P| contains a chain a
1, a
2,..., a
1 such that the cardinality of the interval [a
i, a
i+1] in P is the same for each i.Research supported by NSF grant DMS 8401281.Research supported by ONR grant N00014-85-K-0769. 相似文献
16.
Bernd S. W. Schröder 《Order》1992,9(4):311-319
The following theorem is proved: If Q=L{P
t
tT} is a finite lexicographic sum of posets such that T and all P
t
have the strong fixed point property then Q has the strong fixed point property. Moreover we show the strong fixed point property for two more classes of posets. 相似文献
17.
An ordered set which has the fixed point property but not the strong fixed point property is presentedSupported by NSERC Operating Grant A7884.Supported by NSERC Operating Grant 41702. 相似文献
18.
Josef Niederle 《Order》1995,12(2):189-210
Boolean ordered sets generalize Boolean lattices, and distributive ordered sets generalize distributive lattices. Ideals, prime ideals, and maximal ideals in ordered sets are defined, and some well-known theorems on Boolean lattices, such as the Glivenko-Stone theorem and the Stone representation theorem, are generalized to Boolean ordered sets. A prime ideal theorem for distributive ordered sets is formulated, and the Birkhoff representation theorem is generalized to distributive ordered sets. Fundamental are the embedding theorems for Boolean ordered sets and for distributive ordered sets.Financial support of the Grant Agency of the Czech Republic under the grant No. 201/93/0950 is gratefully acknowledged. 相似文献
19.
Every linear extension L: [x
1<x
2<...<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
2+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. 相似文献
20.
Bernd S. W. Schröder 《Order》1993,10(4):329-347
We introduce retractable points and show how this notion provides the key for a classification of all sets with 11 elements that have the fixed point property. 相似文献