Seminar Archive

Semester 1 programme, Session 2023-24

Thursday 14th September 2023: Jack Allsop (Monash University)

Row-Hamiltonian Latin squares and perfect 1-factorisations

Abstract: A Latin square of order n is an n x n matrix of n symbols, such that each symbol occurs exactly once in each row and column. Let L be a Latin square of order n. Each pair of distinct rows of L forms a 2-line permutation. If this permutation is a single n-cycle, for any choice of rows, then L is called row-Hamiltonian. Each Latin square has six conjugate Latin squares, obtained by uniformly permuting the coordinates of its (row, column, symbol) triples. Let \nu(L) denote the number of conjugates of L which are row-Hamiltonian. It is known that \nu(L) \in \{0, 2, 4, 6\} and for each m \in \{0, 2, 6\} there are known infinite families of Latin squares with \nu = m. We construct the first known infinite family of Latin squares with \nu=4.

A 1-factorisation of a graph is a partition of its edge set into 1-factors. A 1-factorisation is perfect if the union of edges in any pair of its 1-factors forms a Hamiltonian cycle. A perfect 1-factorisation of the complete bipartite graph K_{n, n} is equivalent to a row-Hamiltonian Latin square of order n. Our family of Latin squares with \nu=4 allows us to build the eighth known infinite family of perfect 1-factorisations of complete bipartite graphs.

Thursday 28th September 2023: Rosemary Bailey (St Andrews)

Designs on strongly regular graphs

Abstract: I will talk about experiments where each treatment is applied to some of the vertices of a strongly regular graph. The corresponding Bose-Mesner algebra has three common eigenspaces. I assume that these are also the eigenspaces of the variance-covariance matrix of the responses on the vertices.

There are two (conflicting!) desirable properties of the design that do not depend on the eigenvalues of this matrix. I will describe both of these in the context of two familiar strongly regular graphs.

Thursday 12th October 2023: Scott Harper (St Andrews)

Bases and generating sets for finite groups

Abstract: A base for a permutation group is a set of points whose pointwise stabiliser is trivial. This is a classical notion that plays an important role in computational group theory. It is also a subject where much recent progress has occurred (including by several in this research group!) I will discuss two recent instances of results on bases for primitive permutation groups leading to new results on generating sets for abstract groups. There will be lots of examples.

Thursday 26th October 2023: Bromlyn Cameron (St Andrews)

Transition chains and Thompson’s groups

Abstract: In the 1960s R. Thompson defined a family of three finitely presented groups of homeomorphisms of the Cantor set. Two of these groups, T and V, were the first known examples of finitely presented infinite simple groups. We are interested in the other group – Thompson’s group F – and more specifically groups of PL_+(I) homeomorphisms which do not contain an isomorphic copy of F. In this talk we will introduce transition chains and discuss their place in the study of F-less groups of homeomorphisms.

Thursday 9th November 2023: Florent Hivert (University Paris-Saclay / Orsay)

Diagrammatic for Okada monoid and algebra

Abstract: It is well known that the Young lattice is the Bratelli diagram of thesymmetric groups expressing how irreducible representations restrict from S_Nto S_{N-1}. In 1975, Stanley discovered a similar lattice called theYoung-Fibonacci lattice which was realized as the Bratelli diagram of a family ofalgebras by Okada in 1994. In this talk we will present a combinatorial modelfor the Okada algebra and the associated monoid using a labeled version of thearc diagrams of the Jones monoid and the Temperley-Lieb algebra. We prove thatthe cardinality of the Okada monoid and dimension of the Okada algebra is n!in full generality (it was only proven in the semisimple case by Okada). Inparticular, we interpret the natural bijection between permutations andlabeled arc diagrams as an instance of the Robinson-Schensted-Fomincorrespondence associated to the Young-Fibonacci lattice. This has a lots ofalgebraic consequences: the aperiodicity of the Okada monoid and its Greenrelations as well as the cellularity of the Okada algebra. (Joint work with Jeanne Scott.)

Thursday 23rd November 2023: Reinis Cirpons (St Andrews)

Computing in Free Bands

