MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## automorphism group of orbital graphs

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.

-
@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. – Chris Godsil Jan 1 at 17:41
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. – majid arezoomand Jan 2 at 7:39
@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. – Dima Pasechnik Jan 2 at 14:11