Mark's Research

I work in the Department of Mathematics at the University of Manchester, in the north-west of England. I am affiliated to the Algebra Group and the the Tropical Mathematics Group.

By original training I'm both a mathematician and a computer scientist and I've worked at various points on the spectrum between the two subjects, but my interests over the last few years have drifted more towards the mathematical side. The main focus of my research is the theory of semigroups and automata, which I view as two aspects of the same subject (an automaton being essentially a semigroup action). However, I spend much of my time working on connections with adjacent fields and application areas, such as combinatorial and geometric group theory, and most recently tropical algebra and geometry.

Some of the major topics on which I have recently worked include:

• Geometry of Finitely Generated Semigroups. It is well known that finitely generated groups admit a natural geometric structure (the word metric), which encapsulates many important aspects of their algebraic structure. Conventional geometry is ill-equipped to model semigroups in the same way, because a lack of inverses means that the distance between two elements can depend upon the direction of travel. Indeed, the presence of ideals means that elements can even be at finite distance in one direction and "distance infinity" in the other. This research asks: to what extent can geometric methods be used to study semigroups, when one allows "metrics" which are asymmetric and admit distance infinity? Robert Gray and I have shown that foundational results of geometric group theory, such as the Svarc-Milnor Lemma, have analogues in this setting, and we are hopeful that more advanced techniques will also transfer. Conversely, it is self-evident that "asymmetric" distance spaces arise with great frequency in nature, and hence in applications of mathematics. Think, just for one example, of the effort required to travel between two points in mountainous terrain. We believe that semigroup-theoretic methods have the potential to assist with the study of these spaces, in the same way that group-theoretic methods have been applied in geometry.


• Tropical Matrix Semigroups. Matrices over the tropical semifield (the real numbers equipped with operations of addition and maximum) arise naturally in a huge range of application areas, including automata theory, combinatorial optimisation and scheduling, phylogenetics and enumerative algebraic geometry. I aim to understand the algebraic structure of these matrices under multiplication, which turns out to be very closely bound up with the geometry of tropical convex sets and polytopes. For example, Zur Izhakian, Marianne Johnson and I have shown that the von Neumann regular matrices are exactly those whose row space is a polytope of pure dimension equal to row and column rank of the matrix. It follows that almost all of the numerous notions of rank which have been studied for tropical matrices coincide in the case of regular matrices. This research was funded first by CICADA and then by EPSRC grant EP/H000801/1, and parts of it are joint work with people including Peter Fenner, Christopher Hollings, Zur Izhakian, Marianne Johnson, Matthew Taylor and David Wilding.


• Tropical Semigroup Representations Many of the most important infinite semigroups (such as the ubiquitous bicyclic monoid) do not admit faithful finite dimensional representations over fields. The main obstruction is the strong notion of rank for matrices over fields and, perhaps ironically, the lack of a single satisfactory notion of rank over the tropical semifield makes it a natural candidate as a carrier for representations of these semigroups. In essence, the tropical semifield is badly-behaved enough that we can represent badly-behaved semigroups over it, but well-understood enough that we can hope to understand those semigroups through the resulting representations. For example, Laure Daviaud, Marianne Johnson and I have shown that the bicyclic monoid satisfies exactly the same identities as the monoid of \( 2 \times 2 \) upper triangular tropical matrices; this answers a question of Izhakian and Margolis, and leads to an efficient algorithm for checking identities in the bicyclic monoid. Marianne and I have also established the existence of faithful tropical representations for plactic monoids, which directly answers a question of Izhakian, and also establishes a conjecture of Kubat and Okniński stating that plactic monoids satisfy non-trivial semigroup identities.


• Small Overlap Monoids. Small overlap conditions are combinatorial restrictions on finite presentations for monoids, which limit the complexity of derivation sequences between equivalent words. They are the semigroup analogue of the small cancellation conditions used in geometric group theory. Small overlap monoids are the "generic" finitely presented monoids, in the sense that a randomly chosen \( a \)-generator, \( k \)-relation monoid presentation of size \( n \) satisfies any given small overlap condition with probability which converges exponentially fast to \( 1 \) as \( n \) grows. I developed a new combinatorial approach to these monoids which seems particularly useful for algorithmic and automata-theoretic purposes, yielding for example a linear time uniform algorithm for the word problem monoids given by C(4) presentations, and an extension of Kleene's theorem to these monoids. These have been implemented in a GAP package.