Minicourse
Closures of finite permutation groups
Ilia Ponomarenko received the Ph. D. degree in mathematics from St. Petersburg State University, St. Petersburg, Russia, 1986. He is currently a Head of Laboratory of Mathematical Logic and Discrete Mathematics, St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences. His research interests include algebraic combinatorics, permutation group theory and computational complexity.
Andrey Vasil’ev received the Ph. D. degree in mathematics from Sobolev Institute of Mathematics, Novosibirsk, Russia, 1996. He is currently a Chief Research Fellow of the Laboratory of Algebra at Sobolev Institute of Mathematics. His research interests focus mainly on group theory and its applications to various areas of mathematics such as combinatorics and complexity theory.
The course
We start with a discussion on the connection between the graph isomorphism problem and theory of permutation groups. Then we present the basics of Wielandt’s classical theory connecting permutation groups and invariant relations. Within the framework of this theory, we introduce and study m-equivalent groups (i.e., groups with the same set of invariant relations of arity m). The largest group in the class of m-equivalent groups is defined as the m-closure of any of them. In the second part of the mini-course, we will derive formulas for the m-closure of products of permutation groups, anddiscuss the known algorithms for computing the m-closure. In the last lecture, we will make a short overview of the modern theory of closures of permutation groups and present open problems.
Outline:
Lecture 1. Permutation groups and graph isomorphism problem
Lecture 2. Wielandt’s method of invariant relations: the basics
Lecture 3. Products of permutation and matrix groups
Lecture 4. Closures of products of groups
Lecture 5. Classes of groups, invariant with respect to closures I
Lecture 6. Classes of groups, invariant with respect to closures II
Lecture 7. On computing the closures of permutation groups
Lecture 8. New perspectives and open problems
Lectures 1-2, Lectures 3-4, Lectures 5-6, Lectures 7-8
Outline:
Lecture 1. Permutation groups and graph isomorphism problem
Lecture 2. Wielandt’s method of invariant relations: the basics
Lecture 3. Products of permutation and matrix groups
Lecture 4. Closures of products of groups
Lecture 5. Classes of groups, invariant with respect to closures I
Lecture 6. Classes of groups, invariant with respect to closures II
Lecture 7. On computing the closures of permutation groups
Lecture 8. New perspectives and open problems
Lectures 1-2, Lectures 3-4, Lectures 5-6, Lectures 7-8
Bibliography
H. Wielandt, Permutation groups through invariant relations and invariant functions, The Ohio State University, 1969.
I. Ponomarenko and A. Vasil’ev, Two-closure of supersolvable permutation group in polynomial time, Comp. Complexity, 2020 Vol. 29, 5 (33 pages).
I. Ponomarenko and A. Vasil’ev, The closures of wreath products in product action, Algebra and Logic, 2021 Vol. 60, No. 3, 188−195.
E.A. O’Brien, I. Ponomarenko, A.V. Vasil’ev, and E. Vdovin, The 3-closure of a solvable permutation group is solvable, J. Algebra, 2022, Vol. 607, 618−637.
I. Ponomarenko and A. Vasil’ev, On computing the closures of solvable permutation groups, Internat. J. Algebra Comput., 2024 Vol. 34, no. 1, 137−145.
I. Ponomarenko and A. Vasil’ev, Two-closure of supersolvable permutation group in polynomial time, Comp. Complexity, 2020 Vol. 29, 5 (33 pages).
I. Ponomarenko and A. Vasil’ev, The closures of wreath products in product action, Algebra and Logic, 2021 Vol. 60, No. 3, 188−195.
E.A. O’Brien, I. Ponomarenko, A.V. Vasil’ev, and E. Vdovin, The 3-closure of a solvable permutation group is solvable, J. Algebra, 2022, Vol. 607, 618−637.
I. Ponomarenko and A. Vasil’ev, On computing the closures of solvable permutation groups, Internat. J. Algebra Comput., 2024 Vol. 34, no. 1, 137−145.