Abstract
Theendomorphism spectrum of an ordered setP, spec(P)={|f(P)|:f ∈ End(P)} andspectrum number, sp(P)=max(spec(P)\{|P|}) are introduced. It is shown that |P|>(1/2)n(n − 1)n − 1 implies spec(P) = {1, 2, ...,n} and that if a projective plane of ordern exists, then there is an ordered setP of size 2n 2+2n+2 with spec(P)={1, 2, ..., 2n+2, 2n+4}. Lettingh(n)=max{|P|: sp(P)⩽n}, it follows thatc 1 n 2⩽h(n)⩽c 2 n n+1 for somec 1 andc 2. The lower bound disproves the conjecture thath(n)⩽2n. It is shown that if |P| − 1 ∈ spec(P) thenP has a retract of size |P| − 1 but that for all κ there is a bipartite ordered set with spec(P) = {|P| − 2, |P| − 4, ...} which has no proper retract of size⩾|P| − κ. The case of reflexive graphs is also treated.
Similar content being viewed by others
References
Duffus, D., Rödl, V., Sands, B., and Woodrow, R. (1992) Enumeration of order preserving maps,Order 9, 15–29.
Duffus, D., Rival, I., and Simonovits, M. (1980) Spanning retracts of a partially ordered set,Discrete Math. 32, 1–7.
Hedrlin, Z. and Pultr, A. (1966) On rigid undirected graphs,Canad. J. Math. 18, 1237–1242.
Hell, P. and Nešetřil, J. (1978) Homomorphisms of graphs and of their orientations,Monatsh. für Math. 85, 39–48.
Hell, P. and Nešetřil, J. (1991) Images of rigid digraphs,Europ. J. Combinatorics 12, 33–42.
Hughes, D. R. (1960) On homomorphisms of projective planes,Proc. Symp. Appl. Math. 10, 45–52.
Hughes, D. R. and Piper, F. C. (1973)Projective Planes, Springer-Verlag, New York.
Jawhari, E., Misane, D., and Pouzet, M. (1986) Retracts: Graphs and ordered sets from the metric point of view,Combinatorics and Ordered Sets, Contemporary Mathematics57, 175–226.
Lorimer, J. W. and Buchholz, M. (1992) Homomorphisms of affine and projective planes,Math. Magazine 55, 195–204.
Author information
Authors and Affiliations
Additional information
Communicated by P. Hell
Partially supported by a grant from the NSERC.
Partially supported by a grant from the NSERC.
Rights and permissions
About this article
Cite this article
Grant, K., Nowakowski, R.J. & Rival, I. The endomorphism spectrum of an ordered set. Order 12, 45–55 (1995). https://doi.org/10.1007/BF01108589
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01108589