Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper analyzes the Margolis-Rhodes monoid MR(G) of a finite simple graph G, focusing on its structural, combinatorial, and Krohn-Rhodes complexity. The authors provide explicit enumerations for paths and cycles, compute Green's relations revealing an isomorphism between regular J-classes and induced subgraphs, and establish complexity bounds for specific graph structures. The key result shows that the Krohn-Rhodes complexity of MR(G) is 2 for cycles of length $\ge 4$ and paths of length $\ge 13$.
The Krohn-Rhodes complexity of graph monoids reveals a sharp threshold for cycles and paths, with MR(G) becoming complexity 2 for cycles $\ge 4$ and paths $\ge 13$.
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.