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.

Improve this question
$\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$
    – Benjamin Steinberg
    Commented 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$
    – Benjamin Steinberg
    Commented 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$
    – Robert Bell
    Commented Mar 8, 2018 at 19:03
  • 3
    $\begingroup$ If $c^2=1=c^3$ then $c=1$ and your monoid is trivial. $\endgroup$
    – Benjamin Steinberg
    Commented 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$
    – Andreas Blass
    Commented Mar 8, 2018 at 20:22

0

Reset to default

Browse other questions tagged .