• Graph Isomorphism (GI)
  • Input: two undirected graphs $G$ and $H$
  • Output: $[G\cong H]$
• String Isomorphism (SI)
  • Input: two strings $x,y$: $[n]\to [m]$ and a permutation group $G\subseteq S_n$
  • Output: $[x{\cong }_{G}y]$

群作用的基本概念

• 群 $G$ 在非空集合 $X$上的左作用 $\circ :G\times X\to X$ 满足
  • $\mathrm{\forall }x\in X(e\circ x=x)$
  • $g_1\circ (g_2\circ x)=(g_1{g}_2)\circ x$
• 轨道：$O_x=Gx=g\circ x:g\in G$
  • Let $X/G=O_x|x\in G$
  • $X=⨆O_x$
• $g$-不动点(invariant set)：$X_g=\text{fix}(g)=x\in X:g\circ x=x$
• 稳定化子(stabilizers)：$G_x=\text{stab}(x)=g\in G:g\circ x=x⩽G$
  • $[G:G_x]=|O_x|$
• Burnside引理: $|X/G|=\frac{1}{|G|}\sum _{g\in G}|X_g|$

Pólya Theory of Counting

• $M_{\pi }(x_1,x_2,\cdots ,x_n)=\prod _{i=1}^k{x}_{l_i},i$th cycle has length $i$
• cycle index of $G$: $P_G(x_1,x_2,\cdots ,x_n)=\frac{1}{|G|}\sum _{\pi \in G}{M}_{\pi }(x_1,x_2,\cdots ,x_n)$
• nonequivalent $m$-colorings of $n$ objects under the action of $G$ pattern inventory
  • $F_G(y_1,y_2,\cdots ,y_m)=\sum _v{a}_v{y}_1^{n_1}{y}_2^{n_2}\cdots y_m^{n_m}$
  • $v=(n_1,n_2,\cdots ,n_m),\sum _{i=1}^m{n}_i=n$
• Pólya’s enumeration formula: $F_G(y_1,y_2,\cdots ,y_m)=P_G(\sum _{i=1}^m{y}_i,\sum _{i=1}^m{y}_i^2,\cdots ,\sum _{i=1}^m{y}_i^n)$