Abstract: A band is a semigroup whose elements are all idempotent. Perhaps surprisingly, it turns out that all finitely generated bands are finite. Despite this, existing methods for computing with finite or finitely generated semigroups, such as the Todd-Coxeter and Knuth-Bendix algorithms, are inefficient or inapplicable to bands. In this talk we will focus on the special case of free bands and showcase a way of solving the word problem and computing minimal representatives by using coloured binary trees.

Semester 2 programme:

Week 1 – Thursday 18th January 2024: Peter Cameron (St Andrews)

Covers of sets of groups

Abstract: Let S be a set of finite groups. A cover of S is a finite group G containing a copy of each group in S; it is minimal if no proper subgroup of G is an S-cover, and minimum if no S-cover has smaller order than G. The topic was suggested to me by Hamid Reza Dorbidi from Jiroft. Subsequently David Craven (Birmingham) and Benjamin Sambale (Heidelberg) have contributed. But many open problems remain. I will talk about a few of the results and problems, including the following.

We can describe completely the smallest abelian group containing a given set of abelian groups; but we do not know whether it is the minimum cover.
The set of groups of order 4 has only finitely many minimal covers, but the set of groups of order 8 has infinitely many.
A minimum cover of a set of two non-abelian simple groups is either their direct product or a simple group.

Week 3 – Thursday 1st February 2024: Louis Theran (St Andrews)

Title: Orthogonal representations of graphs revisited

Abstract: An orthogonal representation (OR) of a graph G with n vertices is a configuration of n vectors in a d-dimensional inner product space so that the vectors associated with vertices i and j are orthogonal whenever {i, j} is not an edge of G. ORs, and their general position counterparts, GORs were introduced by Lovász to study the Shannon capacity of a graph, but they have many other applications. I’ll discuss some of these (old and new), and, time permitting, an algebra-geometric approach to constructing a GOR.

Week 5 – Thursday 15th February 2024: Jung Won Cho/Pierre Zhou

Title (Jung Won Cho): Non-finitely presented semigroups

Abstract: In 1975, B.M. Schein proved that free inverse semigroups are not finitely presentable as semigroups. Motivated by this result, we will characterise finite presentability of subsemigroups of the monogenic free inverse semigroup. We will also see how Schein’s transformations can be used to answer James East and Carl-Fredrik Nyberg-Brodda’s question on whether a free regular *-semigroup is finitely presentable.

Title (Pierre Zhou): Determine the atomicity of a family of finitely based permutation classes

Abstract: Permutations, when interpreted as models of some first-order theory whose signature consists of two linear orders, are very often viewed as words, hence can be partially ordered by some arguably ‘natural’ subword involvement (or, containment) order. The downward closed sets of permutations under this particular order are called permutation classes. A permutation class is said to be atomic if it cannot be written as the union of two proper subclasses. Model-theoretically, this is equivalent to having the so-called joint embedding property (JEP). In this talk, we will determine the atomicity of a family of finitely based permutation classes by first inspecting a concrete introductory example. Then, after a quick detour into the notion of symmetries, we shall be able to prove that every member of this family is atomic by showing that the image of each class under the described symmetries has the joint embedding property. This result is part of a work-in-progress classification theorem.

Week 7 – Thursday 7th March 2024: Tom Coleman (St Andrews)

Title: Group-embeddable monoids and graphs

Abstract: Frucht’s theorem states that every finite group arises as the automorphism group of some simple undirected graph. Generalizations have been made in a number of different directions; both in the nature of the algebraic object on one side and the combinatorial object on the other. For instance, any monoid arises as the endomorphism monoid of some graph, and any finite group arises as the automorphism group of a strongly regular graph. In particular, de Groot and Sabidussi independently proved that any group (not necessarily finite) arises as the automorphism group of a graph.

If a monoid is group-embeddable, then it can be embedded in some symmetric group and viewed as a monoid of permutations. A permutation on the vertices of a graph G may preserve edges but not non-edges; this is known as a bimorphism of G. In this talk, we will demonstrate that every group-embeddable monoid arises as the bimorphism monoid of some graph, generalising the result of de Groot/Sabidussi. This is the result of joint work with Isaac Dilley.

