Algorithmic recognition of actions of 2-homogeneous groups on pairs
Graham R. Sharp
Abstract: We give an algorithm that takes as input a transitive permutation
group $(G, \Omega)$ of degree $n={m\choose 2}$ and decides whether or
not $\Omega$ is $G$-isomorphic to the action of $G$ on the set of
unordered pairs of some set $\Gamma$ on which $G$ acts
2-homogeneously. The algorithm is constructive: if a suitable action
exists then one such will be found, together with a suitable
isomorphism. We give a deterministic $O(sn\log^cn)$ implemention of
the algorithm that assumes advance knowledge of the suborbits of
$(G,\Omega)$. This leads to deterministic $O(I^2)$ and Monte-Carlo
$O(sn\log^cn)$ implementations that do not make this assumption.
|
