MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$[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 (published paper here if you have access);

share|cite|improve this question
up vote 4 down vote accepted

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$.

share|cite|improve this answer
I guess I should have said, "no nontrivial elements in the center." – Douglas Zare Oct 27 '12 at 11:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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