     Next: Fixed Point Free Automorphisms Up: Complexity Previous: Basic Issues

## Endomorphism Graphs

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 a |P|-clique. As mentioned in  there currently 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:       Next: Fixed Point Free Automorphisms Up: Complexity Previous: Basic Issues

Bernd.S.W.Schroder