ISSN:
1572-9273
Keywords:
Primary: 06A06, 05C35
;
Secondary: 05B05, 03C13
;
Ordered set
;
order-preserving map
;
endomorphism
;
retract
;
reflexive graph
;
rigid
;
projective plane
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01108589
