Combinatorial optimisation for semigroups

点击翻译按钮获取中文摘要

Semigroups are fundamental algebraic objects. They arise in many areas throughout mathematics and theoretical computer science. While semigroups have a rich theory, the less-rigid structure they have compared to groups makes them more difficult to work with. In fact, a common theme in Computational Semigroup Theory (CST) is considering semigroup problems as a problem in group theory together with a problem in combinatorics. However, the added combinatorial sub-problem can lead to problems for semigroups being much more computationally expensive than the corresponding problems for groups.Combinatorial optimisation is concerned with efficiently finding solutions to combinatorial problems which cannot realistically be found with an exhaustive search. A classic example is the "travelling salesman" problem, which asks for the shortest distance a salesman must travel to visit a number of cities exactly once. For 20 cities, there are over 2 quintillion different possible routes to check, which is unfeasible in any reasonable amount of time. However, far more efficient algorithms exist which can find optimal routes for even much larger numbers of cities. In addition, there are heuristic methods which can find approximate solutions very quickly. Heuristics, approximation, parallelization and reduction of search space through symmetries are examples of techniques from combinatorial optimisation which have applications throughout mathematics and computer science. As many areas can benefit from combinatorial optimisation techniques, general-purpose solvers for combinatorial problems have been developed. However, these solvers are not well-suited to problems in CST, as they cannot efficiently represent certain aspects of the problems. This project will bring the techniques of such solvers to bear on problems in CST. Specific problems in mind include:(Di)graph homomorphisms and endomorphismsTranslations and the translational hull of semigroupsMaximal subsemigroupsMinimal generating sets of semigroupsNormalisers and automorphism groups of semigroupsSemigroup isomorphisms and homomorphismsLattices of congruencesIntersections of subsemigroups and inverse subsemigroupsFor all of the identified problems, theoretical research will lead to practical computer implementations. Completed work will be included in the Semigroups package (J. D. Mitchell and others, 2017) for the free and open source Computational Algebra software GAP (The GAP Group, 2017). Work in development will be available through a hosting service for open source software, GitHub. Algorithms that are performance-critical will be implemented in a standalone C/C++ library, accessible through Python. A recent trend in mathematics has been the use of computational tools to analyse examples in search of theoretical results. For example, researchers may wish to verify a new conjecture on all finite groups less than a certain order. This might not be realistic for a researcher in Semigroup Theory: the number of semigroups of size 10 is a 20-digit number. By providing new and improved tools in CST, and enabling currently-unfeasible computations, this project will open new avenues of mathematical research. J. D. Mitchell and others. (2017). Semigroups - GAP package, Version 3.0.7. doi:10.5281/zenodo.592893The GAP Group. (2017). GAP - Groups, Algorithms, and Programming, Version 4.8.8 (http://www.gap-system.org).