Crossposted on Mathematics.

In this post, an order-preserving self-map of a poset $X$ will be called an **endomorphism** of $X$, and such an endomorphism $f$ will be called **rigid** if the only automorphism of $X$ which commutes with $f$ is the identity of $X$.

The question is in the title:

Does every finite poset have a rigid endomorphism?

Let us prove

**Proposition 1.** Every poset of cardinality at most $9$ has a rigid endomorphism.

Let $X$ be a finite poset and let

$$

G=text{Aut}(X)

$$

be its group of automorphisms. Say that a set theoretical map $f:Xto X$ is **orbit preserving** is $f(A)$ is a subset of $A$ for each orbit $A$ of $G$ in $X$.

It will be convenient to prove a slightly stronger version of Proposition 1:

**Proposition 2.** Every poset of cardinality at most $9$ has an **orbit preserving** rigid endomorphism.

The poset below has no orbit preserving rigid endomorphism:

However any constant endomorphism is rigid.

The sequel is dedicated to the proof of Proposition 2.

Write

$$

(Sigma(X))

$$

for the statement “the poset $X$ has an orbit preserving rigid endomorphism”.

Note that $(Sigma(X))$ is obvious if the cardinality $|X|$ of $X$ is $0,1$ or $2$.

**Remark 3.** Let $X$ be a poset of cardinality $le9$. It suffices to prove $(Sigma(X))$ under the assumption that $(Sigma(Y))$ holds for all poset $Y$ of cardinality $<|X|$.

For any orbits $A$ and $B$ of $G$ in $X$ write

$$

nu(A,B)

$$

for the number of strict inequalities between elements of $Acup B$.

**Remark 4.** We have $nu(A,A)=0$, that is, distinct elements in the same orbit are incomparable. (Indeed, all elements of $A$ are maximal in $A$.) If $a,a’in A$ and $b,b’in B$, then the inequalities $a<b$ and $a’>b’$ are incompatible. Moreover $nu(A,B)$ is a multiple of $|A|$ and of $|B|$ which cannot exceed $|A||B|$.

Let us explain why this technical notion of orbit preservation is introduced.

**Lemma 5.** Let $A$ be an orbit of $G$ in $X$ such that $nu(A,B)in{0,|A||B|}$ for all orbit $B$. Then any orbit preserving rigid endomorphism of the poset $Y:=Xsetminus A$ extends to an orbit preserving rigid endomorphism of $X$.

*Proof.* The proof is easy but we include it just to show where the orbit preservation assumption is used. Let $f$ be our rigid endomorphism of $Y$, and let $g$ be any set theoretical orbit preserving extension of $f$ to a self-map of $X$ which induces a rigid self-map $g_A$ of $A$. It is clear that the only automorphism of $X$ which commutes with $g$ is the identity, and it only remains to show that $g$ is an endomorphism. Let $x,x’in X$ satisfy $x<x’$ (the case $x>x’$ is similar and omitted). We must prove $g(x)le g(x’)$. Note that $x$ or $x’$ is in $Y$ (distinct elements in the same orbit are incomparable, see Remark 4). Say $x$ is in $Y$. If $x’$ is also in $Y$, the inequality $g(x)le g(x’)$ is clear, so that we can assume $x’in A$. Letting $B$ be the orbit of $x$, we have $Bne A$. Since $f$ is orbit preserving, $g(x)=f(x)$ is in $B$ (recall that $x’$ and $g(x’)=f_A(x’)$ are in $A$), and the inequality $x<x’$ implies by assumption $g(x)<g(x’)$. $square$

**Lemma 6.** Let $A$ be an orbit of $G$ in $X$ whose cardinality is coprime to the cardinality of any other orbit, and let $f$ be an orbit preserving rigid endomorphism of the poset $Y:=Xsetminus A$. Then $f$ extends to an orbit preserving rigid endomorphism of $X$.

*Proof.* This follows from the previous lemma and Remark 4. $square$

We want to upgrade Remark 3 to

**Remark 7.** Let $X$ be a poset of cardinality $le9$. It suffices to prove $(Sigma(X))$ under the assumption that $X$ is **connected** and that $(Sigma(Y))$ holds for all poset $Y$ of cardinality $<|X|$.

This will follow from the next two lemmas.

For $ninmathbb N$ set $(n):={1,2,ldots,n}$, and regard the set $(n)$ as a discrete poset. A poset of the form $Xtimes(n)$ with $X$ connected will be called **isotypic**.

**Lemma 8.** Let $X$ be a connected poset. If $X$ has an orbit preserving rigid endomorphism, then so does $Y:=Xtimes(n)$.

*Proof.* Let $f$ be an orbit preserving rigid endomorphism of $X$, and define $g:Yto Y$ by

$$

g(x,i)=begin{cases}(x,i+1),&i<n\ (f(x),n),&i=n.end{cases}

