## Past Colloquia

**Automaton semigroups: new examples and non-examples Tara Brough - Thursday, 11 February 2016**

Automaton semigroups are semigroups of endomorphisms of rooted trees generated by the actions of Mealy automata (deterministic synchronous transducers). They act by 'self-similar' endomorphisms, are finitely generated, residually finite and have solvable word problem. Until recently, only one finitely generated residually finite semigroup had been shown not to be an automaton semigroup. I will prove in this talk that no subsemigroup of the natural numbers (under addition) is an automaton semigroup, thus giving an infinite family of new residually finite non-examples. I will also give an overview of some new ways to build automaton semigroups from known examples, using various standard semigroup constructions such as free products, wreath products and strong semilattices. This is joint work with Alan Cain (Universidade Nova de Lisboa).

**Minimal faithful permutation representations of groups David Easdown, University of Sydney - Wednesday, 23 September 2015**

The minimal faithful degree mu(G) of a finite group G is the least nonnegative integer n such that G embeds in the symmetric group on n letters. We sketch a proof of what appears to be the nontrivial fact that mu(G x G)= mu(G) if and only if G is trivial. The proof relies on a theorem of Wright that mu(G x H)=mu(G)+mu(H) if G x H is nilpotent. We also construct a finite group G that does not decompose nontrivially as a direct product, but such that mu(G x H) = mu(G) for an arbitrarily large direct product H of elementary abelian groups (with mixed primes). A simplification of the construction depends on the existence of infinitely many primes that do not have the Mersenne property, which itself appears to be nontrivial, and a consequence of the Green-Tao theorem. (A prime p is Mersenne with respect to an integer q if p = 1+q+...+q^k for some k.)

**Equitable and Fair Colourings of Graphs and Graph Decompositions Chris Rodger, Auburn University (US) - Thursday, 6 August 2015**

It is often useful to partition mathematical objects so that some sort of fair division is the result. In this talk, several notions of fairness will be discussed in the realm of edge-colourings and block-colourings of graph decompositions. In particular, equitable colourings require that at each vertex the colours be shared as evenly as possible among the incident structures (edges or blocks), and some recent results in this area will be presented. Also, fair decompositions attempt to share edges between different elements of a vertex partition of a graph as evenly as possible among the colour classes, and again recent results will be discussed, one of which surprisingly gives rise to symmetric versions of Sudoku squares.

**Selection against off-target ncRNA:mRNA interactions explains protein expression levels Paul Gardner, University of Canterbury (NZ) - Wednesday, 8 July 2015**

That messenger RNA (mRNA) abundances should broadly correlate with protein abundance is a critical assumption in transcriptomics. However, protein and mRNA abundances show low correlation. In principle, much of the variation in protein and mRNA levels should be predictable from genomic sequences. Some variation can be accounted for by mRNA secondary structure and codon usage, both of which influence protein abundance. However, these features only partially explain this discrepancy. Here we present evidence that a third process impacts mRNA translation: interactions between noncoding RNAs and mRNAs. We show that there has been strong selection for avoidance of off-target ncRNA:mRNA interactions across prokaryotes, and that, such interactions have a greater impact on protein abundance than either mRNA secondary structure or codon usage. By generating synonymously variant green fluorescent protein (GFP) mRNAs with different levels of ncRNA:mRNA crosstalk, we show that GFP levels correlate well with modelled protein abundances. Taking crosstalk interactions into account enables precise modulation of protein abundance.

**Solving word equations Murray Elder (University of Newcastle) - Wednesday, 13 May 2015**

**Abstract for first talk: **If I give you two strings of letters (called "words") - abbbaaa and abbaaa - and ask you to decide if they are identical, you can do that pretty easily. Now if I say X, Y are "unknowns" that you are allowed to replace by any words to get identical words in aXXb and YbX, that is a problem. In this case: Y has to start with a, and X has to end with b or be replaced by nothing (you are allowed to do that, a string of length 0). So, for instance, [Y = abb; X = bb] and [Y = a; X = nothing] are solutions. One would like to answer the following questions:

1. In general (for any two words with unknowns of any length), is there a procedure to answer YES or NO if there is any solution?

2. Formulate a procedure (an algorithm) to find all solutions.

3. Express the set of all solutions in some reasonable way, that is, give some systematic description.

1. was answered by Makanin in 1977; before that it was thought maybe the problem was undecidable (meaning that no algorithm exists; there are similar problems which are undecidable), but his answer was really complicated: you couldn't practically use the procedure he described; is was a purely theoretical result.

2. was answered by Razborov in 1980s, building on Makanin's result, so again complicated.

