# Whether a total order set of size $n$ has the fewest endomorphisms among posets of size $n$

A function $f: P \to P$ is an endomorphism iff for any $x \le y$ in the poset $P$ , $f(x) \le f(y)$. So among posets of size $n$, whether the total order set $[n]$ (with the usual ordering) has the fewest endomorphisms?

No. The zig-zag poset on 4 elements has only 31 endomorphism, whereas the total order has 35 endomorphisms.

I added the number of automorphisms and endomorphisms of a poset to http://www.findstat.org, should be visible shortly.

Update:

To make things a little bit clearer, note that adding more covering relations may increase the number of endomorphisms. Consider the two posets below, then the map sending $[0,1,2,3]$ to $[0,0,0,2]$ is not a poset endomorphism of the fence, but it is a poset endomorphism of the second poset.

• This is now findstat.org/St000634, more information and references are very welcome! Oct 24 '16 at 11:10
• Surprise: the poset on 6 elements with the minimal number of endomorphisms (234) is not the fence (which has 275). Instead, it is the poset with cover relations $[3, 5], [3, 4], [1, 5], [1, 2], [0, 2], [0, 4]$. I hope I did not make a programming mistake - this is rather weird. Oct 24 '16 at 11:38
• The 234 is confirmed by my program. Oct 24 '16 at 14:03
• My back of the envelope calculation suggests that as $n$ grows large, the $n$-element fence should have $\Theta(n(\sqrt2+1)^n)$ endomorphisms, whereas for even $n$, the $n$-element “closed fence” (like the $6$-element one above) only $\Theta(\sqrt n(\sqrt 2+1)^n)$, so the latter should be better for all large enough (and even) $n$. Oct 24 '16 at 19:09
• (For odd $n$, a similar bound should hold for the closed fence with $n-1$ elements with an extra element splitting one of the edges.) Oct 24 '16 at 19:18

For posets with less than five elements, the total order is the unique poset with one unique endomorphism, but on 5 elements, there are in total 3 posets with only one endomorphism: the poset with edges $$12, 13, 24, 35, 45 \text{ and } 13, 14, 24, 25, 35$$

Won't the unique poset $P$ on $n$ elements with no relations whatsoever admit the maximal number of endomorphisms?
Namely, any $P \to P$ is an endomorphism, since any pair of elements are unrelated, and they are also mapped to a pair of unrelated elements. Or, if you do not allow two different elements with no relation to be mapped to the same element, then you get the $n!$ permutations.
• This is not right. The number of endomorphisms of $[n]$ is "$n$ multichoose $n$" or in other words $\binom{2n-1}{n}$. Oct 24 '16 at 2:21
• (Endomorphisms of $[n]$ clearly correspond to sequences $1\leq x_1 \leq x_2 \leq \cdots \leq x_n \leq n$: we just map $i$ to $x_i$.) Oct 24 '16 at 2:23