Redfield-Polya enumeration, but the colors don't matter

Question

Is there a version of Redfield-Polya enumeration with the added condition that you don't care which color is which? An illustrative example is: Count edge-colorings of $K_4$ modulo the group action of graph isomorphism and permutation of the colors.

I don't believe this is as simple as quotienting out by permuting colors with the same number of edges. For example, the graph with a red 3-star and a blue triangle and the graph with a blue 3-star and a red triangle are distinct in standard Polya enumeration but we want to drop one of them. Meanwhile, the graph with a red 3-path and a blue 3-path are already considered equivalent by Polya enumeration. So, we have to account for color relabelings that are already induced by graph isomorphisms!

Any references you know of would be appreciated. Thanks!

Answer 1

To modify the Pólya enumeration theorem to count colorings as equivalent if they agree up to a reassignment of colors: Let $G$ be the automorphism group of the structure and $H$ the symmetric group on the set of colors. Then, the number of colorings up to equivalence is $$\left.P_G\left(\frac{d}{dz_1}, \frac{d}{dz_2}, \ldots\right) P_H(e^{z_1 + z_2 + z_3 + \cdots}, e^{2(z_2 + z_4 + z_6 + \cdots)}, e^{3(z_3 + z_6 + z_9 + \cdots)}, \ldots)\right\vert_{z_1 = z_2 = \cdots = 0} ,$$ where $P_G$ and $P_H$ are the cycle index polynomials of the action of $G$ and the left action of $H$ on itself. See, e.g., C.L. Liu, Introduction to Combinatorial Mathematics, Theorem 5.7.

In our case, $G := \operatorname{Aut}(K_4) \cong S_4$, and it acts faithfully on the set $\mathcal{E}$ of edges, defining an embedding $S_4 \hookrightarrow S_6$. Denote the vertices by $a, b, c, d$ and the edges $ab, ac, ad, bc, bd, cd$ respectively by $1, \ldots, 6$. Then, $S_4$ is generated by the transposition $(ab)$ and the $4$-cycle $(abcd)$, which correspond respectively to the permutations $$(24)(35) \quad \textrm{and} \quad (1364) (25) .$$ Computing directly gives that the cycle index polynomial for the action of $G \cong S_4$ on $\mathcal{E}$ is $$P_G(x_1, \ldots, x_6) = \frac1{24} x_1^6 + \frac38 x_1^2 x_2^2 + \frac14 x_2 x_4 + \frac13 x_3^2 .$$

The symmetric group on a set of $2$ colors is $H \cong C_2$, and its cycle index polynomial is $$P_H(y_1, y_2) = \frac12 y_1^2 + \frac12 y_2 .$$ So, $$P_H\left(e^{z_1 + \cdots + z_6}, e^{2 (z_2 + z_4 + z_6)}\right) = \frac12 e^{2 z_1 + \cdots + 2 z_6} + \frac12 e^{2 z_2 + 2 z_4 + 2 z_6}.$$

