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

DOI10.1007/S10958-013-1398-2MaRDI QIDQ376133zbMATH OpenOpenAlexFDO

Authors Ilya Ponomarenko

Publication date 4 November 2013

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

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

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)

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

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

Cites work

• scientific article; zbMATH DE number 3496414 (Why is no real title available?)
• scientific article; zbMATH DE number 479556 (Why is no real title available?)
• scientific article; zbMATH DE number 2007658 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• Base size, metric dimension and other invariants of groups and graphs
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
• Isomorphism and canonization of tournaments and hypertournaments
• Large character degrees of groups of odd order
• 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
• On primitive cellular algebras
• On pseudocyclic association schemes
• On the order of uniprimitive permutation groups
• Permutation group approach to association schemes
• Primitivity of permutation groups, coherent algebras and matrices
• Regular orbits of finite primitive solvable groups
• Regular orbits on symplectic modules
• The Minimal Base Size of Primitive Solvable Permutation Groups
• Trivial Set-Stabilizers in Finite Permutation Groups
• Two-closure of odd permutation group in polynomial time

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

Describes a project that uses

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)