Projects / Programmes
Semiregular elements in 2-closures of solvable groups
| Code |
Science |
Field |
Subfield |
| 1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
| Code |
Science |
Field |
| P001 |
Natural sciences and mathematics |
Mathematics |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
semiregular element, 2-clouser, solvable group, simultaneous conjugacy problem, cryptography
Researchers (12)
Organisations (3)
Abstract
Let G be a permutation group on a finite set V. A non-identity element of G is semiregular if the subgroup of G generated by this element has all orbits of equal length. It is known that every finite transitive permutation group contains a fixed-point-free element of prime power order, but not necessarily a fixed-point-free element of prime order, that is, a semiregular element of prime order. A permutation group with no semiregular elements of prime order is sometimes called elusive, which is equivalent to requiring that it does not contain semiregular elements at all.
One would expect “nice” combinatorial objects, for example graphs, to have non-elusive automorphism groups. Indeed, the problem first arose in a graph-theoretic context in 1981 when the PI asked if every vertex-transitive digraph has a semiregular automorphism. The now commonly accepted, and more general, version of this question (known as the Polycirculant conjecture) involves the whole class of 2-closed transitive groups and is due to Klin.
Usually, when dealing with problems in algebraic graph theory, and more specifically transitive group actions on graphs, the hardest part is the non-solvable case, with the solvable case allowing at least some partial results. With the semiregularity problem, however, the situation is completely reversed. It is the class of solvable groups that presents the main obstacle to obtaining a complete solution. The proposed project aims to make further steps towards complete solution of the semiregularity problem with special emphasis given to transitive solvable groups. As a starting point we will consider two special cases that have remained open despite the fact that several attempts have been made towards finding a solution. First, knowing that transitive permutation groups of square-free degree are non-elusive, the next natural step is to consider transitive permutation groups of cube-free degree. As for the second case, we impose valency restrictions on the graphs in question. Knowing that cubic and quartic vertex-transitive graphs admit semiregular automorphisms, the next step is to consider graphs of valency 5.
On the other hand, semiregular automorphisms will be used to contribute to other active topics of research in algebraic graph theory and beyond. In particular, the proposed project will also address a connection that went by unnoticed and lies at the intersection of discrete mathematics and the theory of computation: given two arrays of elements in a group, decide whether there exists an element of the group that simultaneously conjugates the two arrays. The problem is known as the simultaneous conjugacy problem. One of the goals of the proposed project is to develop efficient algorithms for solving the simultaneous conjugacy problem in the symmetric group, and to find non-trivial lower bounds for this problem. It is natural to consider this problem in the framework of the proposed project as the Sridhar’s algorithm for solving the simultaneous conjugacy problem does not work in the case when every permutation in each of the arrays
is semiregular.
Significance for science
One of the core concepts essential to understanding natural phenomena and the dynamics of social systems is the concept of “relation”. Human friendships, social and interconnection networks, traffic systems, chemical structures, etc. can be expressed as relational structures. Furthermore, scientists rely on relational structures with high levels of symmetry because of their optimal behavior and high performance. A mathematical model capturing the essence of this situation is a graph exhibiting a high level of symmetry, and the underlying mathematical discipline is algebraic graph theory which is the discipline considered in this proposal. Algebraic graph theory is a part of discrete mathematics involving a wide range of methods from combinatorics, linear algebra, permutation groups, group representations, association schemes, algorithms, geometry, topology, etc. While some symmetries are obvious, certain additional symmetries remain hidden or difficult to grasp. Knowing the full (or as near as possible) set of symmetries of an object is important because it provides the most complete description of that object's structure.
Mathematics has been called the “invisible oil” which keeps our technological society running efficiently. There is a common misunderstanding that technology has solved all our problems. For example, that the availability of powerful computer packages means that users do not require mathematical skills. This is simply untrue. More mathematically and statistically trained young people are needed to use new technology successfully and efficiently. The proposed project is going to spread this message effectively.
Significance for the country
One of the core concepts essential to understanding natural phenomena and the dynamics of social systems is the concept of “relation”. Human friendships, social and interconnection networks, traffic systems, chemical structures, etc. can be expressed as relational structures. Furthermore, scientists rely on relational structures with high levels of symmetry because of their optimal behavior and high performance. A mathematical model capturing the essence of this situation is a graph exhibiting a high level of symmetry, and the underlying mathematical discipline is algebraic graph theory which is the discipline considered in this proposal. Algebraic graph theory is a part of discrete mathematics involving a wide range of methods from combinatorics, linear algebra, permutation groups, group representations, association schemes, algorithms, geometry, topology, etc. While some symmetries are obvious, certain additional symmetries remain hidden or difficult to grasp. Knowing the full (or as near as possible) set of symmetries of an object is important because it provides the most complete description of that object's structure.
Mathematics has been called the “invisible oil” which keeps our technological society running efficiently. There is a common misunderstanding that technology has solved all our problems. For example, that the availability of powerful computer packages means that users do not require mathematical skills. This is simply untrue. More mathematically and statistically trained young people are needed to use new technology successfully and efficiently. The proposed project is going to spread this message effectively.
Most important scientific results
Interim report
Most important socioeconomically and culturally relevant results
Interim report