$$

We leave it to the reader to check that $g$ is an orbit preserving rigid endomorphism of $Y$. $square$

**Lemma 9.** Let $X_1,ldots,X_n$ be the isotypic components of the finite poset $X$, for $1le ile n$ let $f_i$ be an orbit preserving rigid endomorphism of $X_i$. Then the coproduct of the $f_i$ is an orbit preserving rigid endomorphism of $X$.

This is clear. $square$

Let

$$

M(X)

$$

be the undirected graph obtained from the Hasse diagram of $X$ by forgetting the direction of the edges. By Remark 4 this is a **multipartite graph** – Wikipedia entry – the parts being the $G$-orbits. Note that $M(X)$ is connected if and only if $X$ is. Also note that the part preserving endomorphisms of $M(X)$ coincide with the orbit preserving endomorphisms of $X$, and that such an endomorphism is invertible if and only if it is in $G$. Say that a part preserving endomorphism $f$ of $M(X)$ is **rigid** if the only element of $G$ commuting with $f$ is the neutral element. Hence the part preserving rigid endomorphisms of $M(X)$ coincide with the orbit preserving rigid endomorphisms of $X$.

**Lemma 10.** Assume that $X$ is connected, that $G$ has two distinct orbits $A$ and $B$ in $X$, that we have $2=|A|le|B|$, and that there are no other orbits. Then $X$ has an orbit preserving rigid endomorphism.

*Proof.* If $|B|$ is odd this follows from Lemma 6, so that we can assume that $|B|$ is even. We have $nu(A,B)in{|B|,2|B|}$. If $nu(A,B)=|B|$, the poset $X$ is not connected. If $nu(A,B)=2|B|$, the statement results from Lemma 5. $square$

Let us attach to a multipartite graph $M$ a graph

$$

overline M

$$

as follows: The vertices of $overline M$ are the parts of $M$ and two parts $A$ and $B$ form an edge of $overline M$ if and only if there are $ain A,bin B$ such that $a$ and $b$ form an edge of $M$.

**Lemma 11.** Let $M$ be a finite multipartite graph such that $overline M$ is a tree. Assume that for all edge ${A,B}$ of $overline M$ and all $ain A$ there is an edge of $M$ of the form ${a,b}$ with $bin B$. Then the natural morphism $Mtooverline M$ has a section, that is, there is a family

$$

xinprod_{Ainoverline M}A

$$

such that ${x_A,x_B}$ is an edge of $M$ if and only if ${A,B}$ is an edge of $overline M$.

*Proof.* Let us argue by induction on the number $n$ of parts. We can assume that $nge2$ and that the statement holds for $n-1$. Let $A,Binoverline M$ be such that $B$ is the only neighbour of $A$. In particular $overline Msetminus{A}$ is a tree with $n-1$ vertices, and there is a family

$$

xinprod_{Cinoverline Msetminus{A}}C

$$

such that ${x_C,x_D}$ is an edge of $M$ if and only if ${C,D}$ is an edge of $overline Msetminus{A}$. By assumption there is an $x_Ain A$ such that ${x_A,x_B}$ is an edge of $M$. $square$

**Lemma 12.** In the above setting, assume that all the parts of $M$ have exactly two elements, and that $overline M$ is a tree. Then $M$ has a part preserving rigid endomorphism.

*Proof.* There is a family $(x_A)_{Ainoverline M}$ as in the statement of Lemma 11, for each $A$ there is a $y_A$ such that $A={x_A,y_A}$, and we can define $f:Mto M$ by $x_Amapsto y_Amapsto y_A$. $square$

**Lemma 13.** Assume that $X$ has exactly two orbits $A$ and $B$, that these orbits have the same cardinality $nge2$, and that each point of $M(X)$ is linked to $n-1$ points. Let $f_A$ be a rigid self-map of $A$. Then $f_A$ extends to an orbit preserving rigid endomorphism of $X$.

*Proof.* Set

$$

A={a_1,ldots,a_n},quad B={b_1,ldots,b_n}.

$$

We can assume that $a_i<b_j$ if and only if $ine j$. Clearly $G$ is the symmetric group $S_n$, and the lemma will result from the following statement:

Given any self-map $u$ of $(n):={1,ldots,n}$ there is a self-map $v$ of $(n)$ such that $ine j$ implies $v(i)ne u(j)$.

Indeed, $v(1)$ must be different from $u(2),u(3),ldots,u(n)$, so that there are, for $v(1)$, at most $n-1$ prohibited values out of $n$ possible values, and similarly for $v(2),v(3),ldots,v(n)$. $square$

**Lemma 14.** Assume that $G$ has at most five orbits in $X$, and that each such orbit has cardinality two. Then $X$ has a rigid endomorphism.

