Bases of schurian antisymmetric coherent configurations and isomorphism test for schurian tournaments

I. N. Ponomarenko

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 108-147

Résumé

It is known that for any permutation group $G$ of odd order there exists a subset of the permuted set whose stabilizer in $G$ is trivial, and if $G$ is primitive, then there also exists a base of size at most 3. These results are generalized to the coherent configuration of $G$, that is in this case schurian and antisymmetric. This enables us to construct a polynomial-time algorithm for recognizing and isomorphism testing of schurian tournaments (i.e., arc colored tournaments the coherent configurations of which are schurian).

Bibliographie

[1] S. Evdokimov, I. Ponomarenko, “O primitivnykh kletochnykh algebrakh”, Zap. nauchn. semin. POMI, 256, 1999, 38–68 | MR | Zbl

[2] S. Evdokimov, I. Ponomarenko, “Kharakterizatsiya tsiklotomicheskikh skhem i normalnye koltsa Shura nad tsiklicheskoi gruppoi”, Algebra i analiz, 14:2 (2002), 11–55 | MR | Zbl

[3] S. Evdokimov, I. Ponomarenko, “Raspoznavanie i proverka izomorfizma tsirkulyantnykh grafov za polinomialnoe vremya”, Algebra i analiz, 15:6 (2003), 1–34 | MR | Zbl

[4] V. Arvind, B. Das, P. Mukhopadhyay, “Isomorphism and canonization of tournaments and hypertournaments”, J. Computer and System Sciences, 76 (2010), 509–523 | DOI | MR | Zbl

[5] L. Babai, “On the order of uniprimitive permutation groups”, Ann. Math., 113 (1981), 553–568 | DOI | MR | Zbl

[6] L. Babai, E. M. Luks, “Canonical labeling of graphs”, Proc. 15th ACM STOC, 1983, 171–183

[7] R. F. Bailey, P. J. Cameron, “Base size, metric dimension and other invariants of groups and graphs”, Bull. London Math. Soc., 43 (2011), 209–242 | DOI | MR | Zbl

[8] S. Evdokimov, I. Ponomarenko, “On highly closed cellular algebras and highly closed isomorphisms”, Electr. J. Combin., 6 (1999), # R18, 31 pp. | MR | Zbl

[9] S. Evdokimov, I. Ponomarenko, “Two-closure of odd permutation group in polynomial time”, Discr. Math., 235:1–3 (2001), 221–232 | DOI | MR | Zbl

[10] S. Evdokimov, I. Ponomarenko, “Permutation group approach to association schemes”, European J. Combin., 30:6 (2009), 1456–1476 | DOI | MR | Zbl

[11] S. Evdokimov, I. Ponomarenko, G. Tinhofer, “Forestal algebras and algebraic forests (on a new class of weakly compact graphs)”, Discr. Math., 225 (2000), 149–172 | DOI | MR | Zbl

[12] A. Espuelas, “Regular orbits on symplectic modules”, J. Algebra, 138 (1991), 1–12 | DOI | MR | Zbl

[13] A. Espuelas, “Large character degrees of groups of odd order”, Illinois J. Math., 35 (1991), 499–505 | MR | Zbl

[14] The GAP Group, GAP-4-Groups, Algorithms, and Programming, Version 4.4.5, 2005 http://www.gap-system.org

[15] D. Gluck, “Trivial set-stabilizers in finite permutation groups”, Can. J. Math., 35 (1983), 59–67 | DOI | MR | Zbl

[16] G. A. Jones, M. Klin, Y. Moshe, “Primitivity of Permutation Groups, Coherent Algebras and Matrices”, J. Combin. Theory Ser. A, 98 (2002), 210–217 | DOI | MR | Zbl

[17] O. Manz, T. Wolf, Representations of solvable groups, London Math. Soc. Lect. Note Ser., 185, Cambridge Univ. Press, Cambridge, 1993 | MR | Zbl

[18] M. Muzychuk, I. Ponomarenko, “On Pseudocyclic Association Schemes”, Ars Math. Contemporanea, 5:1 (2012), 1–25 | MR | Zbl

[19] A. Seress, “The minimal base size of primitive solvable permutation groups”, J. London Math. Soc., 53 (1996), 243–255 | DOI | MR | Zbl

[20] A. Seress, Permutation Group Algorithms, Cambridge Univ. Press, 2002 | MR | Zbl

[21] D. A. Suprunenko, Matrix Groups, Amer. Math. Soc., Providence, RI, 1976 | MR | Zbl

[22] Yong Yang, “Regular orbits of finite primitive solvable groups”, J. Algebra, 323 (2010), 2735–2755 | DOI | MR | Zbl

[23] B. Weisfeiler (editor), On construction and identification of graphs, Springer Lect. Notes, 558, 1976 | MR | Zbl

[24] P.-H. Zieschang, Theory of Association Schemes, Springer, Berlin–Heidelberg, 2005 | MR | Zbl