The Margolis-Rhodes Monoid of a Graph
Abstract
We investigate the structural, combinatorial, ideal-theoretic and Krohn-Rhodes complexity of the Margolis-Rhodes monoid, MR(G), of a finite simple graph G, viewed topologically as a 1-dimensional simplicial complex. Alongside the full monoid, we examine some subsemigroups including St(G), defined by the condition that the full inverse image is an edge or the empty set and Inj(G), the monoid of all partial 1-1 continuous functions. We provide explicit combinatorial enumerations and struture for paths and cycles. We compute Green's relations showing in particular that the partial order of regular J-classes is isomorphic to the poset of induced subgraphs of G. Finally, we apply these structural invariants to Krohn-Rhodes complexity theory. It is known that the Margolis-Rhodes monoid has complexity at most 2 and 1 for St(G) and Inj(G). We show that for cycles the complexity of its Margolis-Rhodes monoid is 2 if and only if the cycle is of length at least 4. For paths, we prove that the complexity of its Margolis-Rhodes monoid is 2 if the path length is at least 13.
Related
- The prime spectrum of the talented monoid of a higher-rank graph and applications
- Kleisli convolution representations and a Margolis--Sakurai version of the modular isomorphism problem
- Defining the Crick-Franklin-Watson genes of any robot (equals a finite state machine) and defining the Shannon genetic code attached to each gene. We also define the Krohn-Rhodes complexity of any regular maximal prefix code
- K-theory of Matroids and Monoid Schemes
- K-theory of finite monoid sets
BibTeX
@misc{margolis2026margolisrhodes,
title = {{The Margolis-Rhodes Monoid of a Graph}},
author = {Stuart Margolis and John Rhodes},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.39370},
eprint = {2609.39370},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39370},
}
RIS
TY - UNPB
TI - The Margolis-Rhodes Monoid of a Graph
AU - Stuart Margolis
AU - John Rhodes
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.39370
UR - https://arxiv.org/abs/2609.39370
AB - We investigate the structural, combinatorial, ideal-theoretic and Krohn-Rhodes complexity of the Margolis-Rhodes monoid, MR(G), of a finite simple graph G, viewed topologically as a 1-dimensional simplicial complex. Alongside the full monoid, we examine some subsemigroups including St(G), defined by the condition that the full inverse image is an edge or the empty set and Inj(G), the monoid of all partial 1-1 continuous functions. We provide explicit combinatorial enumerations and struture for paths and cycles. We compute Green's relations showing in particular that the partial order of regular J-classes is isomorphic to the poset of induced subgraphs of G. Finally, we apply these structural invariants to Krohn-Rhodes complexity theory. It is known that the Margolis-Rhodes monoid has complexity at most 2 and 1 for St(G) and Inj(G). We show that for cycles the complexity of its Margolis-Rhodes monoid is 2 if and only if the cycle is of length at least 4. For paths, we prove that the complexity of its Margolis-Rhodes monoid is 2 if the path length is at least 13.
ER -