Abstract
The automorphism conjecture for ordered sets states that the automorphism to endomorphism ratio will tend to zero as the size of the ordered set goes to infinity. We show by computer enumeration that up to size 11 the ratio is largest for weakly ordered sets. Subsequently, we derive exact recursive formulas for the number of homomorphisms between two related types of weakly ordered sets and we prove a strong automorphism conjecture for series-parallel ordered sets. We conclude with an example that shows that the automorphism to endomorphism ratio can exceed \(\displaystyle{ \left( .5244 \right) ^{|P|}} \) for arbitrarily large \(|P|\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Currie, J. and Visentin, T.: Counting endomorphisms of crown-like orders, Order 19 (2002), 305–317.
Duffus, D., Rödl, V., Sands, B. and Woodrow, R.: Enumeration of order-preserving maps, Order 9 (1992), 15–29.
Farley, J. D.: The number of order-preserving maps between fences and crowns, Order 12 (1995), 5–44.
Haralick, R. M. and Elliott, G. L.: Increasing tree search efficiency for constraint satisfaction problems, Artif. Intell. 14 (1980), 263–313.
Heitzig, J. and Reinhold, J.: The number of unlabeled orders on fourteen elements, Order 17 (2000), 333–341.
Kondrak, G. and van Beek, P.: A theoretical evaluation of selected backtracking algorithms, Artif. Intell. 89 (1997), 365–387.
Prosser, P.: Hybrid algorithms for the constraint satisfaction problem, Comput. Intell. 9 (1993), 268–299.
Liu, W.-P. and Wan, H.: Automorphisms and isotone self-maps of ordered sets with top and bottom, Order 10 (1993), 105–110.
Rival, I. and Rutkowski, A.: Does almost every isotone self-map have a fixed point? in Bolyai Math. Soc., Extremal Problems for Finite Sets. Bolyai Soc. Math. Studies 3, Viségrad, Hungary, 1991, pp. 413–422.
Schröder, B.: Ordered Sets – An Introduction, Birkhäuser Verlag, Boston, Basel, Berlin, 2003.
Schröder, B.: CSP solver, a program to solve constraint satisfaction problems, available at http://www2.latech.edu/~schroder/software.htm, 2002.
Shoup, V.: NTL – A Library for Doing Number Theory, available at http://www.shoup.net, 2002.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was sponsored by Louisiana Board of Regents RCS grant LEQSF(1999-02)-RD-A-27.
Rights and permissions
About this article
Cite this article
Schröder, B.S.W. The Automorphism Conjecture for Small Sets and Series Parallel Sets. Order 22, 371–387 (2005). https://doi.org/10.1007/s11083-005-9024-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-005-9024-7