Assembling the ingredients gives that the number of equivalent colorings is, where we denote $\partial_i := \frac{d}{dz_i}$, \begin{multline*} \left.P_G\left(\partial_1, \ldots \partial_6\right) P_H\left(e^{z_1 + \cdots + z_6}, e^{2 (z_2 + z_4 + z_6)}\right)\right\vert_{z_1 = \cdots = z_6 = 0} \\ = \left.\left(\frac1{24} \partial_1^6 + \frac38 \partial_1^2 \partial_2^2 + \frac14 \partial_2 \partial_4 + \frac13 \partial_3^2\right) \left(\frac12 e^{2 z_1 + \cdots + 2 z_6} + \frac12 e^{2 z_2 + 2 z_4 + 2 z_6}\right)\right\vert_{z_1 = \cdots = z_6 = 0} = \color{#bf0000}{\boxed{6}} , \end{multline*} as expected.

Analogous computations gives that up to equivalence there are $18$ edge colorings of $K_5$ and $78$ edge colorings of $K_6$.

Answer 2

By way of enrichment this can also be done using Power Group Enumeration. As this algorithm has appeared here many times I will just give one reference to this MSE link.

It remains to compute the two cycle indices, one for the action of the symmetric group on the edges of $K_n$ (slots) and the symmetric group $S_m$ on the colors. The former is a standard computation and the latter is given by the Lovasz recurrence. We get the following Maple code:

pet_cycleind_symm :=
proc(n)
option remember;
    local l;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_cycleind_edg :=
proc(n)
option remember;
local all, term, termvars, res, l1, l2, inst1, u, v,
    uidx, vidx;

    if n=0 or n=1 then return 1; fi;

    all := 0:
    for term in pet_cycleind_symm(n) do
        termvars := indets(term); res := 1;

        # edges on different cycles of different sizes
        for uidx to nops(termvars) do
            u := op(uidx, termvars);
            l1 := op(1, u);

            for vidx from uidx+1 to nops(termvars) do
                v := op(vidx, termvars);
                l2 := op(1, v);

                res := res *
                a[lcm(l1, l2)]
                ^((l1*l2/lcm(l1, l2))*
                  degree(term, u)*degree(term, v));
            od;
        od;

        # edges on different cycles of the same size
        for u in termvars do
            l1 := op(1, u); inst1 := degree(term, u);
            # a[l1]^(1/2*inst1*(inst1-1)*l1*l1/l1)
            res := res *
            a[l1]^(1/2*inst1*(inst1-1)*l1);
        od;

        # edges on identical cycles of some size
        for u in termvars do
            l1 := op(1, u); inst1 := degree(term, u);
            if type(l1, odd) then
                # a[l1]^(1/2*l1*(l1-1)/l1);
                res := res *
                (a[l1]^(1/2*(l1-1)))^inst1;
            else
                # a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
                res := res *
                (a[l1/2]*a[l1]^(1/2*(l1-2)))^inst1;
            fi;
        od;

        all := all + lcoeff(term)*res;
    od;

    all;
end;

kn_pge :=
proc(n,m)
option remember;
local idx_slots, idx_colors, res, term_a, term_b,
    v_a, v_b, inst_a, inst_b, len_a, len_b, p, q;

    if n = 1 or m = 1 then return 1 fi;

    idx_slots := pet_cycleind_edg(n);
    idx_colors := pet_cycleind_symm(m);

    res := 0;

    for term_a in idx_slots do
        for term_b in idx_colors do
            p := 1;

            for v_a in indets(term_a) do
                len_a := op(1, v_a);
                inst_a := degree(term_a, v_a);

                q := 0;

                for v_b in indets(term_b) do
                    len_b := op(1, v_b);
                    inst_b := degree(term_b, v_b);

                    if len_a mod len_b = 0 then
                        q := q + len_b*inst_b;
                    fi;
                od;

                p := p*q^inst_a;
            od;

            res := res +
            lcoeff(term_a)*lcoeff(term_b)*p;
        od;
    od;

    res;
end;

We get for at most two colors

$$1, 1, 2, 6, 18, 78, 522, 6178, 137352, \ldots$$

which points us to OEIS A007689 where we find confirmation of this result.

With at most three colors we find

$$1, 1, 3, 15, 142, 4300, 384199, 98654374, 70130880569, \ldots$$

With at most four colors we get

$$1, 1, 3, 22, 513, 67685, 37205801, 74992370359, \\ 543437207831908, \ldots$$

With at most five colors the result is

$$1, 1, 3, 24, 956, 370438, 794610689, 7713545142724, \\ 334331083961076765, \ldots$$

Observe that when we have $m\gt n(n-1)/2$ the answer stops changeing and becomes independent of $m$ because we have more colors than edges in the graph. With this we get the sequence

$$1, 1, 3, 25, 1299, 1974452, 94345468975, 152799292695935115, \\ 10526127565809458484649781, \ldots$$

This gives the number of colorings of $K_n$ using any number of swappable colors. We observe that we should get one minus this sequence when we have $m=-1+n(n-1)/2$ colors because with all colors distinct there is just one such graph and this is indeed what the Maple code produces.

Important remark. These sequences are not in the OEIS, which is highly unlikely and leads me to question the work above. Therefore we need someone to independently verify these numbers.

Adddendum. These sequences are in fact in the OEIS I just missed them during my consultation. They are OEIS A230367, OEIS A233748, OEIS A233894, and OEIS A309116.