We've seen that when S is a subsemigroup of Tn, whose members have exactly one fixed point each, then we can group them by their fixed points: let Si be the subsemigroup of S consisting of those guys having i as fixed point.
We've also seen that Si is indeed a semigroup and for each i, there exists a partial ordering <i of [n] such that when pf=q for some f in Si, then p<iq. Except when p=i. This <i has i as maximal element.
Without loss of generality we can assume that
- Sn is (one of) the largest among those Si guys and
- <n is consistent with the standard <,
We show that if Sn is "large enough" then the other Si guys are "small". Namely,
Lemma. Suppose for each i<j, i'<j' with i'<>j' there exists some f in Sn with if=j, i'f=j'.
Then for each i and f in Si we have
- if j<i, then j < jf;
- if i<=j, then i=jf.
The other option is that Sn does not satisfy the conditions for the lemma. It's routine to check that in this case |Sn| <= (n-1)! - (n-3)! (this bound is sharp). Since Sn was chosen to be the largest, we have that |S| <= n((n-1)! - (n-3)!).
Now for the proof of the lemma...
- For i = n, the claims get satisfied: guys below n get elevated and n is mapped to n, okay. So assume i < n. And let f be a member of Si.
- Then, nf < n (since n is not a fixed point of f).
- Assume pf < p for some p and that pf <> nf. Then by the assumption, nfg = n and pfg = p for some g in Sn. Thus the composition fg has two fixed points p and n, a contradiction. Hence if pf < p, then pf = nf. In particular, if p < nf, then p <= pf. (That is, all backward arrows share their target.)
- Assume nf < i. Note that if = i. Then by assumption nfg = i and ig=n for some g in Sn, and fgfg has two fixed points n and i, a contradiction. Thus, i <= nf.
- Assume i < nf. Also nfffff..f is eventually i < nf (since f is nonpermutational with target i), hence there exists some smallest k such that nf^{k+1} < nf. However, this involves a second backward jump with target different from nf, a contradiction. Thus i = nf.
- Observe that 3, part b and 5 together prove Statement 1.
- Assume i < j < jf. Then for some g, jfg = n and ig = j and fgfg has two fixed points n and j, a contradiction. Hence if i < j, then jf < j, thus jf = i, proving Statement 2.
...I'd guess the bound is not strict. I would be surprised if some S with |S| >= 3(n-1)! could be actually constructed...