Simple Graphs and Automorphisms of the Hypercube

Question

Consider the set $\mathcal{G}_v$ of all finite simple graphs on a given set of $v$ vertices. Let $m={v\choose 2}$ for sake of notation. Given an identification of $\{1,\dots,m\}$ with the set of 2-element subsets of $\{1,\dots,v\}$, there is a natural bijection $\Phi$ from $\mathcal{G}_v$ onto the $m$-hypercube, $Q_m=\{0,1\}^m$, where each component of a vector $q\in Q_m$ corresponds to the presence of an edge in the corresponding graph ($0$ and $1$ corresponding to the lack of or presence of respectively). We define $Q^{k}_m=\{q\in Q_m:\displaystyle\sum_{i=1}^m q_i=k\}$. The automorphism group of $Q_m$ is isomorphic to $S_m\ltimes S_2^m$ (the hyperoctohedral group), where $S_n$ is the symmetric group on $n$ letters.

The equivalence relation "being isomorphic as graphs" on $\mathcal{G}_v$ induces an equivalence relation $\simeq$ on $Q_m$ through the above bijection $\Phi$. I am interested in automorphisms $\phi$ of $Q_m$ which correspond to graph isomorphisms, that is, such that $x\simeq \phi(x)$ for every vertex $x\in Q_m$.

It is clear that such automorphisms must take each subset $Q^k_m$ to itself as it must preserve the number of edges (or rather the norm given the Hamming metric). However, it is unclear to me if there is much more structure to be imposed on these automorphisms (maybe by introducing restrictions on the metric?). Are there perhaps some references that may lead to some insight? I apologize for the rather vague ending - please advise if more description is needed. Thank you.

Answer 1

So let $H$ be the group of automorphisms $f$ of $Q_m$ such that $f(x)\simeq x$ as graph for every $x\in Q_m$ ($x$ being viewed as a graph using the bijection $\mathcal{G}_v\to Q_m$). If $v\le 2$, then $H$ is reduced to the trivial group.

Assume $v\ge 3$. Then $H$ contains the group $K\simeq\mathfrak{S}_m$ induced by permutations of vertices. Let us check that $H=K$ (as suggested by Ben Barber as a comment).

Let $S\subset Q_m$ be the set of vertices corresponding to a complete graph on $v-1$ vertices and a single isolated vertex. Since $v\ge 3$, $S$ has exactly $v$ elements (one for each choice of isolated vertex). Since $S$ is a single equivalence class of $\simeq$, it is stabilized by $H$. The action of $H$ on $S$ restricts to an isomorphism $K\simeq\mathfrak{S}(S)$. Let $W$ be the kernel of $H\to\mathfrak{S}(S)$, namely the pointwise stabilizer of $S$; thus $H=K\ltimes W$. To show $H=K$ amounts to showing that $W=\{1\}$. Since $H$ stabilizes $Q_m^0=\{0\}$, it fixes 0 (which corresponds to the discrete graph with no edge). Hence, for each $x\in S$, $W$ stabilizes the total segment between $0$ and $x$ (in a metric space, the total segment $[x,y]$ means the set of $z$ such that $xz+zy=xy$). In the hypercube, the total segment between $0$ and $x$ is the sub-cube consisting of the power set of $x$ (if $x$ is viewed as a graph, it consists of those subgraphs of $x$). This implies that for each vertex $z$ and each $f\in W$, the set of graphs $M_z$ for which $z$ is isolated is stable under $f$. Now take two distinct vertices $z_1,z_2$: then $\bigcap_{z\notin\{z_1,z_2\}}M_z$ is reduced to the pair consisting of 0 and the graph with $\{z_1,z_2\}$ as edge. Hence $W$ fixes every graph consisting of a single edge. Since an automorphism of the hypercube fixing a vertex (here, 0) along with all its neighbors has to be the identity, this shows $W=\{1\}$.