The endomorphism spectrum of an ordered set |
| |
Authors: | Ken Grant R J Nowakowski Ivan Rival |
| |
Institution: | (1) Department of Mathematics, University of Ottawa, K1N 6N5 Ottawa, Canada;(2) Department of Mathematics, Dalhousie University, Halifax, Canada;(3) Department of Computer Science, University of Ottawa, K1N 6N5 Ottawa, Canada |
| |
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.Partially supported by a grant from the NSERC.Partially supported by a grant from the NSERC. |
| |
Keywords: | Primary: 06A06 05C35 Secondary: 05B05 03C13 |
本文献已被 SpringerLink 等数据库收录! |
|