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

Anton Betten, Leonard Soicher

1. Speaker: Sascha Kurz (University of Bayreuth, Germany)
   
   Title: Computer classification of linear codes
   
   Abstract:
   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.
2. Speaker: Markus Anders (TU-Darmstadt, Germany)
   
   Title: Fast Probabilistic Symmetry Detection on Graphs
   
   Abstract:
   
   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.
3. Speaker: Anton Betten (Kuwait University, Kuwait)
   
   Title: Computing the Group of an Algebraic Variety over a Finite Field
   
   Abstract:
   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.
4. Speaker: Leonard Soicher (Queen Mary University of London)
   
   Title: Software for proper vertex-colouring exploiting graph symmetry
   
   Abstract:
   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.
5. Speaker: Alfred Wassermann (University of Bayreuth, Germany)
   
   Title:
   Search for combinatorial objects using lattice algorithms - new developments
   Abstract:
   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.
6. Speaker: Bart De Bruyn (Ghent University, Belgium)
   
   Title: Divisible design graphs from the symplectic graph Sp(4,q)
   
   Abstract:
   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 K_q+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: Morgan Rodgers (RPTU Kaiserslautern-Landau, Germany)
   
   Title: Computing double coset representatives in OSCAR using subgroup ladders
   
   Abstract:
   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.
8. Speaker: Rhys Evans (Institute of Mathematics, Physics and Mechanics, Slovenia)
   
   Title: Enumerating graphs with symmetry properties
   
   Abstract:
   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.
9. Speaker: Joel Barraza Nava (Colorado State University, CO, USA)
   
   Title: Enumerating Double-Sixes with Orbiter
   
   Abstract:
   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.
10. Speaker: Katie Brodhead (Western Carolina University, NC, USA)
    
    Title: Using Algebraic Graph Theory to Partition Data for Deep Learning Prediction Models for Knowledge Graphs
    
    Abstract:
    Machine learning, as an area of computer science, attempts to learn a pattern or labeling system for given set of data, without having the rule for the data programmed ahead of time. We work in the context of supervised learning, the case where some labels are provided for some portion of the data ahead time. We additionally allow for query to a set of points for possible use in a set of training data to be used for learning. Within this context, we apply non-conformity measures to partition data into algebraic structures such as association schemes or coherent configurations. This structure facilitates training in deep learning models for link and edge prediction in knowledge graphs.