DISTINGUISHING SETS UNDER GROUP ACTIONS, THE WREATH PRODUCT ACTION

ALICE MARK

1. Notation, Definitions, and Other Background

Notation 1.1. Throughout this paper, the following will be used:

(1) Right group actions will be denoted by exponentiation, so if G is a group action on a set X, g ∈ G, x ∈ X then x^{g} denotes the action of g on x.

(2) [n] denotes the set with n elements, {1, …, n}.

Definition 1.2 (Distinguishing number of a graph). Let Γ = (V, E) be graph and let f : V → [r] be a coloring of the set of vertices by r colors. We say that f is r-distingishing if the only automorphism of Γ that fixes the coloring f is the trivial automorphism. The distingishing number of Γ is denoted by D(Γ) and is equal to min{r | ∃f : V → [r] such that f is r-distinguishing}.

More generally, we can also talk about the distinguishing number of a set under a group action.

Definition 1.3 (Distinguishing number of a set under a group action). Let G be a group that acts on a set X. We say that an r-coloring f : X → [r] is rdistinguishing if the only element of G whose action perserves the labeling (i.e., f(x^{g}) = f(x) for all x ∈ X) is the identity. The distinguishing number of X under the action by G is denoted D_{G}(X) and is equal to min{r | ∃f : X → [r] such that f is r-distinguishing}.

Definition 1.4 (Orbit and Stabilizer). Let G be a group acting on a set X. For x ∈ X, the orbit of x Orb(x) = {y ∈ X | ∃g ∈ Gwithx^{g} = y}. Notice that the relation x ∼ y if x and y are in the same orbit is an equivalence relation on X, that is, either x and y are in the same orbit or their orbits are disjoint.

The stabilizer subgroup of G, Stab(x) = {h ∈ G | x^{h} = x} < G. It is easy to check that this is indeed a subgroup of G.

I will refer to this theorem later:

Theorem 1.5 (Orbit-Stabilizer Theorem). Let G be a group acting on a set X. For x ∈ X, |Orb(x)| · |Stab(x)| = |G|

Proof. Let x ∈ X. Define an equivalence relation on the members of G, where g ∼ h if x^{g} = x^{h}. Stab(x) is one of the equivalence classes, and there is one for each of the elements of Orb(x). Define a function f :Stab(x)×Orb(x) → G as follows: for h ∈Stab(x), x^{g} ∈Orb(x), f(h, x^{g}) = hg where g is the equivalence class of g. It is easy to check that f is a bijection. □

Date: 16 August 2007.

Definition 1.6 (Faithful group action). Let G be a group that acts on a set X. We say that the action of G is faithful if for every g ∈ G that is not the identity, there exists x ∈ X such that x^{g} ≠ x.

Definition 1.7 (Transitive group action). The action of a group G on a set X is called transitive if X is the only orbit, that is for all x, y ∈ X, there exists g ∈ G such that x^{g} = y.

Examples 1.8. Some transitive group actions:

(1) The symmetric group S_{n} acts transitively on the set of n elements [n], since each number is moved to each spot by some group element.

(2) The dihedral group D_{n} acts transitively on the set of vertices of the n-gon, since each vertex can be taken to each other vertex by a rotation.

Definition 1.9 (Imprimitive group action). Let G be a group that acts faithfully and transitively on a set X. Call X′ ⊆ X an imprimitive block if for each g ∈ G, either X^{′g} = X′ or X^{′g} ∩ X′ = ∅. The action of G on X is said to be imprimitive if such a block can be found.

Example 1.10. Let (V, E) be a graph, n ∈ ℕ and let

Γ = ⨆_{i=1}^{n} (V, E)

Then the action of Aut(Γ) on Γ is imprimitive, and each copy of the original (V, E) is an imprimitive block.

Definition 1.11 (Semi-direct product of groups). Let G and H be groups. Let ϕ : H →Aut(G) be a homomorphism. H acts on G by this homomorphism in the following way: for h ∈ H, g ∈ G g^{h} = g^{ϕ(h)}. The semidirect product G ⋊_{ϕ} H is the group made up of the elements of G × H and with internal law of composition (g, h)(g′, h′) = (gg^{′h^{−1}}, hh′).

