ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 22 Apr 2018 09:31:40 -0500Partially commutative monoid of a graphhttp://ask.sagemath.org/question/41756/partially-commutative-monoid-of-a-graph/I am interested in the free partially commutative monoid associated to a graph whose definition can be seen here www.sciencedirect.com/science/article/pii/0304397591903556 and here https://en.m.wikipedia.org/wiki/Trace_monoid.
Basically I need a free monoid in which some variables commutes.
My questions are
1. whether this notion is already implemented in Sage?
2. If not how to implement this in Sage?Sun, 25 Mar 2018 10:54:57 -0500http://ask.sagemath.org/question/41756/partially-commutative-monoid-of-a-graph/Answer by slelievre for <p>I am interested in the free partially commutative monoid associated to a graph whose definition can be seen here <a href="http://www.sciencedirect.com/science/article/pii/0304397591903556">www.sciencedirect.com/science/article...</a> and here <a href="https://en.m.wikipedia.org/wiki/Trace_monoid">https://en.m.wikipedia.org/wiki/Trace...</a>. </p>
<p>Basically I need a free monoid in which some variables commutes.</p>
<p>My questions are</p>
<ol>
<li><p>whether this notion is already implemented in Sage?</p></li>
<li><p>If not how to implement this in Sage?</p></li>
</ol>
http://ask.sagemath.org/question/41756/partially-commutative-monoid-of-a-graph/?answer=42123#post-id-42123I forwarded your question to the sage-combinat-devel mailing list and
Travis Scrimshaw just answered, see
- [https://groups.google.com/d/topic/sage-combinat-devel/hSt1GXDh1NU/discussion](https://groups.google.com/d/topic/sage-combinat-devel/hSt1GXDh1NU/discussion)Sun, 22 Apr 2018 09:31:40 -0500http://ask.sagemath.org/question/41756/partially-commutative-monoid-of-a-graph/?answer=42123#post-id-42123Answer by dan_fulea for <p>I am interested in the free partially commutative monoid associated to a graph whose definition can be seen here <a href="http://www.sciencedirect.com/science/article/pii/0304397591903556">www.sciencedirect.com/science/article...</a> and here <a href="https://en.m.wikipedia.org/wiki/Trace_monoid">https://en.m.wikipedia.org/wiki/Trace...</a>. </p>
<p>Basically I need a free monoid in which some variables commutes.</p>
<p>My questions are</p>
<ol>
<li><p>whether this notion is already implemented in Sage?</p></li>
<li><p>If not how to implement this in Sage?</p></li>
</ol>
http://ask.sagemath.org/question/41756/partially-commutative-monoid-of-a-graph/?answer=41796#post-id-41796(1) It appears that there is no such construction.
(2) Before we read the whole article in depth, which is a lot of work, and i could not spot any breakthrough-structure (for my taste) at first flight, what exactly should be implemented in sage. It feels, that it is easy to implement - for a given finite graph $G$, and for a fixed order on its vertices $\sigma$, and for given elements in the associated monoid $\Sigma^*/\sim$ - a way to get the "first word" in the class of equivalence.
Which constructions should be done now? (The implementation should be close to the application, here and in similar cases.) Please give details in the question, possibly there will be pointed answers to the needed computational framework.
This is an answer and not a comment, to be able to give some code, that may help.
* There is a construction of a free monoid generated by an "alphabet" $\Sigma$, for instance:
sage: F.<a,b,c,d,e> = FreeMonoid()
sage: SIGMA = F.gens()
sage: SIGMA
(a, b, c, d, e)
* We can specify some graph $G$ with five vertices, e.g. using the same letters,
a b
*---*
\ /
*---*---*
c d e
This makes $c$ commute with $a,b,d$ for instance, but not with $e$. (In the associated monoid $M=M(G)$.)
* It is possible to declare an ideal of $F$, but this is not useful for our construction $G\to M(G)$, as far as i can see...
* There is an algebra on $F$, e.g.
sage: A = F.algebra(QQ)
sage: A
Algebra of Free monoid on 5 generators (a, b, c, d, e) over Rational Field
* We finally introduce the graph $G$, using the same letters $a,b,c,d,e$ from above.
sage: G = Graph( [ [a,b,c,d,e], [(a,b), (a,c), (b,c), (c,d), (d,e)] ] )
sage: G
Graph on 5 vertices
sage: G.clique_complex()
Simplicial complex with vertex set (a, b, c, d, e) and facets {(a, b, c), (d, e), (c, d)}
* We can now introduce for instance:
sage: F.<a,b,c,d,e> = FreeMonoid()
sage: A = F.algebra(QQ)
sage: G = Graph( [ [a,b,c,d,e], [(a,b), (a,c), (b,c), (c,d), (d,e)] ] )
sage: def P(K):
....: return sum( [ A(0), ] + [ (-1)^len(S)*prod( [A(s) for s in S] ) for S in Set(K).subsets() if S ] )
....:
sage: for K in G.clique_complex().facets():
....: print K, P(K)
....:
(a, b, c) -B[a] - B[b] - B[c] + B[a*c] + B[b*a] + B[b*c] - B[b*a*c]
(d, e) -B[d] - B[e] + B[d*e]
(c, d) -B[c] - B[d] + B[d*c]
* However, in $A$ the letters $a$ and $b$ do not commute. A two sided ideal may be maybe defined here, and the computations may have a chance to work in this linearized version of $A$.
sage: J = A.ideal( [ A(s)*A(t)-A(t)*A(s) for s,t,_ in G.edges() ] )
sage: J
Twosided Ideal (B[a*b] - B[b*a], B[a*c] - B[c*a], B[b*c] - B[c*b], B[c*d] - B[d*c], B[d*e] - B[e*d]) of Algebra of Free monoid on 5 generators (a, b, c, d, e) over Rational Field
sage: Q = A.quotient(J)
Tue, 27 Mar 2018 15:03:37 -0500http://ask.sagemath.org/question/41756/partially-commutative-monoid-of-a-graph/?answer=41796#post-id-41796