BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mark Kambites

Mark Kambites appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.RAmath.GRmath.AGmath.COComputational ComplexityFormal Languages and Automata Theorymath.DSmath.MG

Catalog footprint

What is connected

21works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

21 published item(s)

preprint2021arXiv

Permutability of Matrices over Bipotent Semirings

We study permutability properties of matrix semigroups over commutative bipotent semirings (of which the best-known example is the tropical semiring). We prove that every such semigroup is weakly permutable (a result previous stated in the literature, but with an erroneous proof) and then proceed to study in depth the question of when they are strongly permutable (which turns out to depend heavily on the semiring). Along the way we classify monogenic bipotent semirings and describe all isomorphisms between truncated tropical semirings.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Identities in Upper Triangular Tropical Matrix Semigroups and the Bicyclic Monoid

We establish necessary and sufficient conditions for a semigroup identity to hold in the monoid of $n\times n$ upper triangular tropical matrices, in terms of equivalence of certain tropical polynomials. This leads to an algorithm for checking whether such an identity holds, in time polynomial in the length of the identity and size of the alphabet. It also allows us to answer a question of Izhakian and Margolis, by showing that the identities which hold in the monoid of $2\times 2$ upper triangular tropical matrices are exactly the same as those which hold in the bicyclic monoid. Our results extend to a broader class of "chain structured tropical matrix semigroups"; we exhibit a faithful representation of the free monogenic inverse semigroup within such a semigroup, which leads also to a representation by $3\times 3$ upper triangular matrix semigroups, and a new proof of the fact that this semigroup satisfies the same identities as the bicyclic monoid.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Linear functions preserving Green's relations over fields

We study linear functions on the space of $n \times n$ matrices over a field which preserve or strongly preserve each of Green's equivalence relations ($\mathcal{L}$, $\mathcal{R}$, $\mathcal{H}$ and $\mathcal{J}$) and the corresponding pre-orders. For each of these relations we are able to completely describe all preservers over an algebraically closed field (or more generally, a field in which every polynomial of degree $n$ has a root), and all strong preservers and bijective preservers over any field. Over a general field, the non-zero $\mathcal{J}$-preservers are all bijective and coincide with the bijective rank-$1$ preservers, while the non-zero $\mathcal{H}$-preservers turn out to be exactly the invertibility preservers, which are known. The $\mathcal{L}$- and $\mathcal{R}$-preservers over a field with "few roots" seem harder to describe: we give a family of examples showing that they can be quite wild.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Face monoid actions and tropical hyperplane arrangements

We study the combinatorics of tropical hyperplane arrangements, and their relationship to (classical) hyperplane face monoids. We show that the refinement operation on the faces of a tropical hyperplane arrangement, introduced by Ardila and Develin in their definition of a tropical oriented matroid, induces an action of the hyperplane face monoid of the classical braid arrangement on the arrangement, and hence on a number of interesting related structures. Along the way, we introduce a new characterization of the types (in the sense of Develin and Sturmfels) of points with respect to a tropical hyperplane arrangement, in terms of partial bijections which attain permanents of submatrices of a matrix which naturally encodes the arrangement.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

NP-completeness in the gossip monoid

Gossip monoids form an algebraic model of networks with exclusive, transient connections in which nodes, when they form a connection, exchange all known information. They also arise naturally in pure mathematics, as the monoids generated by the set of all equivalence relations on a given finite set under relational composition. We prove that a number of important decision problems for these monoids (including the membership problem, and hence the problem of deciding whether a given state of knowledge can arise in a network of the kind under consideration) are NP-complete. As well as being of interest in their own right, these results shed light on the apparent difficulty of establishing the cardinalities of the gossip monoids: a problem which has attracted some attention in the last few years.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Pure Dimension and Projectivity of Tropical Polytopes

We study how geometric properties of tropical convex sets and polytopes, which are of interest in many application areas, manifest themselves in their algebraic structure as modules over the tropical semiring. Our main results establish a close connection between pure dimension of tropical convex sets, and projectivity (in the sense of ring theory). These results lead to a geometric understanding of idempotency for tropical matrices. As well as their direct interest, our results suggest that there is substantial scope to apply ideas and techniques from abstract algebra (in particular, ring theory) in tropical geometry.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Amenability and geometry of semigroups

