$[n]$ is the set $\{0,1\}^n$ equipped with the product order $(\epsilon_1,\dots,\epsilon_n) \leq (\eta_1,\dots,\eta_n)$ if and only if $\forall i=1,\dots,n$, $\epsilon_i \leq \eta_i$. Let $$d((\epsilon_1,\dots,\epsilon_n),(\eta_1,\dots,\eta_n)) = \sum_{i=1}^{i=n}|\epsilon_i-\eta_i|.$$ A set map $f$ from $[m]$ to $[n]$ is adjacency-preserving if it is strictly increasing for the product order and if $d((\epsilon_1,\dots,\epsilon_m),(\eta_1,\dots,\eta_m)) = 1$ implies $d(f(\epsilon_1,\dots,\epsilon_m),f(\eta_1,\dots,\eta_m)) = 1$. Example : the adjacency-preserving maps from $[2]$ to itself are $(x_1,x_2)\mapsto (x_1,x_2)$, $(x_1,x_2)\mapsto (x_2,x_1)$, $(x_1,x_2)\mapsto (\min(x_1,x_2),\max(x_1,x_2))$ and $(x_1,x_2) \mapsto (\max(x_1,x_2),\min(x_1,x_2))$.

Let $n\geq 3$. Let $f:[n]\to [n]$ be an adjacency-preserving map which commutes with all automorphisms of $[n]$ (the set of automorphisms of $[n]$ is in bijection with the permutation of the set $\{1,\dots,n\}$ by permuting the coordinates). Is $f$ necessarily the identity of $[n]$ ? For $n=2$, $(x_1,x_2)\mapsto (x_2,x_1)$ is a counter-example.

PS : the definitions are in this paper http://www.pps.univ-paris-diderot.fr/~gaucher/symcub.pdf (published paper here http://dx.doi.org/10.1016/j.tcs.2009.11.013 if you have access);


Identify elements of $[n]$ with subests of an $n$-element set. $f$ has to be level preserving because a maximal chain must be sent to a chain. If $f$ commutes with permutations, then the image is symmetric, so the image of $f$ contains all singletons. $f$ must be the identity on sets of size $1$ since $S_n$ has no center for $n\gt 2$. You can determine each set $S$ by the singletons in a chain from the empty set to $S$, and $f(S)$ contains the same singletons, so $f$ fixes each set for $n\gt 3$.

  • $\begingroup$ I guess I should have said, "no nontrivial elements in the center." $\endgroup$ – Douglas Zare Oct 27 '12 at 11:40

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.