Definition 1.12 (Wreath product of groups). Let G and H be groups acting on the right faithfully on sets X and Y. Let G^{Y} be the set of functions f : Y → G. This can be considered a group with composition law (ff′)(y) = f(y)f′(y). The wreath product G_{≀Y} H is the semidirect product G^{Y} ⋊_{ϕ} H where ϕ is the homomorphism ϕ : H →Aut(G^{y}) defined as follows: for f ∈ G^{Y} , h ∈ H ϕh f^{h}(y) = f(y^{h^{−1}}). The wreath group G_{≀Y} H acts on the set X × Y by (x, y)^{(f,h)} = (x^{f(y)}, y^{h}).

Remark 1.13. What the wreath action G_{≀Y} H on X×Y does is create an imprimitive action where the blocks are all copies of X and the set of blocks is a copy of Y. An element of the group (f, h) will take an element of the set (x, y) to the block designated y^{h} and then will act on the block by f(y).

Remark 1.14. Since G and H act on the right, the wreath action is a right wreath action, so we have the group G^{Y} ⋊_{ϕ} H. In this group, elements are composed from the right, so (f, h)(f′, h′) = (ff^{′h^{−1}}, hh′). If the actions of G and H were left actions we would have the group H_{ϕ} ⋉G^{Y}. In this group, composition is done from the left, so (h, f)(h′, f′) = (hh′, f^{h^{′−1}}f′).

2. A theorem about the distinguishing number of the wreath action

Chan proves the following theorem in [1]:

Theorem 2.1. Let G and H be groups acting transitively and faithfully on the sets X and Y respectively. For each r, let n_{r} be the number of distinguishing r-colorings

of X. Let S = \{r | n_{r} ≥ D_{H}(Y) · |G|\}. Then D_{G_{≀Y} H}(X × Y) = \begin{cases}min S & if S ≠ ∅ \\ ∞ & if S = ∅ \end{cases}

Remark 2.2. It is interesting that Chan defines n_{r} to be the total number of distinguishing r-colorings. One could define it to be the total number of distinct distinguishing r-colorings, where two colorings C and C′ are distinct if there does not exist g ∈ G such that C(X) = C′(X^{g}). There are |G| more colorings if we include all non-distinct colorings, since if C is a distinguishing coloring, the total number of distinguishing colorings not distinct from C is |G| if we include C as not distinct from itself. It is because we are looking at all distinguishing r-colorings that we want to consider only the r such that n_{r} ≥ D_{H}(Y) · |G|. If n_{r} were the largest possible number of distinct distinguishing r-colorings, we would only want n_{r} ≥ D_{Y} (H). Of course, then we have to define what this maximum means.

Summary and Explanation of Proof. The proof constructs a coloring on X × Y by k = min S colors. First, consider the action of G on the set A of k distinguishing colorings of X, where G acts on A by a^{g}(x) = a(x^{g^{−1}}), so the color assigned to x ∈ X by a^{g} is the same as the color assigned to x^{g^{−1}} by a. Since each a ∈ A is a distinguishing coloring, Stab(a) = {1} for all a. Therefore by the orbit stabilizer theorem (1.5), each element has orbit length |G|. The number of orbits times |G| equals |A| since orbits are disjoint. Therefore, the number of orbits is equal to \frac{|A|}{|G|} = \frac{n_{k}}{|G|}. Since k ∈ S, \frac{n_{k}}{|G|} ≥ D_{H}(Y), so there are at least D_{H}(Y) distinguishing k-colorings of X that are in different orbits of the action of G on A. Select these colorings, and label them a_{1}, …, a_{D_{H}(Y)}. Let b be a distinguishing coloring of Y using D_{H}(Y) colors. Define a coloring C of X × Y as follows: C(x, y) = a_{b(y)}(x), so the color assigned to (x, y) ∈ X × Y is the same as the color assigned to x by the coloring a_{b(y)}.

