组合数学

4 - Symmetry

2019-10-09 14:00 CST
2019-10-19 16:40 CST
CC BY-NC 4.0

Permutation Groups

Group $(G, \cdot)$ with binary operator $\cdot: G \times G \rightarrow G$

  • closure: $\pi, \sigma \in G \Rightarrow \pi \cdot \sigma \in G$
  • associativity: $\pi \cdot (\sigma \cdot \tau) = (\pi \cdot \sigma) \cdot \tau$
  • identity: $\exists e, e \cdot \pi = \pi$
  • inverse: $\pi \cdot \sigma = e, \pi = \sigma^{-1}$

Commutative (abelian) group: $\pi \cdot \sigma = \sigma \cdot \pi$

  • Symmetric group $S_n$: all permutations $$\pi: [n] \underset{onto}{\overset{1-1}{\longrightarrow}} [n]$$
  • Cyclic group $C_n$: rotations $$\pi = (012\cdots n-1), C_n = \langle \pi \rangle$$
  • Dihedral group $D_n$: rotations & reflections: generated by $(012\cdots n-1)$ and $\rho$ (reflection)

Group Action

Configuration $x: [n] \rightarrow [m]$, $X = [m]^{[n]}$

Permutation: $\pi: [n] \underset{onto}{\overset{1-1}{\longrightarrow}} [n]$

Group action: $\circ: G \times X \rightarrow X$

  • associativity: $(\pi \cdot \sigma) \circ x = \pi \circ (\sigma \circ x)$
  • identity: $e \circ x = x$

Graph Isomorphism (GI)

  • Input: two undirected graphs $G$ and $H$
  • Output: $G \cong H ?$
  • GI is in NP (Babai’s algorithm).

String Isomorphism (SI)

  • Input: two strings $x, y: [n] \rightarrow [m]$, and a permutation group $G \subseteq S_n$
  • Output: $x \cong_G y ?$ (i.e., $\exists \sigma \in G, \sigma \circ x = y$)

Johnson group: $\mathbb{S}_V^{(2)} \subset S_{{V \choose 2}}$ on vertex pairs

Two graphs $X \cong Y$ iff their string versions $x \cong_{\mathbb{S}_V^{(2)}} y$

Orbits

Group action $\circ$

Define orbit of $x$: $Gx = \left\lbrace \pi \circ x | \pi \in G \right\rbrace$, an equivalent class of configuration $x$

$X/G = \left\lbrace Gx | x \in X \right \rbrace$

Our goal: count $\vert X/G \vert$

Example: $X = [2]^{[6]}$: $\vert X/G \vert$ is the number of ways to put 2 colors onto a ring of 6 elements.

Let $\vec v = (n_1, n_2, \dots, n_m), \sum n_i = n$, then $a_{\vec v}$ is # of configurations (up to symmetry) with number of color $i$ being $n_i$.

Pattern inventory: (multi-variate) generating function:

$$F_G(y_1, y_2, \dots, y_m) = \sum_{\vec v} a_{vec v} y_1^{\vec v_{n_1}} y_2^{\vec v_{n_2}} \cdots y_m^{\vec v_{n_m}}$$

Example: $n=2, m=6, F_{D_6}(y_1, y_2) = y_1^6 + y_1^5 y_2 + 3y_1^4 y_2^2 + 3y_1^3 y_2^3 + 3y_1^2 y_2^4 + 3y_1 y_2^5 + y_2^6$

Burnside’s Lemma

Define invariant set of $\pi$: $X_\pi = \left\lbrace x \in X | \pi \circ x = x \right\rbrace$.

Burnside’s Lemma:

$$\vert X/G \vert = \dfrac{1}{\vert G \vert} \sum\limits_{x \in G} \vert X_\pi \vert.$$

Define stabilizer of $x$: $G_x = \left\lbrace \pi \in G | \pi \circ x = x \right\rbrace$.

Lemma: $\forall x \in X, \vert G_x \vert \vert Gx \vert = \vert G \vert.$

$$A(\pi, x) = \begin{cases}1, & \pi \circ x = x \\ 0, & \text{o.w.} \end{cases}$$

  • $\vert X_\pi \vert = \sum\limits_{x \in X} A(\pi, x)$
  • $\vert G_x \vert = \sum\limits_{\pi \in G} A(\pi, x)$

Double counting: $$\sum_{\pi \in G} \vert X_\pi \vert = \sum_{\pi \in G}\sum_{x \in X} A(\pi, x) = \sum_{x \in X} \vert G_x \vert = \vert G \vert \sum_{x \in X} \dfrac{1}{\vert G_x \vert} = \overset{??}{\cdots} = \vert G \vert \vert X/G \vert$$

Cycle Decomposition

E.g. $\dbinom{0\ 1\ 2\ 3\ 4}{2\ 4\ 0\ 1\ 3} = (02)(143)$, decompose a permutation into 2 cycles.

Invarian $\pi \circ x = x$, forall $i$, $x(\pi(i)) = x(i)$, iff every cycle of $\pi$ has the same color.

If $X = [m]^{[n]}$ ($m$ colors, $n$ elements on a ring), $\pi$ has $k$ cycles, then $\vert X_\pi \vert = m^k$

Burnside’s Lemma (cont’d): $$\vert X/G \vert = \dfrac{1}{\vert G \vert} \sum\limits_{x \in G} \vert X_\pi \vert = \dfrac{1}{\vert G \vert} \sum\limits_{x \in G} m^{\text{\# of cycle in } \pi}.$$

Cycle Index

Suppose permutation $\pi$ has $k$ cycles of length $l_1, l_2, \dots, l_k$,

Define monomial: $M_n(x_1, x_2, \dots, x_n) = \prod\limits_{i=1}^k x_{l_i}$

Cycle index: $P_G(x_1, x_2, \dots, x_m) = \dfrac{1}{\vert G \vert} \sum\limits_{\pi \in G} M_{\pi}(x_1, x_2, \dots, x_n)$

Burnside’s Lemma: $$\vert X/G \vert = P_G(m, m, \dots, m) = \dfrac{1}{\vert G \vert} \sum\limits_{\pi \in G} M_{\pi}(m, m, \dots, m)$$

Polya’s Enumeration Formula: $$F_G(y_1, y_2, \dots, y_m) = P_G \left( \sum_{i=1}^m y_i, \sum_{i=1}^m y_i^2, \dots, \sum_{i=1}^m y_i^n \right)$$