1
$\begingroup$

Let $G$ be a simple graph with vertex $I$ and edge set $E$. I am defining $M(G)$ to be the quotient of the free monoid $I^*$ on $I$ by the relations $ab=ba$ and $c^2 = 1$ whenever $\{a,b\} \notin E(G)$ and $c \in I$ is arbitrary.

I have the following questions about the monoid $M(G)$.

  1. Is this monoid $M(G)$ well studied in the literature?

  2. What are some algebraic combinatorics or general combinatorial significance of this monoid?

Thanks for your time and have a good day.

$\endgroup$
13
  • $\begingroup$ If you just make adjacent vertices commute you get what are called trace monoids or free partially commutative monoids. They were studied by Cartier and Foata in the seventies in connection with combinatorics and there is now also a huge literature in automata and concurrency theory. I don't know why you are imposing the second relation which doesn't menton b $\endgroup$ Mar 8, 2018 at 18:12
  • 2
    $\begingroup$ But then every vertex which is not connected to some vertex is an involution. So it seems to me you get a free product of a right angled coxeter group and a free monoid. $\endgroup$ Mar 8, 2018 at 18:41
  • 2
    $\begingroup$ With your changes, your monoid is in fact a group: $c^n = 1$ for some $n$ (depending on $c$) implies that $c$ has an inverse. The object you've defined is called a graph product of finite cyclic groups. As Benjamin says, these are called right-angled Coxeter groups if $n = 2$ for every $c \in I$. $\endgroup$ Mar 8, 2018 at 19:03
  • 3
    $\begingroup$ If $c^2=1=c^3$ then $c=1$ and your monoid is trivial. $\endgroup$ Mar 8, 2018 at 19:55
  • 5
    $\begingroup$ If $c^2=c^3=1$ then $1=c^3=c^2\cdot c=1\cdot c=c$. $\endgroup$ Mar 8, 2018 at 20:22

0