Week 9 – Thursday 21st March 2024: Pilar Duque Paez/Joseph Edwards (St Andrews)

Title (Pilar Duque Paez): The embedding of certain linear and abelian groups in finitely presented simple groups

Abstract: In 1984 Elizabeth A. Scott defined a method for constructing finitely presented infinite simple groups. As a consequence of her construction, it was shown that GL(n, Z), the group of nxn matrices with integer entries and determinant 1 or -1, embeds in the group of automorphisms of the m-ary tree, Aut(T_m). This is a much-cited result of Brunner and Sidki from 1998. In this talk, we will give a brief description of Scott’s construction, resulting in the embedding of certain linear and abelian groups in finitely presented simple groups.

Title (Joseph Edwards): Solving the Word Problem: Modern Data Structures for the Knuth-Bendix Procedure

Abstract: In 1970, Knuth and Bendix devised an algorithm for “term rewriting systems” that can decide when two terms composed of variables and operators are equal, given a set of rewriting rules. Fifteen years later, Kapur and Narendran applied this algorithm to string rewriting systems, proving several results regarding the existence, uniqueness, and usefulness of such systems. In this talk, we discuss how string rewriting systems can sometimes be used to solve the word problem for semigroups, and investigate how the classical Knuth-Bendix algorithm can be improved by taking advantage of modern data structures.

EXTRA SEMINAR! Note non-standard day and venue (Maths Lecture Theatre C)

Week 10 – Tuesday 26th March 2024, 1-2pm: David Beers (Oxford)

Title: Level Sets of Persistent Homology for Point Clouds

Abstract: Persistent homology is an operation which takes as input a point cloud and returns a collection of intervals, in an attempt to capture the topology of the space the point cloud was sampled from. How descriptive is this operation? We address this question by studying the dimension of the level sets of the persistence map. In particular, we discuss upper and lower bounds for this dimension and describe connections to rigidity theory. No background in homology theory will be assumed.

Week 11 – Thursday 4th April 2024: Dorte Behrens/ Murray Whyte (St Andrews)

Title (Dorte Behrens): Homogeneous oriented two-graphs

Abstract: In 1954 Fraïssé wrote his theorem on amalgamation classes and the existence of a homogeneous structure that forms their limit. Since then classifications of the homogeneous graphs (Lachlan & Woodrow, 1980), digraps (Cherlin, 1998) 3-hypergraphs (Lachlan & Akhtar, 1995) and others have followed. In this talk we will be considering the homogeneous oriented two-graphs.

Title (Murray Whyte): Short presentations for transformation monoids

Abstract: Many widely-loved transformation monoids, such as the full transformation, symmetric inverse and partial transformation monoids, contain a copy of the symmetric group of the same (here, finite) degree; any presentation for one of these monoids contains a presentation for such a symmetric group, plus a collection of additional defining relations. We’re interested in finding small presentations for these monoids ‘modulo the symmetric group’. In other words, we ask what the minimum number of these additional defining relations is, over all possible presentations of our considered monoids.

I’ll exhibit what I understand to be the smallest-known presentations for these monoids with respect to the number of additional relations — in other words, finding upper bounds in response to this question. I’ll also discuss the pursuit of lower bounds: considering what any collection of these additional relations must be able to ‘do’, so as to conclude there must be a certain number of them in any presentation.

Week 12 – Monday 8th April 2024, 4-5pm: Charles Cox (Bristol)

Title: Wreath products and invariable generation

Abstract: We’ll begin with a gentle introduction to
(1) a wreath product, and
(2) the concept of a group having an invariable generating set.
By mostly working with well-known or concrete examples (based in some way on the integers). There are then two proofs, whose basic ideas I’ll aim to capture for an audience new to both (1) and (2). I hope to illustrate where the proofs have come from and why they are natural.

Week 3 – Thursday 3rd October 2024: Nik Ruskuc (St Andrews)

Title: Heights of congruence lattices of semigroups

