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.

Bibliographie

[1] G. Sabidussi, “On a class of fixed-point-free graphs”, Proc. Amer. Math. Soc., 9:5 (1958), 800–804 | DOI | MR | Zbl

[2] G. Sabidussi, “Vertex-transitive graphs”, Monatsh. Math., 68:5 (1964), 426–438 | DOI | MR | Zbl

[3] M. Krasner, “Une generalisation de la notion de corps”, J. Math. pure et Appl., 17 (1938), 367 | Zbl

[4] H. Wielandt, Permutation groups throught invariant relations and invariant functions, Ohio State Univ., 1969

[5] L. A. Kaluzhnin, M. Kh. Klin, “O nekotorykh maksimalnykh podgruppakh simmetricheskikh i znakoperemennykh grupp”, Matem. sb., 87(129) (1972), 91–121 | MR | Zbl

[6] R. I. Tyshkevich, Zh.-A. Amidi, “Gruppy podstanovok i invariantnye otnosheniya”, Vestsi AN BSSR, seriya fiz.-matem. navuk, 1973, no. 4, 17–27 | Zbl

[7] E. G. Davydov, “O konechnykh grafakh i ikh avtomorfizmakh”, Problemy kibernetiki, 1966, no. 17, 27–39 | MR | Zbl

[8] C.-Y. Chao, “On groups and graphs”, Trans. Amer. Math. Soc., 118:6 (1965), 488–497 | DOI | MR | Zbl

[9] J. Turner, “Point-symmetric graphs with a prime number of points”, J. Combin. Theory, 3 (1967), 136–145 | DOI | MR | Zbl

[10] C.-Y. Chao, “On the classification of symmetric graphs with a prime number of vertices”, Trans. Amer. Math. Soc., 158:1 (1971), 247–256 | DOI | MR | Zbl

[11] J. L. Berrgren, “An algebraic characterisation of symmetric graphs with a prime number of vertices”, Bull. Austral. Math. Soc., 7:1 (1972), 131–134 | DOI | MR

[12] J. L. Berrgren, “On algebraic characterisation of finite symmetric tournaments”, Bull. Austral. Math. Soc., 6:1 (1972), 53–59 | DOI | MR

[13] Annie Astie, “Groups d'automorphismes des Tournois sommetsymetric d'ordre premier et denombement de ces tournois”, C. r. Acad. scient. Paris, ser. A, 275:3 (1972), 167–169 | MR | Zbl

[14] C.-Y. Chao, Wells Jacqueline G., “A class of vertex-transitive digraphs”, J. Combin. Theory, 14:3 (1973), 246–255 | DOI | MR | Zbl

[15] M. Kholl, Teoriya grupp, IL, Moskva, 1962

[16] Zh.-P. Serr, “Derevya, amalgamy i $SL_2$”, Matematika, 18:1 (1974), 3–51 | Zbl

[17] D. A. Suprunenko, Gruppy matrits, izd-vo «Nauka», Moskva, 1972 | MR

[18] H. Wielandt, Finite permutation groups, Acad. press, New York–London, 1964 | MR | Zbl

[19] B. Huppert, “Zweifach transitive, auflösbare Gruppen”, Math. Z., 68 (1957), 126–150 | DOI | MR | Zbl

[20] W. Burnside, Theory of groups of finite order, 1911

[21] F. Kharari, Teoriya grafov, izd-vo «Mir», Moskva, 1973 | MR

[22] R. I. Tyshkevich, V. Z. Feinberg, “O perestanovochnosti preobrazovanii, I”, Vestsi AN BSSR, seriya fiz.-matem. navuk, 1971, no. 2, 5–13 | MR | Zbl

[23] R. I. Tyshkevich, V. Z. Feinberg, “O perestanovochnosti preobrazovanii, II”, Vestsi AN BSSR, seriya fiz.-matem. navuk, 1971, no. 4, 11–18