About the $n$-cube

2012-10-26T19:27:04Z

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

Answer by Douglas Zare for About the $n$-cube

2012-10-26T19:41:47Z

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

About the $n$-cube - MathOverflow

About the $n$-cube

Answer by Douglas Zare for About the $n$-cube