Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

$[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);

share|improve this question

1 Answer 1

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

 
discard

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.