
Robert Gray's PublicationsMaximal subgroups of free idempotent generated semigroups over the full linear monoid (with I. Dolinka). to appear in Transactions of the American Mathematical Society We show that the rank $r$ component of the free idempotent generated semigroup of the biordered set of the full linear monoid of $n \times n$ matrices over a division ring $Q$ has maximal subgroup isomorphic to the general linear group $GL_r(Q)$, where $n$ and $r$ are positive integers with $r < n/3$. Groups Acting on Semimetric Spaces and Quasiisometries of Monoids (with M. Kambites). to appear in Transactions of the American Mathematical Society We study groups acting by lengthpreserving transformations on spaces equipped with asymmetric, partiallydefined distance functions. We introduce a natural notion of quasiisometry for such spaces and exhibit an extension of the SvarcMilnor Lemma to this setting. Among the most natural examples of these spaces are finitely generated monoids and semigroups and their Cayley and Schützenberger graphs; we apply our results to show a number of important properties of monoids are quasiisometry invariants. Maximal subgroups of free idempotent generated semigroups over the full transformation monoid (with N. Ruskuc). Proceedings of the London Mathematical Society (3) Vol. 104, 2012, pp. 9971018. Let $T_n$ be the full transformation semigroup of all mappings from the set $\{1, \dots, n\}$ to itself under composition. Let $E = E(T_n)$ denote the set of idempotents of $T_n$ and let $e \in E$ be an arbitrary idempotent satisfying $\mathrm{im}(e)=r \leq n2$. We prove that the maximal subgroup of the free idempotent generated semigroup over $E$ containing $e$ is isomorphic to the symmetric group $S_r$. Ideals and finiteness conditions for subsemigroups (with V. Maltcev, J. D. Mitchell and N. Ruskuc). to appear in Glasgow Mathematical Journal In this paper we consider a number of finiteness conditions for semigroups related to their ideal structure, and ask whether such conditions are preserved by sub or supersemigroups with finite Rees or Green index. Specific properties under consideration include stability, $\mathcal{D} = \mathcal{J}$ and minimal conditions on ideals. Homotopy bases and finite derivation type for Schützenberger groups of monoids (with A. Malheiro and S. J. Pride). to appear in Journal of Symbolic Computation Given a finitely presented monoid and a homotopy base for the monoid, and given an arbitrary Schützenberger group of the monoid, the main result of this paper gives a homotopy base, and presentation, for the Schützenberger group. In the case that the $\mathcal{R}$class $R$ of the Schützenberger group $\mathcal{G}(H)$ has only finitely many $\mathcal{H}$classes, and there is an element $s$ of the multiplicative right pointwise stabilizer of $H$, such that under the left action of the monoid on its $\mathcal{R}$classes the intersection of the orbit of the $\mathcal{R}$class of $s$ with the inverse orbit of $R$ is finite, then finiteness of the presentation and of the homotopy base is preserved. On Maximal Subgroups of Free Idempotent Generated Semigroups (with N. Ruskuc) Israel Journal of Mathematics Vol. 189, 2012, pp. 147176. The set of idempotents of an arbitrary semigroup has the structure of a so called biordered set (or regular biordered set in the case of von Neumann regular semigroups). These structures were studied in detail in work of Nambooripad (1979) and Easdown (1985). There is a notion of a free idempotent generated semigroup on a biordered set and it was conjectured by McElwee in 2002 that the maximal subgroups of such a semigroup are all free. The first counterexample to this conjecture was given by Brittenham, Margolis and Meakin (2009), where it was shown that the free abelian group of rank 2 is a maximal subgroup of the free idempotent generated semigroup arising from a certain 72element semigroup. In this article we prove the following results: (1) Every group is a maximal subgroup of some free idempotent generated semigroup. (2) Every finitely presented group is a maximal subgroup of some free idempotent generated semigroup arising from a finite semigroup. (3) Every group is a maximal subgroup of some free regular idempotent generated semigroup. (4) Every finite group is a maximal subgroup of some free regular idempotent generated semigroup arising from a finite regular semigroup. Green Index in Semigroups: Generators, Presentations and Automatic Structures (with A. J. Cain and N. Ruskuc). to appear in Semigroup Forum Let $S$ be a semigroup and let $T$ be a subsemigroup of $S$. Then $T$ acts on $S$ by left and by right multiplication. This gives rise to a partition of the complement $S \setminus T$ and to each equivalence class of this partition we naturally associate a relative Schützenberger group. We show how generating sets for $S$ may be used to obtain generating sets for $T$ and the Schützenberger groups, and vice versa. We also give a method for constructing a presentation for $S$ from given presentations of $T$ and the Schützenberger groups. These results are then used to show that several important properties are preserved when passing to finite Green index subsemigroups or extensions, including: finite generation, solubility of the word problem, growth type, automaticity, finite presentability (for extensions) and finite Malcev presentability (in the case of groupembeddable semigroups). These results provide common generalisations of several classical results from group theory and Rees index results from semigroup theory. Sethomogeneous Directed Graphs (with D. Macpherson, C. Praeger and G. Royle). Journal of Combinatorial Theory, Series B Vol. 102, 2012, pp. 474520. A directed graph is sethomogeneous if, whenever $U$ and $V$ are isomorphic finite subdigraphs, there is an automorphism $g$ of the digraph with $U^g = V$. Here, extending work of Lachlan on finite homogeneous digraphs, we classify finite sethomogeneous digraphs, where we allow some pairs of vertices to have arcs in both directions. Under the assumption that such pairs of vertices are not allowed, we obtain initial results on countably infinite sethomogeneous digraphs, classifying those which are not 2homogeneous. A SvarcMilnor Lemma for Monoids Acting by Isometric Embeddings (with M. Kambites). International Journal of Algebra and Computation Vol. 21, 2011, pp. 11351147. We continue our programme of extending key techniques from geometric group theory to semigroup theory, by studying monoids acting by isometric embeddings on spaces equipped with asymmetric, partiallydefined distance functions. The canonical example of such an action is a cancellative monoid acting by translation on its Cayley graph. Our main result is an extension of the SvarcMilnor Lemma to this setting. Presentations of Inverse Semigroups their Kernels and Extensions (with C. Carvalho and N. Ruskuc). Journal of the Australian Mathematical Society Vol. 90, 2011, pp. 289316. Let $S$ be an inverse semigroup and let $\pi: S \rightarrow T$ be a surjective homomorphism with kernel $K$. We show how to obtain a presentation for $K$ from a given presentation for $S$, and vice versa. We then go on to investigate the relationship between the properties of $S$, $K$ and $T$, focusing mainly on finiteness conditions. In particular we consider finite presentability, solubility of the word problem, residual finiteness, and the homological finiteness property $\mathrm{FP}_n$. Our results extend to inverse semigroups several classical results from combinatorial group theory concerning group extensions. Examples are also provided that highlight the differences with the special case of groups. Homological Finiteness Properties of Monoids, their Ideals and Maximal Subgroups (with S. J. Pride). Journal of Pure and Applied Algebra, Vol. 215, 2011, pp. 30053024. We consider the general question of how the homological finiteness property left${\rm FP}_n$ (resp. right${\rm FP}_n$) holding in a monoid influences, and conversely depends on, the property holding in the substructures of that monoid. This is done by giving methods for constructing free resolutions of substructures from free resolutions of their containing monoids, and vice versa. In particular we show how the property left${\rm FP}_n$ holding in a completely simple semigroup relates to the property holding in its maximal subgroups, and also prove results showing how the property holding in a monoid relates to the property holding in the ideals of that monoid. On properties not inherited by monoids from their Schützenberger groups (with A. Malheiro and S. J. Pride). Information and Computation, Vol. 209, 2011, pp. 11201134. We give an example of a monoid with finitely many left and right ideals, all of whose Schützenberger groups are presentable by finite complete rewriting systems, and so each have finite derivation type, but such that the monoid itself does not have finite derivation type, and therefore does not admit a presentation by a finite complete rewriting system. The example also serves as a counterexample to several other natural questions regarding complete rewriting systems and finite derivation type. Specifically it allows us to construct two finitely generated monoids $M$ and $N$ with isometric Cayley graphs, where $N$ has finite derivation type (respectively, admits a presentation by a finite complete rewriting system) but $M$ does not. This contrasts with the case of finitely generated groups for which finite derivation type is known to be a quasiisometry invariant. The same example is also used to show that neither of these two properties is preserved under finite Green index extensions. Generators and Relations for Subsemigroups via Boundaries in Cayley Graphs (with N. Ruskuc). Journal of Pure and Applied Algebra, Vol. 215, 2011, pp. 27612779. Given a finitely generated semigroup $S$ and subsemigroup $T$ of $S$ we define the notion of the boundary of $T$ in $S$ which, intuitively, describes the position of $T$ inside the left and right Cayley graphs of $S$. We prove that if $S$ is finitely generated and $T$ has a finite boundary in $S$ then $T$ is finitely generated. We also prove that if $S$ is finitely presented and $T$ has a finite boundary in $S$ then $T$ is finitely presented. Several corollaries and examples are given. We also include a corrected proof of a result from an earlier paper showing that finite presentability is inherited by subsemigroups with finite complement. Locallyfinite Connectedhomogeneous Digraphs (with R. Moller). Discrete Mathematics Vol. 311, 2011, pp. 14971517. A digraph is connectedhomogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locallyfinite connectedhomogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of treelike graphs constructed by gluing together directed triangles. In the trianglefree case we show that these digraphs are highly arctransitive. We give a classification in the twoended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connectedhomogeneous digraph, and in the process we obtain a new family of highly arctransitive digraphs without property $Z$. Finite Complete Rewriting Systems for Regular Semigroups (with A. Malheiro). Theoretical Computer Science, Vol. 412, 2011, pp. 654661. It is proved that, given a (von Neumann) regular semigroup with finitely many left and right ideals, if every maximal subgroup is presentable by a finite complete rewriting system, then so is the semigroup. To achieve this, the following two results are proved: the property of being defined by a finite complete rewriting system is preserved when taking an ideal extension by a semigroup defined by a finite complete rewriting system; a completely 0simple semigroup with finitely many left and right ideals admits a presentation by a finite complete rewriting system provided all of its maximal subgroups do. Countable connectedhomogeneous graphs (with D. Macpherson) Journal of Combinatorial Theory, Series B, Vol. 100, 2010, pp. 97118. A graph is connectedhomogeneous if any isomorphism between finite connected induced subgraphs extends to an automorphism of the graph. In this paper we classify the countably infinite connectedhomogeneous graphs. We prove that if $\Gamma$ is connected countably infinite and connectedhomogeneous then $\Gamma$ is isomorphic to one of: Lachlan and Woodrow's ultrahomogeneous graphs; the generic bipartite graph; the bipartite ‘complement of a complete matching’; the line graph of the complete bipartite graph $K_{\aleph_0,\aleph_0}$; or one of the ‘treelike’ distancetransitive graphs $X_{\kappa_1, \kappa_2}$ where $\kappa_1, \kappa_2 \in \mathbb{N} \cup \{ \aleph_0 \}$. It then follows that an arbitrary countably infinite connectedhomogeneous graph is a disjoint union of a finite or countable number of disjoint copies of one of these graphs, or to the disjoint union of countably many copies of a finite connectedhomogeneous graph. The latter were classified by Gardiner (1976). We also classify the countably infinite connectedhomogeneous posets. Cyclefree Partial Orders and Ends of Graphs (with J. K. Truss) Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 146, 2009, pp. 535550. The relationship between posets that are cyclefree and graphs that have more than one end is considered. We show that any locally finite bipartite graph corresponding to a cyclefree partial order has more than one end, by showing a correspondence between the ends of the graph and those of the Hasse graph of its DedekindMacNeille completion. If, in addition, the cyclefree partial order is $k$CStransitive for some $k \geq 3$ we show that the associated graph is endtransitive. Using this approach we go on to prove that, for infinite locally finite $3$CStransitive posets with maximal chains of height $2$, the properties of being crownfree and being cyclefree are equivalent. In contrast to this we show that the nonlocally finite bipartite graphs arising from skeletal cyclefree partial orders each have only one end. We include a corrected proof of a result from an earlier paper on the axiomatizability of the class of cyclefree partial orders.
On Residual Finiteness of Direct Products of Algebraic Systems (with N. Ruskuc)
Monatshefte fur Mathematik, Vol. 158, 2009, pp. 6369. It is well known that if two algebraic structures $\mathbf{A}$ and $\mathbf{B}$ are residually finite then so is their direct product. Here we discuss the converse of this statement. It is of course true if $\mathbf{A}$ and $\mathbf{B}$ contain idempotents, which covers the case of groups, rings, etc. We prove that the converse also holds for semigroups even though they need not have idempotents. We also exhibit three examples which show that the converse does not hold in general. kCStransitive Infinite Graphs Journal of Combinatorial Theory, Series B, Vol. 99, 2009, pp. 378398. A graph $\Gamma$ is $k$CStransitive, for a positive integer $k$, if for any two connected isomorphic induced subgraphs $A$ and $B$ of $\Gamma$, each of size $k$, there is an automorphism of $\Gamma$ taking $A$ to $B$. The graph is called $k$CShomogeneous if any isomorphism between two connected induced subgraphs of size $k$ extends to an automorphism. We consider locallyfinite infinite $k$CShomogeneous and $k$CStransitive graphs. We classify those that are $3$CStransitive (resp. homogeneous) and have more than one end. In particular, the $3$CShomogeneous graphs with more than one end are precisely Macpherson's locally finite distance transitive graphs. The $3$CStransitive but nonhomogeneous graphs come in two classes. The first are line graphs of semiregular trees with valencies $2$ and $m$ (where $m$ is a positive integer), while the second is a class of graphs built up from copies of the complete graph $K_4$, which we describe. Green Index and Finiteness Conditions for Semigroups (with N. Ruskuc) Journal of Algebra, Vol. 320, 2008, pp. 31453164. Let $S$ be a semigroup and let $T$ be a subsemigroup of $S$. Then $T$ acts on $S$ by left and by right multiplication. If the complement $S \setminus T$ has finitely many strong orbits by both these actions we say that $T$ has finite Green index in $S$. This notion of finite index encompasses subgroups of finite index in groups, and also subsemigroups of finite Rees index (complement). Therefore, the question of S and T inheriting various finiteness conditions from each other arises. In this paper we consider and resolve this question for the following finiteness conditions: finiteness, residual finiteness, local finiteness, periodicity, having finitely many right ideals, and having finitely many idempotents. Construction of Some Countable Onearc Transitive Bipartite Graphs (with J. K. Truss) Discrete Mathematics, Vol. 308, 2008, pp. 63926405. We generalize earlier work which gave a method of construction for bipartite graphs which are obtained as the set of maximal or minimal elements of a certain cyclefree partial order. The method is extended here to produce a $1$arctransitive bipartite graph in a ‘free’ way, starting with any partial order with greatest and least element and with instructions on its points about how they will ramify in the extension. A key feature of our work is the interplay between properties of the initial partial order, the extended partial order, and the bipartite graph which results. We also extend the earlier work by giving a complete characterization of all $2$CStransitive cyclefree partial orders. In addition, we discuss the completeness of the constructed partial orders, in the sense of DedekindMacNeille, and remark that the bipartite graph constructed can only be $2$arctransitive in the cyclefree case. Construction of Some Uncountable 2arctransitive Bipartite Graphs (with M. Droste and J. K. Truss) Order, Vol. 25, 2008, pp. 349357. We give various constructions of uncountable arctransitive bipartite graphs employing techniques from partial orders, starting with the cyclefree case, but generalizing to cases where this may be violated. Hall's Condition and Idempotent Rank of Ideals of Endomorphism Monoids Proceedings of the Edinburgh Mathematical Society, Vol. 51, 2008, pp. 116. In 1990, Howie and McFadden showed that every proper twosided ideal of the full transformation monoid $T_n$, the set of all maps from an $n$element set to itself under composition, has a generating set, consisting of idempotents, that is no larger than any other generating set. This fact is a direct consequence of the same property holding in an associated finite 0simple semigroup. We show a correspondence between finite 0simple semigroups that have this property and bipartite graphs that satisfy a condition that is similar to, but slightly stronger than, Hall's condition. The results are applied in order to recover the above result for the full transformation monoid and to prove the analogous result for the proper twosided ideals of the monoid of endomorphisms of a finite vector space. Largest Subsemigroups of the Full Transformation Monoid (with J. D. Mitchell) Discrete Mathematics, Vol. 308, 2008, pp. 48014810. In this paper we are concerned with the following question: for a semigroup $S$, what is the largest size of a subsemigroup $T \leq S$ where $T$ has a given property? The semigroups $S$ that we consider are the full transformation semigroups; all mappings from a finite set to itself under composition of mappings. The subsemigroups $T$ that we consider are of one of the following types: left zero, right zero, completely simple, or inverse. Furthermore, we find the largest size of such subsemigroups $U$ where the least rank of an element in $U$ is specified. Numerous examples are given. Idempotent Rank in Endomorphism Monoids of Finite Independence Algebras Proceedings of the Royal Society of Edinburgh: Section A Mathematics, Vol. 137A, 2007, pp. 303331. By the rank of a monoid we mean the smallest cardinality of a generating set for that monoid, while for an idempotent generated monoid the idempotent rank is defined to be the smallest cardinality of an idempotent generating set for the monoid. In 1992, Fountain and Lewin showed that any proper ideal of an endomorphism monoid of a finite independence algebra is generated by idempotents. In this article the ranks and idempotent ranks of these ideals are determined. In particular, it is shown that when the algebra has dimension greater than or equal to three the idempotent rank equals the rank. Generating Sets of Completely 0Simple Semigroups (with N. Ruskuc) Communications in Algebra, Vol. 33, 2005, pp. 46574678. By the rank of a semigroup we mean the smallest cardinality of a generating set for that monoid. In this paper a formula for the rank of an arbitrary finite completely 0simple semigroup, represented as a Rees matrix semigroup $M^0[G; I, \Lambda; P]$, is given. The result generalizes that of Ruskuc concerning the rank of connected finite completely 0simple semigroups. The rank is expressed in terms of $I$, $\Lambda$, the number of connected components $k$ of $P$, and a number $r_{\mathrm{min}}$, which we define. We go on to show that the number $r_{\mathrm{min}}$ is expressible in terms of a family of subgroups of $G$, the members of which are in onetoone correspondence with, and determined by the nonzero entries of, the components of $P$. A number of applications are given, including a generalization of a result of Gomes and Howie concerning the rank of an arbitrary Brandt semigroup $B(G,\{1, \ \ldots \ ,n\})$.
Submitted Papers




