Let $G$ be a transitive group on $\Omega$. Every orbits of $G$ on its natural action on $\Omega\times\Omega$ is called an orbital of $G$ on $\Omega$. For each orbital $\Delta$ of $G$ on $\Omega$, the orbital digraph $Graph(\Delta)$ is a digraph with vertex set $\Omega$ and edge set $\Delta$. Clearly, $G$ is a subgroup of automorphism group of $Graph(\Delta)$. Is there any paper or book that determine for which groups $G$, there is an orbital $\Delta$ that $G$ is equal to the automorphism group of $Graph(\Delta)$? Clearly, the action of $S_5$ on 2-subets of $\{1,\ldots,5\}$ is an example.


The property of $G$ you are looking at is called 2-closure, i.e., you ask for a classification of 2-closed permutation groups. See the paper by Liebeck, Praeger, Saxl, On the 2-closures of finite permutation groups. J. London Math. Soc. (2) 37 (1988), no. 2, 241–252, where this question is investigated for a particular class of primitive permutation groups.

More precisely, this is not 100% equivalent to your question (it would be, if you allowed graphs have coloured arcs), as there exist 2-closed permutation groups $G$ such that for each orbital the automorphism group of the underlying (di)graph is strictly bigger than $G$.

In general such a classification is not known, and the problem is hopelessly hard, I think.

  • 1
    $\begingroup$ @Dima: Couldn't it be true that $G$ is 2-closed, but is not the full automorphism group of one of its orbitals? But I cannot think of any better reference, and I agree with your assessment of the difficulty. $\endgroup$ – Chris Godsil Jan 1 '13 at 17:41
  • $\begingroup$ Thanks for the reference. The thesis of Jing Xu, On closure of finite permutation groups, The university of Western Australia, 2005, is another good reference. $\endgroup$ – majid arezoomand Jan 2 '13 at 7:39
  • $\begingroup$ @Chris: you are right, automorphism groups of association schemes corresponding to mutually orthogonal Latin squares (take the set of Latin squares corresponding to a Desarguesian finite affine plane) provide examples of this phenomenon. $\endgroup$ – Dima Pasechnik Jan 2 '13 at 14:11

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.