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?



Permutation groups transitive on partitions into ordered pairs
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$. 


