10
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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.

Zig Zag other

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is now findstat.org/St000634, more information and references are very welcome! $\endgroup$ – Christian Stump Oct 24 '16 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$ – Martin Rubey Oct 24 '16 at 11:38
  • 1
    $\begingroup$ The 234 is confirmed by my program. $\endgroup$ – Wilberd van der Kallen Oct 24 '16 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$ – Emil Jeřábek Oct 24 '16 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$ – Emil Jeřábek Oct 24 '16 at 19:18
-2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Sam Hopkins Oct 24 '16 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$ – Sam Hopkins Oct 24 '16 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$ – Gerhard Paseman Oct 24 '16 at 2:28
  • 1
    $\begingroup$ [2] has 3 endomorphisms. You can always map all elements to a fixed element. $\endgroup$ – Rafael Prince Oct 24 '16 at 3:34
  • 2
    $\begingroup$ It would be great to have the number of strictly order-preserving maps in findstat, too! $\endgroup$ – Martin Rubey Oct 24 '16 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.