Intuitively, what this is doing is coloring each block of X ×Y using one of the a_{i}. This makes sense since each block looks like X. Then each coloring a_{i} is treated as a color. Since the action on the blocks looks like the action of H on Y, these colorings distinguish the blocks.

There are two things to check about this coloring. First, we need to make sure it is distinguishing, second that there is no distinguishing coloring with fewer than k colors.

To show that it is distinguishing, we first assume that for some (f, h) ∈ G_{≀Y} H, C(x, y) = C((x, y)^{(f,h)}) for all pairs (x, y) ∈ X × Y and show that (f, h) = (1, 1). By construction, the assumption means that a_{b(y)}(x) = a_{b(y^{h})}(x^{f(y)}), so by the

definition of the action of G on A, a_{b(y^{h})}^{f(y)^{−1}} = a_{b(y)}. This implies that a_{b(y^{h})} and a_{b(y)} are in the same orbit of that action, but since the a_{i} were chosen from distinct orbits, they must be the same, so b(y^{h}) = b(y). Since b is distinguishing, h = 1. Now we have that C(x, y) = C((x, y)^{(f,1)}) for all pairs (x, y) ∈ X × Y, but this necessarily means f(y) = 1∀y since a_{b(y)}(x^{f(y)}) = a_{b(y)}(x) since a_{b(y)} is distinguishing. Therefore our coloring C is distinguishing.

Now all that remains to be shown is that there is no distiguishing coloring with fewer than k colors. Here we implicitly use the fact that the wreath action is imprimitive. Suppose we have a distinguishing l-coloring of X × Y, C′. For each y ∈ Y, define an l-coloring of X, a_{y} where for x ∈ X, a_{y} : x ↦ C′(x, y). Now suppose g ∈ G preserves a_{y}. Take f ∈ G^{Y} such that f(y) = g, and f(y′) = 1 for y′ ≠ y. Then C′((x, y′)^{(f,1)}) = C′(x^{f(y′)}, y) = C′(x^{1}, y) = C′(x, y′), so (f, 1) preserves C′. Since we assumed that C′ is distinguishing, we must have f = 1 which means g = 1 which means that a_{y} is a distinguishing coloring of X for each y. Now, as in the first part of the proof, let A′ be the set of all distinguishing l-colorings of X, and consider the action of G on A′ as before. Again, note that we have that the number of orbits is \frac{|A′|}{|G|} = \frac{n_{l}}{|G|}. This fact will come up later. Each of the colorings a_{y} is contained in one and only one of the orbits of this action since the orbits of an action are always disjoint. Let d be the number of orbits of the action of G on A′, and index the orbits by [d]. Define b, a coloring of Y, as follows: b : Y → [d] by b(y) = i if a_{y} is in the i-th orbit. Suppose we have h ∈ H that preserves b. If this is the case, then ∀y ∈ Y we have b(y) = b(y^{h}) which by the way we defined b means that a_{y} and a_{y^{h}} are in the same orbit, so ∃g_{y} ∈ G st a_{y}^{g_{y}} = a_{y^{h}}. Let f ∈ G^{Y} be the function f(y) = g_{y}. Then for (x, y) ∈ X × Y we

have C′((x, y)^{(f,h)}) = C′(x^{f(y)}, y^{h}) = C′(x^{g_{y}}, y^{h}) = a_{y^{h}}(x^{g_{y}}) = a_{y^{h}}^{g_{y}^{−1}}(x) = a_{y}(x) = C′(x, y) which implies that (f, h) = (1, 1) since C′ is distinguishing. Since h = 1 we have that b is a distinguishing coloring of Y, so d ≥ D_{H}(Y). Therefore the number of orbits of the action \frac{n_{l}}{|G|}d ≥ D_{H}(Y) so n_{l} ≥ D_{H}(Y) · |G|. Therefore l ∈ S so l ≥ min S = k, so every distinguishing coloring uses at least k colors.

