Recall that a graph is a pair G=(V,E) of a set V of vertices and a set E of doubleton subsets of V, called edges. The induced subgraph of a graph G=(V,E) with vertex set is the graph . Unless otherwise stated all subgraphs will be induced subgraphs.
The choice of language can be justified by the following
Proof: `` ": If is an order-preserving self map then is in particular well-defined and thus for all . Now let . Then since is order-preserving the logical statement
is true and is an edge in .
`` ": Let be such that the induced subgraph of with vertex set is a complete graph with for all . The latter immediately shows that is well-defined, i.e., a function. Now let with , . If , then, since
is a true logical statement, we have . Thus is order-preserving. \
Based on criterion 2.7 various kinds of order-preserving self maps can be identified in the endomorphism graph.
Theorem 2.7 is applicable to infinite ordered sets. For the computationally more interesting finite case the condition for all p can be replaced with the demand that has |P| vertices. With regards to fixed point free order-preserving maps on finite ordered sets we obtain:
Proof: This follows directly from the analogue of Theorem 2.7 for fixed point free order-preserving self maps. Just note that by Remark 2.5 any complete subgraph of the endomorphism graph has at most one vertex in each . \
In order to decide if a finite ordered set P has a fixed point
free order-preserving self map one would thus need to decide if
the fixed point free endomorphism graph has
As mentioned in 
are algorithms that determine the maximal size of a
clique in a graph in acceptable time for graphs with up to
400 to 1000 vertices. As the fixed point free endomorphism
graph of P has at most |P|(|P|-1) vertices and normally actually
fewer than that, this means the fixed point property can be
determined through the fixed point free endomorphism graph for
ordered sets with up to 20 (guaranteed) to (possibly)
50 or more points.
To decide if a finite ordered set P has a fixed point free automorphism one would need to decide if the fixed point free endomorphism graph has a complete induced subgraph as described in part 3 of Proposition 2.8 and Corollary 2.9. To get a completely analogous formulation consider: