ICMS 2024 - Durham - Software for the applications of group theory to combinatorics - Session 3

Anton Betten, Leonard Soicher

Go to the Main Sessions Page
Session Chairs: Anton Betten (Kuwait University), Leonard Soicher (Queen Mary University of London)
Many combinatorial search and classification problems are computationally very challenging. It can be extremely helpful to use computational group theoretic techniques to exploit any symmetry in the problem as well as any possible symmetry in a solution. Such approaches must balance the group theoretic aspects and the combinatorial aspects. The fields we have in mind range from finite geometry to graph theory to design theory to coding theory and beyond. The session is about the software aspects of work in this field. Our goal is not so much to collect mathematical results, but rather to discuss the challenges along the way to finding new such results. We are interested in highlighting the challenges in the field of software development. Are there any new approaches? Are there new ways to use existing software? What languages are used successfully? Are there any new packages or systems? Are there any interesting new applications of group-theoretic or other algebraic techniques?


Session 1, MCS3052
Monday, 10:30 Alfred Wassermann
Monday, 11:00 Sacha Kurz
Monday, 11:30 Markus Anders
Monday, 12:00 Morgan Rodgers
Session 2, MCS3052
Monday, 13:30 Rhys Evans
Monday, 14:00 Bart de Bruyn
Monday, 14:30 Joel Barraza Nava
Monday, 15:00 Anton Betten
Session 3, MCS3052
Monday, 16:00 Leonard Soicher
Monday, 16:30 Discussion

  1. Speaker: Alfred Wassermann (University of Bayreuth, Germany)
    Search for combinatorial objects using lattice algorithms - new developments
    In 1986, Kreher and Radziszowski first used the famous LLL algorithm to construct combinatorial designs. Subsequently, lattice algorithms have been applied to construct a large variety of objects in design theory, coding theory and finite geometry. The author's software "solvediophant" uses lattice basis reduction, followed an exhaustive enumeration of those lattice points, to determine all solutions of a system of Diophantine linear equations. This has proven useful to construct combinatorial designs of strength 7, 8, and 9, many subspace designs, and various other record breaking combinatorial structures. In many successful cases, this solving algorithm had been combined with the strategy to prescribe a group of automorphisms on the structures to be constructed.
    Recently, the algorithm could be improved on various levels, e.g. a new enumeration strategy based on "limited discrepancy search" was implemented to speed up the search for a first solution. In this talk, we will describe the search strategy based on lattice basis reduction and outline the recent progress.
  2. Speaker: Sascha Kurz (University of Bayreuth, Germany)
    Title: Computer classification of linear codes
    Linear codes play a central role in coding theory and have applications in several branches of mathematics. For error correction purposes the minimum Hamming distance should be as large as possible. One way to consider minimal linear codes is to impose a restricted ratio on the minimum and the maximum weight. Linear codes related to applications in Galois Geometry often require a certain divisibility of the occurring weights. In this talk we present a software package for the classification of linear codes over finite fields with restricted sets of weights. The underlying algorithms are based on lattice point enumeration.
  3. Speaker: Markus Anders (TU-Darmstadt, Germany)
    Title: Fast Probabilistic Symmetry Detection on Graphs
    The use of symmetry has a dramatic impact on the efficiency of algorithms in various fields. Before symmetries of a structure can be utilized, one first has to have the algorithmic means to find them. Typically, this is achieved through modeling said structure as a graph, followed by an application of a practical graph isomorphism solver such as nauty, saucy, bliss, Traces, or dejavu.
    In this talk, I will give a brief overview of recent progress made on graph isomorphism solvers, in particular regarding the computation of automorphism groups of graphs. I will discuss the probabilistic search as well as other implementation strategies used by the dejavu solver.
  4. Speaker: Morgan Rodgers (RPTU Kaiserslautern-Landau, Germany)
    Title: Computing double coset representatives in OSCAR using subgroup ladders
    In group theory, a double coset is an orbit of group elements under the action of two subgroups, one acting on the left and one acting on the right. More specifically, if H and K are subgroups of G, a double coset takes the form HgK = hgk : h in H, k in K for some fixed g in G. Double cosets are an important algebraic tool for counting isomorphism classes of many types of combinatorial objects. They also arise in many important problems in representation theory, functional analysis, and algebraic number theory.
    In this talk, we will describe an algorithm for computed representative elements of double cosets due to Bernd Schmalz. This method is known as the "Leiterspiel" (ladder game) and is based on finding sequences of subgroups in which the subgroup index of consecutive groups in the sequence is small; finding "good" ladders starting with G and ending with K lead to efficient calculations of the desired double coset representatives. We will show an implementation of this algorithm in the OSCAR Computer Algebra System, and look at some applications to some classification problems involving graphs and combinatorial designs.
  5. Speaker: Rhys Evans (Institute of Mathematics, Physics and Mechanics, Slovenia)
    Title: Enumerating graphs with symmetry properties
    Collections of small mathematical objects are often used in the forming and testing of new conjectures, and can also provide counterexamples to other open problems. Due to the number of labelled graphs of a fixed order and the complexity of the graph isomorphism problem, the enumeration of graph isomorphism classes is infeasible for all but very small orders. However, we are interested in certain classes of graphs which have nice symmetry properties. By using the extra structure found in their automorphism groups, we can often characterise such graphs and significantly extend their enumeration to much larger orders.
    In this talk I will introduce certain classes of graphs having a given symmetry property, and present the current status of their enumeration for small orders. I will also mention what results and methods are used in their enumeration, and a GAP package we are developing to make the resulting collections of graphs available to a wider audience.
    This is joint work with Katja Bercic, Antonio Montero, Primoz Potocnik and Janos Vidali.
  6. Speaker: Bart De Bruyn (Ghent University, Belgium)
    Title: Divisible design graphs from the symplectic graph Sp(4,q)
    A regular graph is called a divisible design graph if the set of vertices can be partitioned into subsets of the same size such that any two distinct vertices belonging to the same subset have a constant number of common neighbours and any two vertices belonging to distinct subsets also have a (possibly distinct) constant number of common neighbours.
    We construct new examples of divisible design graphs related to the symplectic graph Sp(4,q) whose vertices are the points of a 3-dimensional finite projective space, where two vertices are adjacent whenever the line connecting them is totally isotropic with respect to a given symplectic polarity. Several examples of divisible design graphs can be constructed from a special spread of Sp(4,q), q odd. This is a partition of the vertex set of Sp(4,q) in induced subgraphs isomorphic to the complete bipartite graph Kq+1,q+1.
    We construct an infinite family of such special spreads, and classify them, up to isomorphism, for q at most 7. We discuss the computational challenges we faced during the process for q=7 and explain how we were able to solve these.
    This is joint work with Sergey Goryainov, Willem Haemers and Leonid Shalaginov.
  7. Speaker: Joel Barraza Nava (Colorado State University, CO, USA)
    Title: Enumerating Double-Sixes with Orbiter
    An approach to the classification of cubic surfaces with 27 lines is through the classical theory of double-sixes. A double-six determines a unique cubic surface while a cubic surface contains 36 double-sixes. Thus, we classify cubic surfaces by classifying double-sixes. In order to classify double-sixes we consider the substructure of (5+1)-configurations. That is, a set of 5 pairwise skew lines with a common transversal such that any 4 lines of the 5 pairwise skew lines have a unique transversal distinct from the transversal of the 5 lines. To classify cubic surfaces we use Orbiter, a C++ class library devoted to the classification of combinatorial objects.
  8. Speaker: Anton Betten (Kuwait University, Kuwait)
    Title: Computing the Group of an Algebraic Variety over a Finite Field
    Algebraic varieties over finite fields are important objects. Here we are interested in the following two problems:
    (a) Computing their automorphism group and
    (b) Classification up to isomorphism.
    We will utilize combinatorial tools such as canonical forms for graphs. But the problem is different from the set-stabilizer problem, because the action on equations is different from the action on points. Our solution is implemented in the computer algebra system Orbiter, which is devoted to the study of combinatorial objects. Relations to other computer algebra systems are explored.
  9. Speaker: Leonard Soicher (Queen Mary University of London)
    Title: Software for proper vertex-colouring exploiting graph symmetry
    GAP is a large open-source system for discrete mathematics, with an emphasis on computational group theory. GRAPE is a GAP package for efficiently storing and computing with graphs together with associated groups of automorphisms, and is designed for applications in algebraic graph theory, permutation group theory, design theory, and finite geometry. This talk will focus on the current functionality in GRAPE for proper vertex-colouring, including the calculation of the chromatic number of a graph, which exploits the automorphism group of that graph.

File translated from TEX by TTH, version 4.08.
On 16 Jun 2024, 07:48.