Abstract: The height of a (finite) poset P is the size of a maximum chain in P. Cameron,
Solomon and Turull (1989) showed that the height of the subgroup lattice of the
symmetric group S_n is given by \lceil 3n/2 \rceil – b(n), where b(n) is the number
of 1s in the binary expansion of n. The analogue of S_n for semigroups is the full
transformation semigroup T_n. Cameron, Gadoleau, Mitchell and Perese (2017)
established an accurate asymptotic formula for the height of the subsemigroup lattice
of T_n. But the subgroup lattice of a group G can be viewed from a different angle:
it is (isomorphic to) the lattice of right (or left) congruences of G. (And one-sided
congruences of a monoid are in a 1-1 correspondence with cyclic transformation
representations of S.) In this talk I will introduce a general method which gives a
lower bound for the height of the lattices of one- or two-sided congruences of an
arbitrary semigroup, and under certain additional conditions gives the exact values.
I will apply this theory to obtain the height for the lattices of right and left
congruences of T_n, as well as for many other natural semigroups of transformations,
partitions and matrices. This is joint work with Matthew Brookes, James East, Craig
Miller and James Mitchell.

Week 5 – Thursday 17th October 2024: Rosemary Bailey and Peter Cameron (St Andrews)

Title: Permutation groups, lattices and orthogonal block structures

Abstract: (Joint work with Marina Anagnstopoulou-Merkouri (Bristol))

The story began when Marina was doing a STARIS undergraduate research internship with Peter. We were studying transitive but imprimitive permutation groups through their invariant equivalence relations, and were looking at the case where the equivalence relations commute; in room 317, Rosemary overheard our conversation, and said, “Statisticians know about those things; we call them orthogonal block structures”.

An orthogonal block structure is a lattice of commuting uniform equivalence relations. These are combinatorial objects which may have trivial automorphism group. We will discuss the history of how they arose in experimental design.

A better behaved special case occurs when the lattice is distributive; these are called poset block structures. They always have a large automorphism group, a generalised wreath product of symmetric groups, described by a poset with a set attached at each of its points. Our main results are a proof that a group preserving a poset block structure is contained in a generalised wreath product of permutation groups defined from the action (an extension of the Krasner–Kaloujnine theorem), and that a generalised wreath product over a poset is the intersection of the iterated wreath products of the same groups over all linear extensions of the poset.

Week 8 – Thursday 7th November 2024: Giusi Capobianco (Roma Tor Vergata, visiting St Andrews)

Title: Hyperelliptic double covers of metric graphs

Abstract: In tropical geometry, graphs and metric graphs serve as the foundational objects of study, representing the combinatorial and geometric properties of algebraic varieties in a piecewise linear setting. Among these, hyperelliptic graphs form a distinguished class due to their structure, characterized by the presence of an involution called the hyperelliptic involution such that its quotient is a tree. Another example of map between two metric graphs is the covering map, which is an isometry of the corresponding metric spaces. In this talk I will focus on the double covers with no fixed points and explain a new construction of hyperelliptic double covers, as well as the computation on the total number of such covers, which is part of the joint work with Yoav Len on the Abel-Prym map. As result, the study of tropical double covers provides valuable insights into the classical theory of double covers of smooth algebraic curves and I will give some examples to highlight these connections and their implications.

Week 10 – Thursday 21st November 2024: Reinis Cirpons (St Andrews)

Title: Minimum degree transformation representations of diagram monoids

Abstract: A transformation representation of a monoid M is an embedding of M into a full transformation monoid. Cayley’s theorem establishes that a transformation representation always exists. Given this, it is only natural to ask what the smallest such representation is. In other words, what is the minimum number N such that the monoid M embeds into the full transformation monoid of degree N? The answer is known for certain special families of semigroups such as the inverse semigroups, rectangular bands and Rhodes semisimple semigroups, yet there is no general-purpose method for determining the minimum transformation degree of an arbitrary monoid. The equivalent question for groups is well studied, but certain difficulties arise when trying to apply methods from group theory to the monoid case.

In recent joint work with James East and James Mitchell we obtain exact formulas for the minimum transformation degrees of several families of finite diagram monoids, including the partition, Brauer, Temperley–Lieb and Motzkin monoids. In this talk I will give an overview of the theory of transformation representations with an emphasis on the similarities and differences to the group case, outline our proofs and results for diagram monoids and showcase some difficulties in generalizing to larger classes of monoids.