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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
11
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.
answered Oct 24, 2016 at 10:25
-
1$\begingroup$ This is now findstat.org/St000634, more information and references are very welcome! $\endgroup$ Oct 24, 2016 at 11:10
-
3$\begingroup$ 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. $\endgroup$ Oct 24, 2016 at 11:38
-
1$\begingroup$ The 234 is confirmed by my program. $\endgroup$ Oct 24, 2016 at 14:03
-
1$\begingroup$ 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$. $\endgroup$ Oct 24, 2016 at 19:09
-
1$\begingroup$ (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.) $\endgroup$ Oct 24, 2016 at 19:18
$\begingroup$
$\endgroup$
8
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 $$
Old unrelated answer:
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.
answered Oct 24, 2016 at 1:57
-
1$\begingroup$ This is not right. The number of endomorphisms of $[n]$ is "$n$ multichoose $n$" or in other words $\binom{2n-1}{n}$. $\endgroup$ Oct 24, 2016 at 2:21
-
1$\begingroup$ (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$.) $\endgroup$ Oct 24, 2016 at 2:23
-
2$\begingroup$ @Per : Uh, no. Every poset has at least one endomorphism which is the identity and (when having more than one element) one constant map to each element. Endomorphisms do not preserve incompatibility necessarily. Gerhard "Let's Get This Order Straight" Paseman, 2016.10.23. $\endgroup$ Oct 24, 2016 at 2:28
-
1$\begingroup$ [2] has 3 endomorphisms. You can always map all elements to a fixed element. $\endgroup$ Oct 24, 2016 at 3:34
-
2$\begingroup$ It would be great to have the number of strictly order-preserving maps in findstat, too! $\endgroup$ Oct 24, 2016 at 14:41