Bases of Schurian antisymmetric coherent configurations and an isomorphism test for Schurian tournaments

DOI10.1007/S10958-013-1398-2zbMATH Open1282.05225arXiv1108.5645OpenAlexW2053664971MaRDI QIDQ376133FDOQ376133

Authors: Ilya Ponomarenko 

Publication date: 4 November 2013

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Abstract: It is known that for any permutation group $G$ of odd order one can find a subset of the permuted set whose stabilizer in $G$ is trivial, and if $G$ is primitive, then also a base of size at most 3. Both of these results are generalized to the coherent configuration of $G$ (that is in this case a schurian antisymmetric coherent configuration). 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).

Full work available at URL: https://arxiv.org/abs/1108.5645

Recommendations

• Polynomial time recognition and isomorphism testing for cyclic tournaments
• Permutation group approach to association schemes
• Bases for primitive permutation groups and a conjecture of Babai
• Faster canonical forms for primitive coherent configurations (extended abstract)
• Finding a cycle base of a permutation group in polynomial time

zbMATH Keywords

polynomial-time algorithmprimitive permutation groupscoherent configurationsSchurian configurations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Association schemes, strongly regular graphs (05E30) Primitive groups (20B15)

Cites Work

• Title not available (Why is that?)
• Base size, metric dimension and other invariants of groups and graphs
• Title not available (Why is that?)
• The Minimal Base Size of Primitive Solvable Permutation Groups
• Permutation group approach to association schemes
• On the order of uniprimitive permutation groups
• Large character degrees of groups of odd order
• On pseudocyclic association schemes
• Title not available (Why is that?)
• Regular orbits on symplectic modules
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On highly closed cellular algebras and highly closed isomorphisms
• Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
• Primitivity of permutation groups, coherent algebras and matrices
• Title not available (Why is that?)
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Trivial Set-Stabilizers in Finite Permutation Groups
• Two-closure of odd permutation group in polynomial time
• On primitive cellular algebras
• Regular orbits of finite primitive solvable groups
• Isomorphism and canonization of tournaments and hypertournaments

Cited In (7)

• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• Regular orbits of finite primitive solvable groups. III
• Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
• Regular orbits of finite primitive solvable groups, the final classification
• Every 4-equivalenced association scheme is Frobenius
• On Schur 2-groups
• Cartan coherent configurations

Uses Software

• GAP

This page was built for publication: Bases of Schurian antisymmetric coherent configurations and an isomorphism test for Schurian tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q376133)