Algebraic combinatorics lecture 14: Polya Theory

We are given a domain {D}, a finite set {R}, and a group {G} acting on {D}, {H} acting on {R}. Let {\mathcal{F}(D,R) = \{f: D \rightarrow R\}} and {f^{g,h}(d) = (f(d^g))^h}, i.e., {G \times H} acts on {\mathcal{F}(D,R)}, and splits it into orbits. Visually it’s easiest to represent {\mathcal{F}(D,R)} as coloring schemes of balls. In this case {R} is the set of colors, and {D} is the set of balls. If the balls are arranged in some graph with symmetry, then {G} could be the symmetry group. {H} being either the full symmetry group or the trivial group makes sense, but others are possible.

Definition 1 a weight {w: R \rightarrow A}, {A} some algebra, e.g. {k[x_1,\ldots, x_s]}, extends to a weight on {\mathcal{F}(D,R)} by

\displaystyle  w(f) =\prod_{d \in D} w(f(d)). \ \ \ \ \ (1)

We say {w} is an invariant weight if {w(f_1) = w(f_2)} for {f_2 = f_1^{g,h}} for any {f_1}, {g \in G} and {h \in H}.
An orbit of {G \times H} on {\mathcal{F}(D,R)} is called a pattern.

Theorem 2 (de Bruijn): Let {w} be an invariant weight,

\displaystyle  \sum_{p \in \mathcal{F}(D,R)/(G \times H)} w(p) = \frac{1}{|G||H|} \sum_{g,h} \sum_{f: f^{g,h}=f} w(f). \ \ \ \ \ (2)

Proof: An easy application of not-Burnside’s theorem, which states

Lemma 3 (Sunnyside) Suppose {X} is a finite set, {G} acts on {X}, {F(g) := \{x: x^g = x\}} is the set of points fixed by {g}, and {G_x=\{g: x^g = x\}} is the symmetries fixing {x}. Suppose also that {X} splits into orbits {X = \mathcal{O}_{x_1} \coprod \mathcal{O}_{x_2} \ldots \coprod \mathcal{O}_{x_t}}. Then

\displaystyle  \frac{1}{|G|} \sum_{g \in G} F(g) = t. \ \ \ \ \ (3)

Proof: (of Sunnyside) Let {B = |\{(x,g): x^g =x\}|}.

\displaystyle  \sum_g |F(g)| = B = \sum_x |G_x| = \sum_{i=1}^t |\mathcal{O}_{x_i}| |G_{x_i}| \\ \sum_{i=1}^t \frac{|G|}{|\mathcal{O}_{x_i}|} |\mathcal{O}_{x_i}| = t|G|. \ \ \ \ \ (4)

\Box

Continuing with De Bruijn, we fix {a \in A} in the range of {w}. Let {P_a = \{\text{pattern } p: w(p) = a\}}. Then {P_a}‘s partition {\mathcal{F}(D,R)}. Also {G \times H} acts on {P_a}. Then {G \times H} acts on {P_a}. By not-Burnside’s theorem,

\displaystyle  |P_a| = \frac{1}{|G||H|} \sum_{g,h} F_{P_a}(g,h), \ \ \ \ \ (5)

where {F_{P_a}(g,h)} denotes the elements in {P_a} fixed by {(g,h)}. Multiply both sides by {a} and sum over the range of {w} gives (2). \Box

Specializing De Bruijn’s result to {H= \{id\}}, i.e., all colors are distinct, we get Polya’s theorem.
Now let {A = Q[y_1, \ldots, y_\infty]}, {r \in R}, and {w(r) \in A} and as usual {w(f) = \prod_{d \in D} w(f(d))}. Then we have

\displaystyle  \sum_{\text{pattern } p} w(p) = \frac{1}{|G|} \sum_{g \in G} \sum_{f: f^g =f} w(f). \ \ \ \ \ (6)

Fixing {g \in G}, and write {g = c_1 c_2 \ldots c_k} as a product of cycles, with {c_i = (d, d^g, d^{g^2}, \ldots )} in the permutation representation of {G} on {D} (in other words {G} can be thought of as a subgroup of {S_{|D|}}). We also denote {C_i = \{d, d^g, \ldots \}}, i.e., the support of {c_i}.
Let {f :D \rightarrow R} be such that {f^g = f}, i.e., {f} is constant on the {C_i}‘s (we abuse {f^{g,id}} as {f^g}). Consider the algebraic manipulation