We study the connection between amenability, Følner conditions and the geometry of finitely generated semigroups. Using results of Klawe, we show that within an extremely broad class of semigroups (encompassing all groups, left cancellative semigroups, finite semigroups, compact topological semigroups, inverse semigroups, regular semigroups, commutative semigroups and semigroups with a left, right or two-sided zero element), left amenability coincides with the strong Følner condition. Within the same class, we show that a finitely generated semigroup of subexponential growth is left amenable if and only if it is left reversible. We show that the (weak) Følner condition is a left quasi-isometry invariant of finitely generated semigroups, and hence that left amenability is a left quasi-isometry invariant of left cancellative semigroups. We also give a new characterisation of the strong Følner condition, in terms of the existence of weak Følner sets satisfying a local injectivity condition on the relevant translation action of the semigroup.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A large class of sofic monoids

We prove that a monoid is sofic, in the sense recently introduced by Ceccherini-Silberstein and Coornaert, whenever the J-class of the identity is a sofic group, and the quotients of this group by orbit stabilisers in the rest of the monoid are amenable. In particular, this shows that the following are all sofic: cancellative monoids with amenable group of units; monoids with sofic group of units and finitely many non-units; and monoids with amenable Schutzenberger groups and finitely many L-classes in each D-class. This provides a very wide range of sofic monoids, subsuming most known examples (with the notable exception of locally residually finite monoids). We conclude by discussing some aspects of the definition, and posing some questions for future research.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A strong geometric hyperbolicity property for directed graphs and monoids

We introduce and study a strong "thin triangle"' condition for directed graphs, which generalises the usual notion of hyperbolicity for a metric space. We prove that finitely generated left cancellative monoids whose right Cayley graphs satisfy this condition must be finitely presented with polynomial Dehn functions, and hence word problems in NP. Under the additional assumption of right cancellativity (or in some cases the weaker condition of bounded indegree), they also admit algorithms for more fundamentally semigroup-theoretic decision problems such as Green's relations L, R, J, D and the corresponding pre-orders. In contrast, we exhibit a right cancellative (but not left cancellative) finitely generated monoid (in fact, an infinite class of them) whose Cayley graph is a essentially a tree (hence hyperbolic in our sense and probably any reasonable sense), but which is not even recursively presentable. This seems to be strong evidence that no geometric notion of hyperbolicity will be strong enough to yield much information about finitely generated monoids in absolute generality.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Convexity of tropical polytopes

We study the relationship between min-plus, max-plus and Euclidean convexity for subsets of $\mathbb{R}^n$. We introduce a construction which associates to any max-plus convex set with compact projectivisation a canonical matrix called its dominator. The dominator is a Kleene star whose max-plus column space is the min-plus convex hull of the original set. We apply this to show that a set which is any two of (i) a max-plus polytope, (ii) a min-plus polytope and (iii) a Euclidean polytope must also be the third. In particular, these results answer a question of Sergeev, Schneider and Butkovic and show that row spaces of tropical Kleene star matrices are exactly the "polytropes" studied by Joswig and Kulas.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Anisimov's Theorem for inverse semigroups

The idempotent problem of a finitely generated inverse semigroup is the formal language of all words over the generators representing idempotent elements. This note proves that a finitely generated inverse semigroup with regular idempotent problem is necessarily finite. This answers a question of Gilbert and Noonan Heale, and establishes a generalisation to inverse semigroups of Anisimov's Theorem for groups.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Exact rings and semirings

We introduce and study an abstract class of semirings, which we call exact semirings, defined by a Hahn-Banach-type separation property on modules. Our motivation comes from the tropical semiring, and in particular a desire to understand the often surprising extent to which it behaves like a field. The definition of exactness abstracts an elementary property of fields and the tropical semiring, which we believe is fundamental to explaining this similarity. The class of exact semirings turns out to include many other important examples of both rings (proper quotients of principal ideal domains, matrix rings and finite group rings over these and over fields), and semirings (the Boolean semiring, generalisations of the tropical semiring, matrix semirings and group semirings over these).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The word problem for free adequate semigroups