We answered 1,2,3 giving a much simpler algorithm, which runs in very low space complexity (we claim optimal), that is, the amount of computer memory required is as small as you could expect for any algorithm that solves the problem. Makanin-Razborov's solution needed exponential space (which is practically infeasible for a computer). Our description of all solutions is really nice: we give a finite graph that you follow around to produce all solutions. In addition, we really solved a (seemingly harder) problem where the letters a, b, ... have "inverses" a-1, b-1, ... which cancel out: aa-1 -> nothing, and a-1a -> nothing. So, for instance, baa-1a-1b-1bb-1 cancels to ba-1b-1. So the equation aXXb = YbX also has the solution X = b-1Y = ab-1 (and many more). Our proof uses data compression (the same as when you send a file in an email as a zip file to make it smaller), probability and algebra. It builds on previous work by Plandowski, and Jez. This is joint work with Laura Ciobanu, Neuchatel and Volker Diekert, Stuttgart.

**Abstract for second talk: **I will give some details of the proof of our result - that the set of all solutions to an equation over a free group or free monoid has a simple description encoded by a finite graph, that can be constructed in space O(n log n):

- reduction from an equation over a free group to an equation over a free monoid with involution with constraints,

- extended equations and partial commutation,

- construction of the finite graph encoding all solutions,

- two propositions: any path in the graph from an initial to final vertex is a solution; and any solution is realised by a finite path in the graph from an initial to final vertex, - algorithm to prove the second proposition - block and pair compression. This is joint work with Laura Ciobanu, Neuchatel and Volker Diekert, Stuttgart.

**Genome Rearrangements and the Hultman Numbers Pedro Feijao (University of Bielefeld) - Wednesday, 22 April 2015 **

Genomes are subject to mutations and rearrangements in the course of evolution. Large-scale rearrangements can change the number of chromosomes and/or the positions and orientations of large blocks of DNA. A classical problem in comparative genomics is to compute the rearrangement distance, that is, the minimum number of rearrangements required to transform a given genome into another genome. The breakpoint graph is a discrete structure that has proven to be effective in solving

rearrangement distance problems, and the number of cycles in its cycle decomposition is directly related to many rearrangement distances. For a fixed $k$, the number of linear unichromosomal genomes (signed or unsigned) with $n$ elements such that the induced breakpoint graph has $k$ disjoint cycles, known as the Hultman number, has been already determined. In this talk I will show how to extend these results to multichromosomal genomes and discuss how these series can be used to calculate the distribution and expected value of the rearrangement distance between random genomes.

**Symbolic dynamics and Leavitt path algebras Pere Ara (University of Autonoma, Barcelona) - Tuesday, 11 November 2014 **

This is a survey talk, covering the recent new connections between the two topics of symbolic dynamics and Leavitt path algebras.

**Exceptional Quotients of Permutation Groups Neil Saunders (University of Bristol) - Monday, 13 October 2014 **

The minimal permutation degree of a finite group *G* is the smallest non-negative integer *n* such that *G* embeds inside Sym(*n*). This invariant is easy to define but very difficult to calculate in general. Moreover, it doesn't behave well under algebraic constructions such as direct product and homomorphic image. For example, it is possible for the minimal degree of a homomorphic image to be strictly larger than that of the group -- such groups are called 'exceptional'. In this talk, I will describe how this invariant may be calculated by a greedy algorithm for nilpotent groups and report on recent work with Britnell and Skyner on the classification of exceptional groups of order *p*^{5}.

**Matrices that *almost* commute Adam Peder Wie Sørensen (University of Wollongong) - Monday, 25 August 2014 **

In this talk we will look at square matrices A and B that satisfy that AB is close to BA. That is to say, matrices A and B that almost commute. I will explain what it means (to operator algebraists) that two matrices are close. We will look at the questions of whether one can find exactly commuting matrices close to almost commuting ones. We also look at how this question changes if we impose additional conditions on our matrices, say that they are unitary or real or something else.

The question has drawn interest from some mathematicians just because it is a natural question. Lately questions of this form has also drawn interest from physicists due to its application in the field of so-called topological insulators. I will attempt to justify the connection to physics. I will only assume basic knowledge a of linear algebra and little familiarity with continuity.

**An introduction to higher rank graphs and their C*-algebras Alex Kumjian (University of Nevada, Reno) - Tuesday, 19 August 2014 **

Higher rank graphs were introduced more than a decade ago as a generalization of directed graphs for the purpose of enlarging the class of C*-algebras associated to directed graphs. This was inspired by the examples of C*-algebras arising from certain group actions on buildings in the work of Roberts and Steger. We discuss some examples and fundamental properties of higher rank graphs and define the associated C*-algeras. If time permits we will discuss the homology and cohomology theory of these objects.

**When Artin groups are sufficiently large... Sarah Rees (University of Newcastle, UK) - Monday, 14 July 2014 **