*Proof.* Let $E$ be the set of all edges ${A,B}$ of $overline{M(X)}$ such that $nu(A,B)=4$. Let $overlineGamma$ be the (undirected) graph obtained from $overline{M(X)}$ by removing the edges in $E$ (and keeping all the vertices). Similarly let $Gamma$ be the multipartite graph obtained from $M(X)$ by removing the edges of the form ${a,b}$ with $ain A$, $bin B$, ${A,B}in E$ (and keeping all the vertices).

If $overlineGamma$ is a disjoint union of trees, then, by Lemma 13, $Gamma$ has a part preserving rigid endomorphism, which is easily seen to be an orbit preserving rigid endomorphism of $X$.

Hence we can assume that $overlineGamma$ contains at least one cycle. This implies that the cardinality $|X|$ of $X$ is equal to $8$ or $10$. We can assume that $X$ is connected.

If $|E|=0$, then any constant endomorphism is rigid, so that we can assume now $|E|ge1$. Since a cycle has at least four vertices, this entails $|X|=10$.

Let us consider the case $|E|=1$. Set $E={{A,B}}$ with $deg Aledeg B$, where $deg$ denotes the degree in $overlineGamma$. Let $ain A$, $bin B$ and define $f:Xto X$ by

$$

f(x)=begin{cases}a&text{if }xin A\ b&text{if }xnotin A.end{cases}

$$

By looking carefully at Appendix B page 286 of the book

**Finite ordered sets: concepts, results and uses** by Caspard, Nathalie and Leclerc, Bruno and Monjardet, Bernard, 2012, Cambridge University Press, pdf link,

we see that $f$ is a rigid endomorphism of $X$.

The same appendix shows that the case $|E|ge2$ is incompatible with the assumption that $overlineGamma$ contains at least one cycle. This completes the proof. $square$

As an illustration, here are two cases with $E={{A,B}}$, represented by the Hasse diagram of $overline X$:

Going back to the general setting where $X$ is a finite poset and $G$ is its automorphism group, if the $p_i$ with $p_1lecdotsle p_k$ are the cardinalities of the orbits of $G$ in $X$, then we say that

$$

p_1+cdots+p_k

$$

is the **partition** of $|X|$ attached to the poset $X$.

In view of the lemmas, it suffices to consider the following partitions:

$$

2+2+4,quad4+4,quad3+3+3.

$$

$bullet$ **Partition 2+2+4**

The graph $overline{M(X)}$ is of the form $A-B-C$.

Case 1: $|A|=|B|=2,|C|=4$. By Lemma 10 the sub-poset $Bcup C$ of $X$ has an orbit preserving rigid endomorphism $f$, and it is clear that $f$ extends to an orbit preserving rigid endomorphism of $X$.

Case 2: $|B|=4$. We have $nu(A,B),nu(B,C)in{4,8}$. If $nu(B,C)=8$, arguing as in Case 1 above, we can extend an orbit preserving rigid endomorphism of $Acup B$ to an orbit preserving rigid endomorphism of $X$. Hence it suffices to consider the case $nu(A,B)=nu(B,C)=4$. Write

$$

A={a_1,a_2},quad B={b_1,b_2,b_3,b_4},quad C={c_1,c_2}.

$$

We can assume that $M(X)$ contains the subgraphs $b_1-a_1-b_2$ and $b_3-a_2-b_4$. If we had $b_1-c_1-b_2$ and $b_3-c_2-b_4$, the poset $X$ would not be connected. Thus we have (perhaps after swapping $c_1$ and $c_2$) $b_1-c_1-b_3$ and $b_2-c_2-b_4$. Then it is not hard to check that

$$

a_imapsto a_2,quad b_imapsto b_4,quad c_imapsto c_2

$$

is an orbit preserving rigid endomorphism of $X$.

$bullet$ **Partition 4+4**

Assume that $X$ is connected (Remark 7) and say that each point of $M(X)$ is linked to $d$ points. Then $d$ is equal to $2,3$ or $4$. The cases $d=3$ and $d=4$ follow respectively from Lemmas 13 and 5. Consider the case $d=2$. Setting

$$

A={a_1,ldots,a_4},quad B={b_1,ldots,b_4},

$$

we can assume that the only strict inequalities are $a_i<b_j$ if $j-i$ is congruent to $0$ or $1$ modulo $4$. Then

$$

a_1mapsto a_2mapsto a_3leftrightarrow a_4,quad b_2mapsto b_3mapsto b_4mapsto b_4,quad b_1mapsto b_3

$$

is an orbit preserving rigid endomorphism of $X$.

$bullet$ **Partition 3+3+3**

The graph $overline{M(X)}$ is of the form $A-B-C$. Set $B={b_1,b_2,b_3}$. Using Lemmas 5 and 13 we see that

$$

b_1mapsto b_2mapsto b_3mapsto b_3

$$

extends to an orbit preserving rigid endomorphism of $X$.