We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute normal forms in each of these, and hence also to test whether any given identity holds in the classes of left, right and/or two-sided adequate semigroups.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Green's J-order and the rank of tropical matrices

We study Green's J-order and J-equivalence for the semigroup of all n-by-n matrices over the tropical semiring. We give an exact characterisation of the J-order, in terms of morphisms between tropical convex sets. We establish connections between the J-order, isometries of tropical convex sets, and various notions of rank for tropical matrices. We also study the relationship between the relations J and D; Izhakian and Margolis have observed that $D \neq J$ for the semigroup of all 3-by-3 matrices over the tropical semiring with $-\infty$, but in contrast, we show that $D = J$ for all full matrix semigroups over the finitary tropical semiring.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Idempotent tropical matrices and finite metric spaces

There is a well known correspondence between the triangle inequality for a distance function on a finite set, and idempotency of an associated matrix over the tropical semiring. Recent research has shed new light on the structure (algebraic, combinatorial and geometric) of tropical idempotents, and in this paper we explore the consequences of this for the metric geometry of tropical polytopes. We prove, for example, that every n-point metric space is realised by the Hilbert projective metric on the vertices of a pure n-dimensional tropical polytope in tropical n-space. More generally, every n-point asymmetric distance function is realised by a residuation operator on the vertices of such a polytope. In the symmetric case, we show that the maximal group of tropical matrices containing the idempotent associated to a metric space is a direct product of the real numbers with the isometry group of the space; it follows that every direct product of a finite group with the real numbers arises as a maximal subgroup of a sufficiently large finitary full tropical matrix semigroup. In the process we also prove some new results about tropical idempotent matrices, and note some semigroup-theoretic consequences which may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quasi-isometry and finite presentations of left cancellative monoids

We show that being finitely presentable and being finitely presentable with solvable word problem are quasi-isometry invariants of finitely generated left cancellative monoids. Our main tool is an elementary, but useful, geometric characterisation of finite presentability for left cancellative monoids. We also give examples to show that this characterisation does not extend to monoids in general, and indeed that properties such as solvable word problem are not isometry invariants for general monoids.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tropical matrix groups

We study the subgroup structure of the semigroup of finitary tropical matrices under multiplication. We show that every maximal subgroup is isomorphic to the full linear automorphism group of a related tropical polytope, and that each of these groups is the direct product of the real numbers with a finite group. We also show that there is a natural and canonical embedding of each full rank maximal subgroup into the group of units of the semigroup of matrices over the tropical semiring with minus infinity. Our results have numerous corollaries, including the fact that every automorphism of a projective (as a module) tropical polytope of full rank extends to an automorphism of the containing space, and that every full rank subgroup has a common eigenvector.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Svarc-Milnor lemma for monoids acting by isometric embeddings

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, partially-defined 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 Svarc-Milnor Lemma to this setting.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Tropical matrix duality and Green's D relation

We give a complete description of Green's D relation for the multiplicative semigroup of all n-by-n tropical matrices. Our main tool is a new variant on the duality between the row and column space of a tropical matrix (studied by Cohen, Gaubert and Quadrat and separately by Develin and Sturmfels). Unlike the existing duality theorems, our version admits a converse, and hence gives a necessary and sufficient condition for two tropical convex sets to be the row and column space of a matrix. We also show that the matrix duality map induces an isometry (with respect to the Hilbert projective metric) between the projective row space and projective column space of any tropical matrix, and establish some foundational results about Green's other relations.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

On groups and counter automata

We study finitely generated groups whose word problems are accepted by counter automata. We show that a group has word problem accepted by a blind n-counter automaton in the sense of Greibach if and only if it is virtually free abelian of rank n; this result, which answers a question of Gilman, is in a very precise sense an abelian analogue of the Muller-Schupp theorem. More generally, if G is a virtually abelian group then every group with word problem recognised by a G-automaton is virtually abelian with growth class bounded above by the growth class of G. We consider also other types of counter automata.

0 citations0 reviewsNo code linkedOpen access