The following came up in a problem on graph reconstruction. It isn't very important, but I thought some people here might find it interesting and not too trivial (I'm not a group theorist).

Take a set $\Omega_n=\lbrace x_1,\ldots,x_n,y_1,\ldots,y_n\rbrace$ of $2n$ distinct atoms. A partition of $\Omega_n$ into ordered pairs is a set of ordered pairs of the form $x_iy_i$ or $y_ix_i$ such that for each $i$, exactly one of $x_iy_i$ and $y_ix_i$ appears. There are exactly $2^n$ such partitions altogether. An example of a partition of $\Omega_3$ into ordered pairs is $\lbrace x_1y_1,y_2x_2,x_3y_3\rbrace$, which is different from $\lbrace x_1y_1,y_2x_2,y_3x_3\rbrace$.

Now let $G$ be a permutation group on $\Omega_n$. $G$ has a natural action on the set of all partitions of $\Omega_n$ into ordered pairs: just apply it to the atoms where they appear. Thus, for $g\in G$, $\lbrace x_1y_1,y_2x_2,x_3y_3\rbrace^g = \lbrace x_1^gy_1^g,y_2^gx_2^g,x_3^gy_3^g\rbrace$. Now suppose that the set of partitions is closed under this action and that this action is transitive on the partitions.

Question: What can we say about $G$?

(Added:) Since we want $G$ the set of partitions to be closed under $G$, we know that $G$ is a subgroup of the wreath product $Z_2\wr S_n$.

Obviously $|G|\ge 2^n$. Also, it suffices to consider (inclusion-)minimal groups with the required transitivity.

The easiest example, with order, $2^n$ is $$G=\langle (x_1\,y_1), (x_2\,y_2), \ldots, (x_n\,y_n)\rangle.$$ Slightly less obviously, but still with order $2^n$, divide $\lbrace 1,2,\ldots,n\rbrace$ into singletons and pairs, and have a transposition for the singletons and a 4-cycle for the pairs. This is an informal definition, but as an example for $n=6$: $$G=\langle (x_1\,x_2\,y_1\,y_2), (x_3\,y_3), (x_4\,y_4), (x_5\,x_6\,y_5\,y_6)\rangle.$$ What else is there?

  • 3
    $\begingroup$ I'm a little confused by the way you've stated the problem. Not every permutation group on $\Omega_n$ acts on the set of partitions as you've defined them. The group of those that do is the wreath product $W=C_2\wr S_n$, and if $H$ is the subgroup $C_2^n$, then you're asking for subgroups $G$ of $W$ for which $W=HG$, I think. $\endgroup$ – Jeremy Rickard Feb 14 '14 at 16:42
  • $\begingroup$ Yes, you are right. I'm only referring to subgroups of the wreath product. I'll edit the question. $\endgroup$ – Brendan McKay Feb 15 '14 at 1:10
  • $\begingroup$ In my previous comment I meant $H$ to be the subgroup $S_n$, not $C_2^n$. Sorry. $\endgroup$ – Jeremy Rickard Feb 15 '14 at 2:48

The stabilizer of a partition in $C_2 \wr S_n$ is a subgroup $S_n$ complementing the base group. So, we can attack the problem computationally by looking at the permutation action of $C_2 \wr S_n$ on the $2^n$ cosets of this subgroup. You are looking for its minimal transitive subgroups or, more specifically, for its regular subgroups.

I tried this quickly (in Magma) and for $n=4$ I found a couple of transitive examples of order $2^n$, one of which was

$\langle (1, 2)(5, 6), (1, 2)(3, 4)(5, 6)(7, 8), (1, 6, 2, 5)(3, 7, 4, 8), (1, 4, 6, 8, 2, 3, 5, 7) \rangle$.

Then, for $n=8$, I found the transitive example of order $2^n$:

$\langle (3, 4)(5, 6)(7, 8)(15, 16), (1, 12)(2, 11)(3, 14)(4, 13)(5, 10, 6, 9)(7, 15, 8, 16), (1, 15)(2, 16)(3, 5)(4, 6)(7, 11, 8, 12)(9, 14, 10, 13), (1, 2)(3, 4)(5, 6)(15, 16), (5, 6)(7, 8)(9, 10)(15, 16), (11, 12)(15, 16), (1, 13, 15, 9, 2, 14, 16, 10)(3, 8, 6, 11)(4, 7, 5, 12), (1, 2)(3, 4)(5, 6)(7, 8)(9, 10)(11, 12)(13, 14)(15, 16) \rangle$.

That is far as I could get by just asking for all regular subgroups, but it looks as though there might be transitive examples of degree $2^k$ for all $k$.

  • $\begingroup$ That's great, Derek. I'm guessing that looking at these examples carefully will indicate the generalization. $\endgroup$ – Brendan McKay Feb 16 '14 at 7:03
  • $\begingroup$ These groups answer the problem I asked, but when I tried them in my application they didn't give anything new. The reason is that any graph with these groups as automorphisms also has all the transpositions $(x_i\,y_i)$ as automorphisms. This happens because for all $i,j$, the four pairs $\lbrace x_i,y_i\rbrace$, $\lbrace x_i,y_j\rbrace$, $\lbrace x_j,y_i\rbrace$, $\lbrace x_j,y_j\rbrace$ are equivalent. $\endgroup$ – Brendan McKay Feb 19 '14 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.