Suppose $S$ is a finite set and we are given a family of functions $(f_i:S\to S)_{i\in I}$. When can we find a total order $<$ on $S$ such that all the functions $f_i$ are nondecreasing?
I am interested in the case where all the functions are idempotent and form a submonoid of the set of all functions on $S$. Furthermore, in my examples $S$ is already equiped with a partial order on for which all the functions are nondecreasing, and I would like extend the partial order to a total order keeping the $f_i$ nondecreasing.
There are a few necessary yet not sufficient conditions: in the general case one would require there be no cycles in arbitrary products of the $f_i$ (this being automatically the case in my scenario), and my case we must have for any $x\neq y\in S$ and $m,m'\in M$ ($M$ stands for the submonoid of functions we are working with) such that $m(x)=m'(y)\neq m(y)$ then $m(y)\neq m'(x)$. This is intuitively clear (and easy to prove) when one draws a picture: if we had equality then $m$ and $m'$ could not both be nondecreasing.
This last condition is not sufficient however (there are small counterexamples).
Let $X$ be a finite set. The set of all functions $X\to X$ will be called $F(X)$, and the subset of all idempotent functions will be called $E(X)$.
A function $f\in F(X)$ will be called nondecreasing if there exists a total order $<$ on $X$ such that $f$ is $<$-nondecreasing. We make a similar definition for nonincreasing functions.
$f$ is a fixed function from now on. When is $f$ nondecreasing? Obviously, the only permutation of $X$ that is nondecreasing is $\mathrm{id}_X$, and the only nonincreasing permutations are those that are conjugate to the permutation whose graph is the antidiagonal. We can represent $f$ as follows $$f=[X_1:x_1|\cdots|X_r:x_r]$$ Where $\mathrm{Ran}(f)=\lbrace x_1,\dots,x_r\rbrace$ and for all $i,~X_i=f^{-1}(x_i)$.
Let us define a new function $f'$ on $\lbrace 1,\dots,r\rbrace$ by setting $\forall i\in\lbrace 1,\dots,r\rbrace,~x_i\in X_{f'(i)}$. Obviously, $f$ is idempotent iff $f'=\mathrm{id}$.
Lemma. $f$ is nondecreasing (resp. nonincreasing) iff $f'$ is nondecreasing (resp. nonincreasing)
The proof is straightforward. Let us start with $(\Rightarrow)$: given a total order $<$ on $X$ such that $f$ is nondecreasing, the $X_i$ are intervals and therefore themselves totally ordered. This order is easily seen to make $f'$ non decreasing. Now for $(\Leftarrow)$: suppose $f'$ is non decreasing. There is a total order on the $X_i,i=1,\dots,r$ say $X_1<X_2<\cdots<X_r$ with $i<j$ implying $x_i\in X_a,~x_j\in X_b$ with $a\leq b$. We define a total order on $S$ by declaring the $X_i$ to be intervals ordered in agreement with $<$. It remains to define a total order on every $X_i$. We start with $X_r$. The only requirement is that if $\lbrace i_1<\cdots <i_p\rbrace$ are the indices with $x_i\in X_r$ then we must have $x_{i_1}<\cdots<x_{i_p}$ in $X_r$. This is no problem since they are by definition distinct. How we order the other points inside $X_r$ does not matter. We proceed similarly to produce a total order on $X_{r-1}$ etc.
Corollary $f$ is nondecreasing iff for large enough $p,~f^{(p)}=\mathrm{id}_{\dots}$ while $f$ is nonincreasing iff for large enough $p,~f^{(p)}$ is conjugate to the antidiagonal map of some finite set.
I don't know wether this map (which is obvioulsy defined on conjugacy classes) $$F(X)/\mathrm{Aut}(X)\to \coprod_{1\leq p\leq n}\mathrm{ConjCl}(S_p), f\mapsto f^{(n)}$$ has a name or has been studied (I guess it must exist somewhere since it is so easily defined).