|
Zapiski Nauchnykh Seminarov POMI, 2012, Volume 402, Pages 108–147
(Mi znsl5241)
|
|
|
|
This article is cited in 7 scientific papers (total 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.
Received: 07.05.2012
Citation:
I. N. Ponomarenko, “Bases of schurian antisymmetric coherent configurations and isomorphism test for schurian tournaments”, Combinatorics and graph theory. Part IV, RuFiDiM'11, Zap. Nauchn. Sem. POMI, 402, POMI, St. Petersburg, 2012, 108–147; J. Math. Sci. (N. Y.), 192:3 (2013), 316–338
Linking options:
https://www.mathnet.ru/eng/znsl5241 https://www.mathnet.ru/eng/znsl/v402/p108
|
Statistics & downloads: |
Abstract page: | 249 | Full-text PDF : | 67 | References: | 66 |
|