Finally, in the case where S = ∅, The proof has shown that if there is a distinguishing k-coloring for some finite k, then n_{k} ≥ D_{H}(Y) · |G|. If there is no such k, as S = ∅ implies, then there is no finite coloring, so the distinguishing number is infinite. [1]

3. Some examples

Example 3.1 (Symmetric Groups). The symmetric group on k elements is the permutation group of the set [k]. The group acts on the set by permuting the elements. The distinguishing number of this action D_{S_{k}}([k]) = k. This is because if we color the elements of [k] with k − 1 colors, there must be 2 with the same color since there are k elements total. There is a transposition element of S_{k} that switches these two, while holding all others fixed. Therefore the coloring is not distinguishing, so we need at least k colors. Of course, we need at most k colors since there are only k elements.

Remark 3.2. As a side note, consider the alternating group A_{k} = {σ ∈ S_{k} | σ is an even permutation} in its action on [k]. The transpositions are odd, so they are not in A_{k}. Let C be a distinguishing coloring of [k] under A_{k} if for x, y ∈ [k] we have C(x) = C(y), any permuation that switches them will also switch another pair. Therefore there cannot be any other pairs with the same color. If there is a third point colored the same as x and y then there is a 3-cycle that permutes them. Therefore there can be at most two elements with the same color and all others must be distinct, so D_{A_{k}}([k]) = k − 1

Consider the symmetric groups S_{k} and S_{m} and their respective actions on [k] and [m]. The distiguishing number of the wreath action of S_{k}_{≀[m]}S_{m} on [k] × [m] can be computed directly for certain m and k.

Claim. D_{S_{k}_{≀[m]}S_{m}}([k] × [m]) = k + 1 if m ≤ k + 1

Proof. Suppose for contradiction that we have a distinguishing coloring C of [k] × [m]that uses k colors. For each y ∈ [m], the set A_{y} = {(x, y)|x ∈ [k]} is a “copy” of [k], and the action of {(f, 1)|f ∈ G^{Y} } on A_{y} is “isomorphic” to the action of S_{K} on [k]. Therefore, k colors are required to distinguish each set A_{y}, so the coloring C must assign the same k colors to each A_{y}, and all of them must be used for each A_{y}.

Now consider A_{y} and A_{y′}, and let σ ∈ S_{m} such that y^{σ} = y′ ≠ y. For each (x, y) ∈ A_{y}, there exists a unique (x′, y′) ∈ A_{y′} such that C(x, y) = C(x′, y′), and there exists π ∈ S_{k} such that x^{π} = x′. Since there exists f ∈ G^{Y} such that f(y) = π, we have C(x, y) = C(x′, y′) = C(x^{π}, y^{σ}) = C(x^{f(y)}, y^{σ}) = C((x, y)^{(f,σ)}) so C is not distinguishing, so more than k colors are required.

