Dimension two,fixed points and dismantlable ordered sets

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.     

Fixed point property and formal concept analysis

The purpose of this paper is to interpret, with the language of formal concept analysis, the fixed point free and order-preserving self-mappings of ordered sets as formal concepts of a context. With this interpretation one can derive a practicable algorithm for determining if a given finite ordered set has the fixed point property. As a side product it is proved that dismantlability of finite ordered sets can be tested in polynomial time.     

The fixed point property in ordered sets of width two

We consider the fixed point property (FPP) in an ordered set of width two (every antichain contains at most two elements). The necessary condition of the FPP and a number of equivalent conditions to the FPP in such sets is established. The product theorem is proved, as well.     

On the strong fixed point property

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.     

The strong fixed point property for small sets

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.     

Comparability invariance of the fixed point property

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.     

On the number of nondismantlable posets with the fixed point property

We give a lower bound for the number of orders on a finite set that are not dismantlable and have the fixed point property. To do so we also derive an upper bound for the number of orders on a finite set that are dismantlable.The author was partially funded by the Office of Naval Research under Contract N00014-88-K-0455.     

The Fixed Point Property for Ordered Sets of Interval Dimension 2

We provide a polynomial time algorithm that identifies if a given finite ordered set is in the class of d2-collapsible ordered sets. For a d2-collapsible ordered set, the algorithm also determines if the ordered set is connectedly collapsible. Because finite ordered sets of interval dimension 2 are d2-collapsible, in particular, the algorithm determines in polynomial time if a given finite ordered set of interval dimension 2 has the fixed point property. This result is also a first step in investigating the complexity status of the question whether a given collapsible ordered set has the fixed point property.     

Fixed points and products

We prove that if the finite ordered setsP andX have the fixed point property then so too doesP×X.Supported by NSERC Operating Grant 41702.     

Fixed points of products and the strong fixed point property

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.     

Fixed point theorems for ordered sets P with P ∖ {a,c} as retract

We prove fixed point theorems for ordered sets P that have a retract with two points less than P and show how they can be used to prove the fixed point property for various well-known and various new ordered sets.     

Fixed points of posets and clique graphs

The fixed point property for partial orders has been the object of much attention in the past twenty years. Recently, M. Roddy ([7]) proved this famous conjecture of Rival (see [6]): the class of finite orders with the fixed point property is closed under finite products.In this article, we prove that a finite order has the fixed point property if the sequence of iterated clique graphs of its comparability graph tends to the trivial graph.     

A fixed point theorem with applications to truncated lattices

We prove a fixed point theorem related to the set P2 of [17]. The result gives access to nontrivial infinite ordered sets with the fixed point property. We also show how the result can be used to provide an elementary proof of part of Baclawski and Björner’s results on truncated lattices.Dedicated to the memory of Ivan RivalReceived December 1, 2002; accepted in final form June 18, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Retractability and the fixed point property for products

LetP, Q be ordered sets and letaP. IfP \ {a} is a retract ofP and setsP and {xP:x>p} (or its dual) have the fixed point property then, for each chain complete setP,P×Q has the fixed point property if and only if (P\{a})×Q has this property. This establishes the fixed point property for some products of ordered sets which are beyond the reach of all known product theorems.The work of the first of authors was supported in part by the K.B.N. Grant No. 2 2037 92 03.     

Multifunctions and the fixed point property for products of ordered sets

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

A note on maximal antichains in ordered sets

We examine the question of when two consecutive levels in a product of -chains form an ordered set such that for any antichain, there is a maximal antichain disjoint from it. We characterize the pairs of consecutive levels in the product of t2 -chains that have this property. We also show that there is no upper bound on the heights of ordered sets having this property.The graph of an ordered set is the graph whose points are the elements of the ordered set, and whose edges are the ordered set's 2-element maximal antichains. We construct a class of ordered sets of all widths at least three such that the graph of each ordered set is a path, and we construct an ordered set of infinite width having a connected graph.Research supported by NSERC undergraduate student summer research fellowship, and by NSERC operating grant 69-3378Research supported by ONR contract N00014-85-K-0769     

Automorphism group and dimension of ordered sets

It is shown that a finite groupG is isomorphic to the automorphism group of a two-dimensional ordered set if and only if it is a generalized wreath product of symmetric groups over an ordered index set that is a dual tree. Furthermore, every finite abelian group is isomorphic to the full automorphism group of a three-dimensional ordered set. Also every finite group is isomorphic to the automorphism group of an ordered set that does not contain an induced crown with more than four elements.     

On the dimension of ordered sets with the 2-cutset property

An ordered setP is said to have 2-cutset property if, for every elementx ofP, there is a setS of elements ofP which are noncomparable tox, with |S|?2, such that every maximal chain inP meets {x}∪S. We consider the following question: Does there exist ordered sets with the 2-cutset property which have arbitrarily large dimension? We answer the question in the negative by establishing the following two results.Theorem: There are positive integersc andd such that every ordered setP with the 2-cutset property can be represented asP=X∪Y, whereX is an ordinal sum of intervals ofP having dimension ?d, andY is a subset ofP having width ?c. Corollary: There is a positive integern such that every ordered set with the 2-cutset property has dimension ?n.     

The fixed point property for small sets

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.     

The strong fixed point property for lexicographic sums

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.