About the $n$-cube - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:40:03Z http://mathoverflow.net/feeds/question/110781 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110781/about-the-n-cube About the $n$-cube Philippe Gaucher 2012-10-26T19:27:04Z 2012-10-26T19:55:28Z <p>$[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))$.</p> <p>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.</p> <p>PS : the definitions are in this paper <a href="http://www.pps.univ-paris-diderot.fr/~gaucher/symcub.pdf" rel="nofollow">http://www.pps.univ-paris-diderot.fr/~gaucher/symcub.pdf</a> (published paper here <a href="http://dx.doi.org/10.1016/j.tcs.2009.11.013" rel="nofollow">http://dx.doi.org/10.1016/j.tcs.2009.11.013</a> if you have access);</p> http://mathoverflow.net/questions/110781/about-the-n-cube/110782#110782 Answer by Douglas Zare for About the $n$-cube Douglas Zare 2012-10-26T19:41:47Z 2012-10-26T19:55:28Z <p>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$. </p>