To see that k + 1 colors is enough, assign a coloring as follows: \binom{k+1}{k} = k + 1 so there are k + 1 ways to choose k colors. Since m ≤ k + 1, there are at most k + 1 sets A_{y}, so each one may be assigned a different k colors taken from the original k + 1 colors. If we use all k colors for each A_{y}, the claim is that we have a distiguishing coloring. If for (f, σ), C(x, y) = C(x, y)^{(f,σ)} for all (x, y) we have two cases to check. First suppose σ ≠ 1, let y ∈ [m] such that y^{σ} ≠ y. There exists x such that C(x, y) ≠ C(x^{f(y)}, y^{σ}) since A_{y} is colored by a different set of k colors than A_{y^{σ}}, so this case will not happen. If σ = 1, we have C(x, y) = C((x, y)^{(f,1}) = C(x^{f(y)}, y)∀y ∈ [m], but since (x^{f(y)}, y) ∈ A_{y} and each element of A_{y} is colored a different color, we must have (x^{f(y)}, y) = (x, y) which implies that x = x^{f(y)} for all x ∈ [k] so f = 1. So we have (f, σ) = (1, 1) so C is distinguishing. □

Using the theorem, we arrive at the same result much more quickly. The function n_{r} = \binom{r}{k}k!, since from r colors we want to select k of them, and then we can assign them to [k] in k! many ways. Then S = \{r | \binom{r}{k}k! ≥ mk!\} so min S is the minimal r such that \binom{r}{k} ≥ m. As we saw before, this must be k + 1.

What happens when m−k is a fairly large number? It is not as easy to compute D_{S_{k}_{≀[m]}S_{m}}([k] × [m]) when m ≥ k + 2. The reason for this becomes apparent when we try to use the theorem to compute it.

It is clear that for fixed m and k, \binom{r}{k} is eventually greater than m as r increases, so S ≠ ∅. It turns out that we can’t compute this number because that would involve soving a large degree polynomial. The number we are looking for is the smallest integer r such that \binom{r}{k} ≥ m. The sequence of numbers a_{k}_{r} = \binom{r}{k} is the kth diagonal sequence of Pascal’s triangle, where the first diagonal sequence a_{1}_{r} = 1, the second a_{2}_{r} = r and in general

a_{k}_{r} = ∑_{i=1}^{r−1} a_{k−1}_{i}

The closed form of this formula is

a_{k}_{r} = ∏_{i=1}^{k−2} (i + r)

which is a polynomial in r of degree k − 2.

There is no easy way to compute the exact value of r from this, but we can approximate. We want \binom{r}{k} ≥ m > \binom{r−1}{k}. We can bound \binom{r}{k} in the following way:

\binom{r}{k} = \frac{r(r − 1) … (r − k + 1)}{k!}

The numerator is a productof k terms, so it can be bounded above by the largest:

\binom{r}{k} < \frac{r^{k}}{k!}

Similarly, \binom{r−1}{k} can be bounded below:

\binom{r − 1}{k} > \frac{(r − k)^{k}}{k!}

so we want

\frac{r^{k}}{k!} > m > \frac{(r − k)^{k}}{k!}

Which means that

r > (mk!)^{\frac{1}{k}} > r − k

So the r we want is an integer in the interval ((mk!)^{\frac{1}{k}} , (mk!)^{\frac{1}{k}}).[3]

Example 3.3 (Dihedral Groups). The dihedral group on k elements is defined here to be the automorphism group of the k cycle C_{k}. It is isomorphic to the symmetry group of the k-gon. For the purposes of this paper, C_{k} refers to the vertex set of the k-cycle, although it might as well refer to the edges. The distinguishing number

D_{D_{k}}(C_{k}) = \begin{cases}3 & if 3 ≤ k ≤ 5 \\ 2 & if 5 < k \end{cases}

This should be clear in the k ≤ 5 cases. The k = 6 and k = 7 cases are pictured below. For larger k, the pattern can continue with longer sections colored all by 2. The 6-cycle is included in figure 1 because it has interesting unavoidable symmetry.

Figure 1. distinguishing 2-colorings of C_{6} and C_{7}

If colors 1 and 2 are switched in the 6-cycle coloring, the resulting graph is the same as it would be if it were reflected across the axis that splits the graph fron the top left edge through the bottom right edge. There is an element of D_{6} that acts on the graph in this way. Other even cycles can be two colored in distinguishing ways with this kind of symmetry or not, but with a 6-cycle there is no other distinct distinguishing 2-coloring.

Consider the wreath action of D_{k}_{≀C_{m}}D_{m} on C_{k} × C_{m}. Unlike symmetric groups, it is easier to count the distinguishing number for large k and m.

Claim. For k ≥ 7, m > 6, D_{D_{k}_{≀Cm} D_{m}}(C_{k} × C_{m}) = 2

Proof. Since one color is clearly not enough, all we need is to construct a 2-coloring that works. For y ∈ C_{m} let A_{y} = {(x, y)|x ∈ C_{k}}. A_{y} is a copy of C_{k} within C_{k} × C_{m}, and for any h ∈ D_{m}, {(f, h)|f ∈ D_{k}^{C_{m}}} acts on A_{y^{h}} in the same way D_{k} acts on C_{k}. Therefore only 2 colors are needed to distinguish A_{y} for each y. The wreath group acts on the set of sets A_{y} in the same way D_{m} acts on C_{m}. In order to distinguish the set of sets A_{y}, we need 2 distinct 2-distinguishing colorings, where distinct means that the number of elements colored by color 1 in the first coloring is different from the number of elements colored by color 1 in the second coloring. Two distinct colorings exist for k > 7, all we need is to take one without the symmetry of the C_{6} coloring and switch the color of each vertex. □

Using the theorem, we should get the same result.

Claim. Same as above.

Proof. If k > 7, n_{2} ≥ 2k · 2 = 4k where 2k = |D_{k}| is the number of colorings we get by acting on C_{k} with D_{k}. It is multiplied by 2 since when we switch one color with the other we get a distinct coloring. There are even more ways, as described earlier, however we don’t even need to count them since D_{D_{m}}C_{m} · |D_{k}| = 2 · 2k so the numbers are already equal. Since n_{1} = 0, we have min S = 2. □

This deals with most cases. The theorem makes the others a lot simpler. For 3 < m < 5, we have D_{D_{m}}(C_{m}) = 3 and |D_{k}| = 2k so S = {r|n_{r} ≥ 6k}. For m > 5 we have D_{D_{m}}(C_{m}) = 2 and |D_{k}| = 2k so S = {r|n_{r} ≥ 4k}, so we need to compute n_{r}, at least partially, for these cases.

In the case where k = 3, the function n_{r} = \binom{r}{3}3! since D_{3} ≅ S_{3}. If 3 ≤ m ≤ 5, min S is the minimal r such that 6\binom{r}{3} ≥ 6 · 3 so the r we want is 4. If 5 < m min S is the minimal r such that 6\binom{r}{3} ≥ 4 · 3, so again the r we want is 4.

In the case where k = 4, the function n_{r} is more complicated since it is the sum of the number of 3-colorings plus the number of 4-colorings. The number of 3colorings by r colors is 24\binom{r}{3}. A distinguishing 3-coloring of C_{4} is shown in figure 2. First we choose 3 colors, then choose which one will be used for two vertices. Note that the two with the same color must be next to each other as in the figure, since there are group elements that switch each pair of opposite corners while holding the other pair fixed. Then there are 4 ways this can be rotated, and the two colors used only once can be flipped, so the whole thing is multiplied by 3 · 4 · 2 = 24

Figure 2. distinguishing 3-coloring of C_{4}

The number of distinguishing 4-colorings is simply 24\binom{r}{4} since we choose 4 colors and then place them in 4 distinct spots. Therefore n_{r} = 24(\binom{r}{3} + \binom{r}{4}).

If 3 ≤ m ≤ 5, min S = min\{r | 24(\binom{r}{3} + \binom{r}{4}) ≥ 6 · 4\} So the r we want is 3 (note that if r < k, \binom{r}{k} := 0). This is also the result when m > 5 since 4 · 4 < 6 · 4 and with r < 3 n_{r} = 0. Computing n_{r} explicitly wasn’t even necessary, since already there are enough 3-colorings that we need not even consider the 4-colorings.

In the case where k = 5, n_{r} is the sum of the number of distinguishing 3,4, and 5-colorings. As before, however, we can find enough 3-colorings that we need not even consider 4 and 5-colorings. The number of distinguishing 3-colorings is 72\binom{r}{3}. There are a few different kinds of distinguishing 3-colorings of C_{5}, shown in figure 3. In all cases, we first choose 3 colors. In cases (a) and (c), there are 3 choices for which color is used 3 times, there are 2 ways to order the remaining 2 colors, and there are 5 ways to place them to make a picture like (a) and 5 ways to place them to make a picture like (c). Therefore we multiply by 3 · 2 · 10 = 60. To get (c) and (d), first we have 3 choices for the one single color, then we must order the pairs. There are 2 ways if vertices of the same color are next to each other(c), and 2 ways if they are not (d). Therefore the whole thing is multiuplied by 3 · 4 = 12. This gives us that the total number of 3-colorings of C_{5} is 60\binom{r}{3} + 12\binom{r}{3} = 72\binom{r}{3}

Figure 3. ways to color C_{5} with 3 colors

All that we need to notice is that the terms describing the number of 4 and 5-colorings will be a\binom{r}{4} and b\binom{r}{5} respectively for some constants a and b. When r = 1 or 2, all three terms will be 0. Therefore the smallest nonzero value of n_{r} occurs when r = 3, at which point the 4 and 5 terms are 0 and the 3 term is 72. This will be plenty of colorings, since if 3 ≤ m ≤ 5 we want n_{r} ≥ 6 · 5 = 30 and when m > 5 we want n_{r} ≥ 4 · 5 = 20, so with 3 colors we have enough colorings.

We can also see that this is true if we thing about this problem in terms of distinct colorings, as described in Remark 2.2. No m will require more than 3 distinct distinguishing colorings, and figure 3 shows that we have 4 distinct distingushing colorings of C_{5}.

In the case where k = 6, n_{r} is the sum of the number of 2, 3, 4, 5, and 6-colorings of C_{6}. Once again, it will not be necessary to compute this entirely.

The total number of distinguishing 2-colorings by r colors is 12\binom{r}{2}, since there is only 1 distinct 2-coloring and |D_{6}| = 12. The number of distinguishing 3-colorings of D_{6} by r colors is going to be larger than the number of distincguishing 3-colorings of D_{5} by r colors, since each distinct 5-coloring gives rise to at least 1 6-coloring, and there is a way to do this such that the 6-colorings generated will all be distinct. So it will be a\binom{r}{3} where a > 72. Following a similar argument to the k = 5 case, we find that r = 3 both when 3 ≤ m ≤ 5 and when m > 5.

Figure 4. 3 distinct 2-colorings of C_{k} for k ≥ 7

Finally in the case where k ≥ 7, we need only consider what happens when 3 ≤ m ≤ 5, since we have already done the other case. It should be clear that there are at least 3 distinct 2-colorings of C_{k} from figure 4

It turns out that for all k, min S is the same no matter what m is. This is because n_{r} goes up in such big jumps that there is no case where 6k > n_{r} ≥ 4k.

Everything is summarized in table 1.

Table 1. Table of cases. Note that if k > r, \binom{r}{k} := 0.
D_{D_{k}_{≀Cm} D_{m}}C_{k} × C_{m} = min S

\begin{matrix}k & 3 & 4 & 5 & 6 & ≥ 7 \\ min S & 4 & 3 & 3 & 3 & 2 \end{matrix}

Example 3.4 (Symmetric and Dihedral groups). It is interesting what happens with the wreath action of a symmetric and a dihedral group. Let S_{K} be the symmetric group acting on the set [k], and let D_{m} be the automorphism group of the m-cycle C_{m}. It should not be suprising that D_{S_{k}_{≀Cm} D_{m}}([k] × C_{m}) is not the same as D_{D_{m}_{≀[k]}S_{k}}(C_{m} × [k]).

In the first case, the blocks look like symmetric groups and the action on the blocks looks like a dihedral action. We therefore need either 3 or 2 distinct colorings of the symmetric group on k elements, depending on whether 3 ≤ m ≤ 5 or m > 5. Either way, if k > 1 we have \binom{k+1}{k} = k + 1 ≥ 3 so the distinguishing number will be k + 1

In the second case the blocks look like dihedral groups, so 2 or 3 colors are needed to distinguish each one depending on whether 3 ≤ m ≤ 5 or m > 5. We need k distinct colorings of the blocks, however, since the wreath group acts on the blocks in the way S_{k} acts on [k]. For small k this will be easy to solve for, and we can use much the same method as when both were dihedral groups. When k is very large, however, it is necessary to compute explicitly what n_{r} will be for a given m. This is possible, and can be done using combinatorial arguments, but the process is long and repetitive.

References

[1] Melody Chan. The distinguishing number of the direct product and wreath product action. Yale University. 2005.

[2] Thanks to Ian Shipman.

[3] Also thanks to Laci Babai for a suggestion.