\displaystyle  \prod_{i=1}^k \sum_{r \in R} w(r)^{|C_i|} = \sum_{f: \text{ constant on each }C_i} \prod_{d \in D} w(f(d)) = \sum_{f: f^g = f} w(f). \ \ \ \ \ (7)

The forgoing computation leads to

Theorem 4 (Polya) Say {|D| =d}, and let {p_G(x_1, \ldots, x_d) = \frac{1}{|G|} \sum_{g \in G} x_1^{a_1(g)} \ldots x_d^{a_d(g)}}, where {a_i(g) =} number of cycles in {g} of length {i}. Then

\displaystyle  \sum_{\text{pattern } p} w(p) = p_G(\sum_{i \in R} w(i), \sum_{i \in R} w(i)^2, \ldots, \sum_{i \in R} w(i)^d). \ \ \ \ \ (8)

In particular, the total number of patterns equal {p_G(|R|, \ldots, |R|)}.

Examples: Let {D} be {[4]}, with {G = C_4},

\displaystyle  p_{C_4}(x_1, \ldots, x_4) = \frac{1}{4} (x_1^4 + x_2^2 + 2 x_4). \ \ \ \ \ (9)

If we have two colors, then {|R|=2}, and {\frac{1}{4}(2^4 + 2^2 + 4)=6} (recall {H = \{ id\}}). And indeed there are 6 ways of coloring {D} up to {C_4} symmetry with two colors.
Example 2: Want 2 red and 2 blue: then we set {w(R) = y_1} and {w(B) = y_2}. And we need
\displaystyle [y_1^2 y_2^2] p_{C_4}(y_1 + y_2, y_1^2 + y_2^2, y_1^3 + y_2^3, y_1^4 + y_2^4) = \frac{1}{4}(6 + 2) = 2. Indeed there are only two ways of distinct colorings in this situation, namely BRBR or BBRR.
More generally, given {G, D}, the {[y_1^{a_1} \ldots y_d^{a_d}]} coefficient of {p_G( \sum y_i, \sum y_i^2, \ldots, \sum y_i^d)} is the number of colorings with {a_i} color {i}.

