Permutation Group Algorithms.

Seress, Ákos.

Permutation Group Algorithms. - 1 online resource (274 pages) - Cambridge Tracts in Mathematics ; v.152 . - Cambridge Tracts in Mathematics .

Cover -- Half-title -- Title -- Copyright -- Contents -- 1 Introduction -- Acknowledgments -- 1.1. List of Algorithms -- 1.2. Notation and Terminology -- 1.2.1. Groups -- 1.2.2. Permutation Groups -- 1.2.3. Algorithmic Concepts -- 1.2.4. Graphs -- 1.3.Classification of Randomized Algorithms -- 2 Black-Box Groups -- 2.1. Closure Algorithms -- 2.1.1. Orbit Computations -- 2.1.2.Closure of Algebraic Structures -- The Closure Algorithm -- Algorithms Based on Normal Closure -- 2.2. Random Elements of Black-Box Groups -- The Product Replacement Algorithm -- 2.3. Random Subproducts -- 2.3.1. Definition and Basic Properties -- 2.3.2. Reducing the Number of Generators -- 2.3.3. Closure Algorithms without Membership Testing -- 2.3.4. Derived and Lower Central Series -- 2.4. Random Prefixes -- 2.4.1. Definition and Basic Properties -- 2.4.2. Applications -- Exercises -- 3 Permutation Groups A Complexity Overview -- 3.1. Polynomial-Time Algorithms -- 3.2. Nearly Linear-Time Algorithms -- 3.3. Non-Polynomial-Time Methods -- 4 Bases and Strong Generating Sets -- 4.1. Basic Definitions -- The Sifting Procedure -- 4.2. The Schreier-Sims Algorithm -- The Schreier-Sims Algorithm -- 4.3. The Power of Randomization -- The Random Schreier-Sims Algorithm -- 4.4. Shallow Schreier Trees -- 4.5. Strong Generators in Nearly Linear Time -- The SGS Construction -- The Algorithm Solving (4.6) -- 4.5.1. Implementation -- Exercises -- 5 Further Low-Level Algorithms -- 5.1. Consequences of the Schreier-Sims Method -- 5.1.1. Pointwise Stabilizers -- 5.1.2. Homomorphisms -- 5.1.3. Transitive Constituent and Block Homomorphisms -- The Block Homomorphism Algorithm -- 5.1.4. Closures and Normal Closures -- 5.2. Working with Base Images -- 5.3. Permutation Groups as Black-Box Groups -- Representation as a Black-Box Group -- 5.4. Base Change. The Exchange of Two Base Points (Deterministic Version) -- The Exchange of Two Base Points (Las Vegas Version) -- Base Change by Conjugation -- 5.5. Blocks of Imprimitivity -- 5.5.1. Blocks in Nearly Linear Time -- 5.5.2. The Smallest Block Containing a Given Subset -- Computation of the Smallest Block Containing… -- 5.5.3. Structure Forests -- Exercises -- 6 A Library of Nearly Linear-Time Algorithms -- 6.1. Special Case of Group Intersection and pplications -- 6.1.1. Intersection with a Normal Closure -- 6.1.2. Centralizer in the Symmetric Group -- 6.1.3. The Center -- 6.1.4. Centralizer of a Normal Subgroup -- 6.1.5. Core of a Subnormal Subgroup -- 6.2. Composition Series -- 6.2.1. Reduction to the Primitive Case -- 6.2.2. The O'Nan-Scott Theorem -- 6.2.3. Normal Subgroups with Nontrivial Centralizer -- Computing the Socle of a Frobenius Group -- Luks's Algorithm -- Neumann's Algorithm (the EARNS Subroutine) -- 6.2.4. Groups with a Unique Nonabelian Minimal Normal Subgroup -- The Algorithm for Case B of Theorem 6.2.7 -- The Algorithm for Case C(i) -- The Algorithm for Case C(ii) -- The Algorithm for Case C(iii) -- 6.2.5. Implementation -- 6.2.6. An Elementary Version -- Beals's Algorithm for Groups with Regular Normal Subgroups -- Beals's Algorithm for Groups with No Regular Normal Subgroups -- 6.2.7. Chief Series -- 6.3. Quotients with Small Permutation Degree -- 6.3.1. Solvable Radical and p-Core -- The Algorithms -- Exercises -- 7 Solvable Permutation Groups -- 7.1. Strong Generators in Solvable Groups -- The Generalized Normal Closure Algorithm -- 7.2. Power-Conjugate Presentations -- Conversion to a pcp -- 7.3. Working with Elementary Abelian Layers -- 7.3.1. Sylow Subgroups -- 7.3.2. Conjugacy Classes in Solvable Groups -- Computation of the Class Representatives -- Computation of the Centralizers -- 7.4. Two Algorithms for Nilpotent Groups. 7.4.1. A Fast Nilpotency Test -- 7.4.2. The Upper Central Series in Nilpotent Groups -- Exercises -- 8 Strong Generating Tests -- 8.1. The Schreier-Todd-Coxeter-Sims Procedure -- 8.1.1. Coset Enumeration -- 8.1.2. Leon's Algorithm -- The STCS Algorithm -- 8.2. Sims's Verify Routine -- The Verify Routine -- 8.3. Toward Strong Generators by a Las Vegas Algorithm -- 8.4. Short Presentation -- 9 Backtrack Methods -- 9.1. Traditional Backtrack -- 9.1.1. Pruning the Search Tree: Problem-Independent Methods -- 9.1.2. Pruning the Search Tree: Problem-Dependent Methods -- 9.2. The Partition Method -- 9.3. Normalizers -- 9.4. Conjugacy Classes -- Class Representatives by Random Sampling -- Representatives in Centralizers of p-Elements -- Separation of the Solvable Radical -- Exercises -- 10 Large-Base Groups -- 10.1. Labeled Branchings -- 10.1.1. Construction -- 10.2. Alternating and Symmetric Groups -- 10.2.1. Number Theoretic and Probabilistic Estimates -- 10.2.2. Constructive Recognition: Finding the New Generators -- 10.2.3. Constructive Recognition: The Homomorphism Lambda -- Summary of the Proof of Theorem 10.2.4(a) -- Proof of Theorem 10.2.4(b) -- 10.2.4. Constructive Recognition: The Case of Giants -- 10.3. A Randomized Strong Generator Construction -- Bibliography -- Index.

Theory of permutation group algorithms for graduates and above. Exercises and hints for implementation throughout.

9781139146166


Permutation groups.


Electronic books.

QA175 .S47 2003

512.2