Relations admitting a~transitive group of automorphisms

R. I. Tyshkevich

Sbornik. Mathematics, Tome 26 (1975) no. 2, pp. 245-259

Résumé

The concepts of a Cayley relation of arbitrary arity and a quotient relation are defined. Cayley relations are characterized as those relations whose automorphism groups contain regular subgroups. The freedom of Cayley relations is proved: any relation with a transitive automorphism group is isomorphic to a quotient relation of a Cayley relation. Using Cayley relations, two problems are solved: 1) for a given transitive permutation group on a set $V$ to construct all relations on $V$ whose automorphism groups contain it; 2) for a given abstract group $G$ to construct all relations whose automorphism groups contain a transitive subgroup isomorphic to $G$. Cayley relations are used to describe the graphs, digraphs, and tournaments having a transitive automorphism group. A solution is given for a weak variant of a problem of König: what is the nature of a transitive permutation group $G$ if there exists a nontrivial graph whose automorphism group contains $G$? Finally, Cayley relations are used to describe the centralizer of a transitive permutation group in the symmetric group. Bibliography: 23 titles.