The Structure of a Graph Inverse Semigroup

Authors:
  • ZMZachary Mesyan
    Zachary Mesyan
  • JMJ. D. Mitchell
    J. D. Mitchell

Abstract
Given any directed graph E one can construct a graph inverse semigroup G(E), where, roughly speaking, elements correspond to paths in the graph. In this paper we study the semigroup-theoretic structure of G(E). Specifically, we describe the non-Rees congruences on G(E), show that the quotient of G(E) by any Rees congruence is another graph inverse semigroup, and classify the G(E) that have only Rees congruences. We also describe the partially ordered set of J-classes of G(E), find the minimum possible degree of a faithful representation by partial transformations of any countable G(E), and show that any isomorphism between two graph inverse semigroups restricts to an isomorphism of the underlying graphs.