数理論理学・集合論の問題

$(A,E^{\mathcal{M}})$ は立方体の頂点と辺からなるグラフである。以下、$o=(0,0,0)$, $\bar{o}=(1,1,1)$ と書く。

$o$ を固定する自己同型. $\sigma (o)=o$ とする。$\sigma$ は $E$ を保つので、$o$ の隣接点の集合 $N=\{(1,0,0),(0,1,0),(0,0,1)\}$ を自分自身に移す。

$\sigma$ は $N$ 上の置換で一意に決まることを示す。
- 成分が 2 つ $1$ の点（たとえば $(1,1,0)$）は、$N$ の 2 点 $(1,0,0),(0,1,0)$ の両方に隣接する点のうち $o$ でないただ 1 つの点である。$\sigma$ は隣接関係を保つので、その像は $\sigma ((1,0,0))$ と $\sigma ((0,1,0))$ の両方に隣接する $o$ 以外のただ 1 つの点として決まる。
- 残る $\bar{o}$ は、ほかの 7 点の像が決まれば残った 1 点として決まる。

よって $o$ を固定する自己同型は高々 $3!=6$ 個。逆に、座標の置換 $(x_1,x_2,x_3)\mapsto (x_{\pi (1)},x_{\pi (2)},x_{\pi (3)})$（$\pi$ は $\{1,2,3\}$ の置換）は「異なる成分の個数」を保つので $E$ を保ち、$o,\bar{o}$ をそれぞれ固定するので $P$ も保つ。これで 6 個がすべて実現され、$o$ を固定する自己同型はちょうど $6$ 個である。

$o$ の行き先. 自己同型は $P^{\mathcal{M}}$ を $P^{\mathcal{M}}$ に移すので、$\sigma (o)\in \{o,\bar{o}\}$。補数写像 $\tau (x)=(1-x_1,1-x_2,1-x_3)$ は異なる成分の個数を保つので $E$ を保ち、$o$ と $\bar{o}$ を入れかえるので $P$ も保つ。よって $\tau$ は自己同型で $\tau (o)=\bar{o}$。

$\sigma (o)=\bar{o}$ となる自己同型 $\sigma$ に対し ${\tau }^{-1}\circ \sigma$ は $o$ を固定する自己同型だから、そのような $\sigma$ は $\tau \circ \rho$（$\rho$ は $o$ を固定する自己同型）の形にちょうど 6 通りに書ける。

結論. 自己同型の個数は $6+6=12$ である。

（参考：$P$ がないと立方体グラフの自己同型群の位数は $8\cdot 6=48$ であり、$P$ の条件で $o$ の行き先が 8 通りから 2 通りに制限される。）

$(A,E^{\mathcal{M}})$ は 3 次元立方体グラフ $Q_3$ であり、その自己同型群は位数 $2^3\cdot 3!=48$（成分の置換 $S_3$ と、各成分の 0/1 反転 $(\mathbb{Z}/2{)}^3$ の半直積）である。自己同型 $\sigma$ が $P$ を保つ条件は $\sigma (\{000,111\})=\{000,111\}$。

$Q_3$ の自己同型は距離を保つので、$000$ と $111$（距離 3 の対蹠点）の対は、対蹠点の対（$\{u,\bar{u}\}$ の形、全部で 4 組）へ写る。群は 4 組に推移的に作用する（反転で $000$ を任意の $u$ へ送れる）ので、軌道・安定部分群の定理により $\{000,111\}$ の安定部分群の位数は $48/4=12$。

直接数えても確かめられる。$\sigma (000)\in \{000,111\}$ の 2 通り。$\sigma (000)=000$ のとき、$\sigma$ は成分の置換のみで $3!=6$ 通り（このとき $111\mapsto 111$ となる）。$\sigma (000)=111$ のときは、全成分反転を合成して同様に 6 通り。合計 $2\cdot 6=12$。