2. Cycle Indices

  1. {G = C_n}, {P_{C_n}(x_1, \ldots, x_n) = \frac{1}{n} \sum_{d | n} \phi(d) x_d^{n/d}}.
  2. {G= D_{2n}} the dihedral group: then for n odd

    \displaystyle  p_{D_{2n}}= \frac{1}{2n} (nx_1 x_2^{\frac{n-1}{2}} + \sum_{d |n} \phi(d) x_d^{n/d}) \ \ \ \ \ (10)

    and for {n} even

    \displaystyle  p_{D_{2n}} = \frac{1}{2n}( \frac{n}{2} x_2^{n/2} + \frac{n}{2} x_1^2 x_2^{(n-2)/2} + nx_1 x_2^{\frac{n-1}{2}} + \sum_{d |n} \phi(d) x_d^{n/d}). \ \ \ \ \ (11)

  3. {G=S_n}: we get the familiar

    \displaystyle  p_{S_n}(x_1, \ldots, x_n) = \frac{1}{n!} \sum_{\lambda \vdash n} \frac{n!}{z_{\lambda}} \prod_{i=1}^n x_i^{a_i(\lambda)}. \ \ \ \ \ (12)

  4. If {G_i} acts on {D_i} for {i=1,2}, and {D_1 \cap D_2 = \emptyset}, then {G_1 \oplus G_2} acts on {D_1 \cap D_2}, and {p_{G_1 \oplus G_2} = p_{G_1} p_{G_2}}.
  5. Wreath product: Suppose {I} is an index set, {D} is a set, {G} acts on {I}, and {H^{|I|}} acts on {D^{|I|}} coordinate-wise. Also let {G \ltimes H^{|I|}:= \{(g; h_1, \ldots, h_{|I|})\}} be the wreath product of {G} and {H} under the above action. Then

    Theorem 5

    \displaystyle  P_{G \ltimes H}(x_1,x_2, \ldots) = p_G(p_H(x_1,x_2,\ldots), p_H(x_2,x_4,\ldots),p_H(x_3,x_6,\ldots),\ldots). \ \ \ \ \ (13)

    Literature: James and Kerber. Rep. Theory of symmetrici groups.
    A. Kerber: Group acting on sets.
    R. Read: Polya’s theory of enumerations.

  6. Alas, computing the cycle indices is {\#}-P complete even for {C_2^n}, a result of Jenaum-Golberg. Computational Polya Theory. This immediately implies that the Ising model partition function is {\#}-P complete to compute, for dimension {d > 2}.

More generally, for De Bruijn stuff i.e. nontrivial {H}, we need to do

  1. Find {p_G(x_1,x_2,\ldots)}
  2. associate {w(r_i) = y_i} for each {r_i \in R},
  3. for each {s =1, \ldots, d}, and {h \in H}, compute {S(h,s):= \{r: r^{h^s} =r\}}. Set {P_s(h) = \sum_{r \in S(h,s)} w(r) w(r^h) \ldots w(r^{h^{s-1}})}. If {S(h,r) = \emptyset}, set {P_s(h) = 0}.
  4. then the number of {G}-patterns {f: D \rightarrow R} (i.e., orbits under {G} action), invariant under {h}, with {a_i} color i, is {[y_1^{a_1} \ldots y_d^{a_d}] p_G(P_1(h), P_2(h), \ldots, P_d(h))}.
  5. The total number of {G \times H} patterns is then

    \displaystyle  \frac{1}{|H|} \sum_{h \in H} p_G(P_1(h), \ldots, P_d(h)). \ \ \ \ \ (14)

As a small application of Polya theory, we can do graph enumeration on a fixed number of vertices, up to permutation of the vertices:
{|D|= \binom{V}{2}}, {D} consists of distinct pairs {(i,j)}, and {G = S_V}, {R = \{0,1\}}, {H = \{id\}} or {C_2}. See paper by P. Hanlon and R. W. Robinson.

Advertisements

About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in algebraic combinatorics, Uncategorized. Bookmark the permalink.

5 Responses to Algebraic combinatorics lecture 14: Polya Theory

  1. drexel28 says:

    Friend, this is a fantastic blog. I cannot believe that I haven’t run into it before. The only comment I’d offer is I wish you’d ‘categorize’ them. I have been following your alg. comb. lecture series, but I wish I could just go to a category labeled ‘Algebraic Combinatorics’ for easy access–but this is a very minor detail!

    Just out of curiousity, what part of probability are you working in?

    Best,
    Alex Youcis

    • Dear Alex,
      Thank you for your interest in my blog. You are the first one to make a comment on the mathematical content. I will follow your advice to categorize the material from now on as well as back issues. In fact all the algebraic combinatorics lectures are taken from my advisor Persi Diaconis’ course. I am working in markov chain mixing, random matrix theory, as well as discrete probability models with symmetry.

      • drexel28 says:

        Friend,

        That is shocking that I am the first one to comment. This is a legitimate blog with interesting topics etc. Keep up the good work!

        As for your areas of research I must admit that while I know what a Markov chain is I have no idea what Markov chain mixing is. Also, I am only tangentially aware of random matrix theory after hearing about Montgomery’s result concerning the distrbution of the zeta zeros.

        Best,

        Alex

  2. drexel28 says:

    Also, how do you hyperlink back to a previous equation? For example, in your Berry-Esseen post you hyperlinked (1) and it, when clicked, brough the screen back to equation (1).

    • you can label the equations using \label{} and refer back to it using \eqref{} just as in usual latex. The easiest way is to use latex2wp, a free python script that converts latex files into wordpress latex format. I actually wrote a blog entry a while ago on how to make latex2wp into an executable file for windows system. You can search for that. Random matrix theory has connections to lots of other discrete models, due to its representation theoretic significance. A personal hero of mine is Kurt Johansson, who did lots of hardcore analytic stuff in related areas.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s