The family of Artin groups contains a wide range of groups, including braid groups, free groups, free abelian groups and much else, and its members exhibit a wide range of behaviour. Many problems remain open for the family as a whole, including the word problem, but are solved for particular subfamilies. The groups of finite type (mapping onto finite Coxeter groups), right-angled type (with each m_{ij} ∈ {2, ∞}), large and extra-large type (with each m_{ij} ≥ 3 or 4), FC type (every complete subgraph of the Coxeter graph corresponds to a finite type subgroup) have been particularly studied. After introducing Artin groups and surveying what is known, I will describe recent work with Derek Holt and (sometimes) Laura Ciobanu, Eddy Godelle, dealing with a big collection of Artin groups, containing all the large groups, which we call 'sufficiently large'. For those Artin groups Holt and I have elementary descriptions of the sets of geodesic and shortlex geodesic words, and can reduce any input word to either form. So we can solve the word problem, and prove the groups shortlex automatic. And, following Appel and Schupp we can solve the conjugacy problem in extra-large groups in cubic time. For many of the large Artin groups, including all extra-large groups, Holt, Ciobanu and I can deduce the rapid decay property and verify the Baum- Connes conjecture. And although our methods are quite different from those of Godelle and Dehornoy for spherical-type groups, we can pool our resources and derive a weak form of hyperbolicity for many, many Artin groups. I'll explain some background for the problems we attach, and outline their solution.

**Diagram algebras and representations Peter Jarvis (School of Physical Sciences, University of Tasmania) - Thursday, 27 February 2014 **

