RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2012 Volume 402, Pages 108–147 (Mi znsl5241)

This article is cited in 7 papers

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

I. N. Ponomarenko

St. Petersburg Department of Steklov Mathematical Institute RAS, St. Petersburg, Russia

Abstract: 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).

Key words and phrases: coherent configuration, linear group, wreath product, the Weisfeiler–Leman algorithm.

UDC: 512.542.7+519.14+510.52

Received: 07.05.2012

Language: English


 English version:
Journal of Mathematical Sciences (New York), 2013, 192:3, 316–338

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025