An informal introduction to some aspects of matrix groups and their characters, in the context of Schur-Weyl duality, related to recent investigations of an interesting `triapsid' monoid. Joint work with Nick Ham, Des Fitzgerald, Bertfried Fauser and Ronald King.

**Homogenisation for deterministic maps and multiplicative noise Georg Gottwald (University of Sydney) - Monday, 21 October 2013 **

Whereas diffusion limits of stochastic multi-scale systems have a long and successful history, the case of constructing stochastic parameterisations of chaotic deterministic systems has been much less studied. We present rigorous results of convergence of a chaotic slow-fast system to a stochastic differential equation with multiplicative noise. Furthermore we present rigorous results for chaotic slow-fast maps, occurring as numerical discretisations of continuous time systems. This raises the issue of how to interpret certain stochastic integrals; surprisingly the resulting integrals of the stochastic limit system are generically neither of Stratonovich nor of Ito type in the case of maps. It is shown that the limit system of a numerical discretisation is different to the associated continuous time system. This has important consequences when interpreting the statistics of long time simulations of multi-scale systems - they may be very different to the one of the original continuous time system which we set out to study.

**Computing with infinite groups Murray Elder (University of Newcastle) - Monday, 04 November 2013 **

I will talk about two projects. The first is a recently submitted paper on counting the number of words of generators that equal the identity in a group, in this case the Baumslag-Solitar groups. Using some techniques and tricks from enumerative combinatorics and statistical physics, we prove that the generating function Σ* _{n }c_{n}z^{n}* (where

*c*is the number of words of length

_{n}*n*equal to the identity) is D-finite, and find asymptotic growth rates for these numbers. The second is a paper that appeared earlier this year on computing normal forms for group elements in low space complexity. We found many groups for which there is an algorithm that takes input a word in the generators and puts it into a standard (normal) form that runs in logspace. I will give some examples and maybe the audience can add some more. The first part is joint work with Andrew Rechnitzer, Buks van Rensburg, Tom Wong; the second with Gillian Elston and Gretchen Ostheimer.

**Geometric modular representation theory Anthony Henderson (University of Sydney) - Monday, 19 August 2013**

Representation theory is one of the oldest areas of algebra, but many basic questions in it are still unanswered. This is especially true in the modular case, where one considers vector spaces over a field F of positive characteristic; typically, complications arise for particular small values of the characteristic. For example, from a vector space V one can construct the symmetric square S^{2}(V), which is one easy example of a representation of the group GL(V). One would like to say that this representation is irreducible, but that statement is not always true: if F has characteristic 2, there is a nontrivial invariant subspace. Even for GL(V), we do not know the dimensions of all irreducible representations in all characteristics. In this talk, I will introduce some of the main ideas of geometric modular representation theory, a more recent approach which is making progress on some of these old problems. Essentially, the strategy is to re-formulate everything in terms of homology of various topological spaces, where F appears only as the field of coefficients and the spaces themselves are independent of F; thus, the modular anomalies in representation theory arise because homology with modular coefficients is detecting something about the topology that rational coefficients do not.

**Residues and duality in algebraic geometry Amnon Neeman (Australian National University) - Monday, 5 August 2013 **

On a compact Riemann surface the sum of the residues of a meromorphic function must vanish. Starting with this simple observation once can develop an "obstruction theory" to the existence of functions with prescribed local behaviour, and this leads one to several theorems. We will develop the theory starting at an elementary level, but hopefully reach some statements of current research interest.

**Computing with finite semigroups James Mitchell (University of St Andrews) - Friday, 5 July 2013 **

In this talk I will discuss the problem of how to compute a finite semigroup. What does it mean to 'compute' a finite semigroup? It means to find structural information about that semigroup, for example, calculating their Green's classes, size, elements, group of units, minimal ideal, small generating sets, testing membership, finding the inverses of a regular element, factorizing elements over the generators, and so on. I will review what is known about computing with finite semigroups and give an overview of recently developed functionality in the computer algebra system GAP. No prior knowledge of computing or of semigroup theory will be assumed. Time permitting, I will demonstrate the Semigroups software package for computing with semigroups of transformations and partial permutations, and describe some recent theoretical advances that will allow the methods in Semigroups to be applied to several other natural types of semigroup including monoids of partitions.

**The lattice of subsemigroups of the semigroup of all mappings on an infinite set James Mitchell (University of St Andrews) - Friday, 5 July 2013 **

In this talk I will review some recent results relating to the lattice of subgroups of the symmetric group and its semigroup theoretic counterpart, the lattice of subsemigroups of the full transformation semigroup on an infinite set. As might be expected, these lattices are extremely complicated. I will discuss several results that make this comment more precise, and shed light on the maximal proper sub(semi)groups in the lattice. I will also discuss a natural related partial order, introduced by Bergman and Shelah, which is obtained by restricting the type of sub(semi)groups and considering classes of, rather than individual, (semi)groups. In the case of the symmetric group, this order is very simple but in the case of the full transformation semigroup it is again very complex.

**Association and aggregation for contingency table analysis Eric Beh (University of Newcastle) - Monday, 15 April 2013 **

For reasons of confidentiality, government departments and other agencies often release information to the public that has been aggregated. When working with aggregated data it is important to ensure that one keeps in mind any loss of information (due to the aggregation process) when making conclusions at the individual level. There are a variety of techniques that exist which analyse aggregate data and these generally lie within the family of ecological inference techniques. This presentation is not about those techniques. Rather, we shall consider a very simple illustrative example to highlight the loss of information due to aggregation and show how correspondence analysis can be used as a means of visually identifying the source of such loss. This presentation will explore the impact of aggregation using the standard statistical techniques of simple linear regression and the chi-squared test of independence.

**Adventures with group theory: counting and constructing polynomial invariants for applications in quantum entanglement and molecular phylogenetics [or: the Power of Plethysm] Peter Jarvis (University of Tasmania) - Monday, 21 January 2013 **

In many modelling problems in mathematics and physics, a standard challenge is dealing with several repeated instances of a system under study. If linear transformations are involved, then the mathematical machinery of tensor products steps in, and it is the job of group theory to control how the relevant symmetries lift from a single system, to having many copies. At the level of group characters, the construction which does this is called PLETHYSM. In this talk all this will be contextualised via two case studies: entanglement invariants for multipartite quantum systems, and Markov invariants for tree reconstruction in molecular phylogenetics. By the end of the talk, listeners will have understood why Alice, Bob and Charlie love Cayley's hyperdeterminant, and they will know why the three squangles -- polynomial beasts of degree 5 in 256 variables, with a modest 50,000 terms or so -- can tell us a lot about quartet trees!

**Higher homotopy, higher groupoids Steve Lack (Macquarie University) - Monday, 15 October 2012 **

Topology is a branch of geometry in which objects are regarded as being the same if one can be transformed into the other by bending or stretching (tearing and glueing are not allowed). It is sometimes also called "rubber sheet geometry". Homotopy theory is a part of topology in which the geometric objects (called spaces) are studied via algebraic ones, such as groups and groupoids. In this talk, I shall describe groupoids, and how to associate to any space a groupoid, called the fundamental groupoid, which can be seen as measuring the "one-dimensional holes" in the space. I shall then go on to describe higher-dimensional analogues of groupoids, and how they can be used to measure the higher-dimensional holes in spaces.

**The Breaking of JN-25 John Mack (The University of Sydney) - Monday, 20 August 2012 **

JN-25 was the name given by the Allies to the main operational code used by the Imperial Japanese Navy (IJN) during World War II. It was broken into almost immediately after its introduction in mid-1939 by John Tiltman, one of the greatest World War II British code breakers. It continued to be broken throughout the war, and yielded by far the majority of useful signals intelligence regarding IJN operations available to the Allies. At the same time, the Imperial Japanese Army (IJA), using the same cryptographic systems, maintained their security until early 1943, when only one important system was broken. All others defied attack. The talk will describe the coding system used, why the IJN was insecure, and how this was exploited.