# Revision history [back]

If I got the problem correctly, the following code constructs the relations (eliminating some redundant ones):

Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
X2I = {v:i for i,v in enumerate(H.vertices())}

# G is isomorphic to H but has integer vertices and labeled edges
G = DiGraph()
for e in H.edges(labels=False):

# polynomials ring over the rationals with edge labels as variables
R = PolynomialRing(QQ,[e[2] for e in G.edges()])

S = G.path_semigroup()
print(len(S))

rels = []
for u in Y:
for v in Y.principal_upper_set(u):
P = S.all_paths(X2I[u],X2I[v])
for i in range(len(P)-1):
rels.append(R( str(P[i])+'-'+str(P[i+1])) )

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)


If I got the problem correctly, the following code constructs the relations (eliminating some redundant ones):

Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
X2I = {v:i for i,v in enumerate(H.vertices())}

# G is isomorphic to H but has integer vertices and labeled edges
G = DiGraph()
for e in H.edges(labels=False):

# polynomials ring over the rationals with edge labels as variables
R = PolynomialRing(QQ,[e[2] for e in G.edges()])

S = G.path_semigroup()
print(len(S))
#print(len(S))

rels = []
for u in Y:
for v in Y.principal_upper_set(u):
P = S.all_paths(X2I[u],X2I[v])
for i in range(len(P)-1):
rels.append(R( rels.append( R( str(P[i])+'-'+str(P[i+1])) )

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)


If I got the problem correctly, the following code constructs the relations (eliminating some redundant ones):

Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',['x'+str(v) for v in H.vertices()])
X2I = {v:i for i,v in enumerate(H.vertices())}

# G is isomorphic to H but has integer vertices and labeled edges
G = DiGraph()
G.add_edges( (X2I[e[0]],X2I[e[1]],'x'+str(e[0])+'_x'+str(e[1])) for e in H.edges(labels=False):
H.edges(labels=False) )
print('arrows:',[e[2] for e in G.edges()])

# polynomials ring over the rationals with edge labels as variables
R = PolynomialRing(QQ,[e[2] for e in G.edges()])

S = G.path_semigroup()
#print(len(S))

rels = []
for u u,v in Y:
for v in Y.principal_upper_set(u):
Y.relations_iterator(strict=True):
P = S.all_paths(X2I[u],X2I[v])
for i in range(len(P)-1):
rels.append( R( str(P[i])+'-'+str(P[i+1])) )

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)


If I got the problem correctly, the following code constructs the relations (eliminating some redundant ones):

Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',['x'+str(v) print('vertices:',['x'+v for v in H.vertices()])
X2I = {v:i for i,v in enumerate(H.vertices())}

# G is isomorphic to H but has integer vertices and labeled edges
G = DiGraph()
G.add_edges( (X2I[e[0]],X2I[e[1]],'x'+str(e[0])+'_x'+str(e[1])) (X2I[e[0]], X2I[e[1]], 'x%s_x%s' % e) for e in H.edges(labels=False) )
print('arrows:',[e[2] for e in G.edges()])

# polynomials ring over the rationals with edge labels as variables
R = PolynomialRing(QQ,[e[2] for e in G.edges()])

S = G.path_semigroup()
#print(len(S))

rels = []
for u,v in Y.relations_iterator(strict=True):
P = S.all_paths(X2I[u],X2I[v])
for i in range(len(P)-1):
rels.append( R( str(P[i])+'-'+str(P[i+1])) )

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)


If I got the problem correctly, the following code constructs the relations (eliminating some redundant ones):

import json

Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',['x'+v print('vertices:',json.dumps(['x'+v for v in H.vertices()])
H.vertices()]))
X2I = {v:i for i,v in enumerate(H.vertices())}

# G is isomorphic to H but has integer vertices and labeled edges
G = DiGraph()
G.add_edges( (X2I[e[0]], X2I[e[1]], 'x%s_x%s' % e) for e in H.edges(labels=False) )
print('arrows:',[e[2] print('arrows:',json.dumps([e[2] for e in G.edges()])
G.edges()]))

# polynomials ring over the rationals with edge labels as variables
R = PolynomialRing(QQ,[e[2] for e in G.edges()])

S = G.path_semigroup()
#print(len(S))

rels = []
for u,v in Y.relations_iterator(strict=True):
P = S.all_paths(X2I[u],X2I[v])
for i in range(len(P)-1):
rels.append( R( str(P[i])+'-'+str(P[i+1])) f'{P[i]} - {P[i+1]}' ) )

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)


If I got the problem correctly, the following code constructs the relations (eliminating some redundant ones):

import json

Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+v for v in H.vertices()]))
X2I = {v:i for i,v in enumerate(H.vertices())}

# G is isomorphic to H but has integer vertices and labeled edges
G = DiGraph()
G.add_edges( (X2I[e[0]], X2I[e[1]], 'x%s_x%s' % e) for e in H.edges(labels=False) )
print('arrows:',json.dumps([e[2] for e in G.edges()]))

# polynomials ring over the rationals with edge labels as variables
R = PolynomialRing(QQ,[e[2] for e in G.edges()])

S = G.path_semigroup()
#print(len(S))

rels = []
for u,v in Y.relations_iterator(strict=True):
P = S.all_paths(X2I[u],X2I[v])
for i in range(len(P)-1):
rels.append( R( rels += [R( f'{P[i]} - {P[i+1]}' ) )
for i in range(len(P)-1)]

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)


If I got the problem correctly, the following code constructs the relations (eliminating some redundant ones):

import json

Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+v for v in H.vertices()]))
print('arrows:',json.dumps([['x'+e[0],'x'+e[1],'x%s_x%s' % e] for e in H.edges(labels=False)]))

X2I = {v:i for i,v in enumerate(H.vertices())}

# G is isomorphic to H but has integer vertices and labeled edges
G = DiGraph()
G.add_edges( (X2I[e[0]], X2I[e[1]], 'x%s_x%s' % e) for e in H.edges(labels=False) )
print('arrows:',json.dumps([e[2] for e in G.edges()]))

# polynomials ring over the rationals with edge labels as variables
R = PolynomialRing(QQ,[e[2] for e in G.edges()])

S = G.path_semigroup()
#print(len(S))

rels = []
for u,v in Y.relations_iterator(strict=True):
P = S.all_paths(X2I[u],X2I[v])
[p for p in S.all_paths(X2I[u],X2I[v]) if len(p)==2]
rels += [R( f'{P[i]} - {P[i+1]}' ) for i in range(len(P)-1)]

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)


If I got the problem correctly, the following code constructs the relations (eliminating some redundant ones):

import json

Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()

print('vertices:',json.dumps(['x'+v print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+e[0],'x'+e[1],'x%s_x%s' print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),'x%s_x%s' % e] for e in H.edges(labels=False)]))

X2I = {v:i for i,v in enumerate(H.vertices())}

# G is isomorphic to H but has integer vertices and labeled edges
G = DiGraph()
G.add_edges( (X2I[e[0]], X2I[e[1]], 'x%s_x%s' % e) for e in H.edges(labels=False) )

# polynomials ring over the rationals with edge labels as variables
R = PolynomialRing(QQ,[e[2] for e in G.edges()])

S = G.path_semigroup()
#print(len(S))

rels = []
for u,v in Y.relations_iterator(strict=True):
P = [p for p in S.all_paths(X2I[u],X2I[v]) if len(p)==2]
rels += [R( f'{P[i]} - {P[i+1]}' ) for i in range(len(P)-1)]

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)


If I got the problem correctly, the following code constructs the relations (eliminating (excluding some redundant ones):

import json

def xlabel(e):
return 'x%s_x%s' % e

Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()

print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),'x%s_x%s' % e] print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))

X2I R = {v:i for i,v in enumerate(H.vertices())}

# G is isomorphic to H but has integer vertices and labeled edges
G = DiGraph()
G.add_edges( (X2I[e[0]], X2I[e[1]], 'x%s_x%s' % e) PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False) )

# polynomials ring over the rationals with edge labels as variables
R = PolynomialRing(QQ,[e[2] for e in G.edges()])

S = G.path_semigroup()
#print(len(S))
H.edges(labels=False)])

rels = []
for u,v u in Y.relations_iterator(strict=True):
H.vertices():
for v in set.union(*([set()]+[set(H.neighbors_out(w)) for w in H.neighbors_out(u)])):
P = [p for p in S.all_paths(X2I[u],X2I[v]) if len(p)==2]
list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( f'{P[i]} - {P[i+1]}' xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)


If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):

import json

def xlabel(e):
return 'x%s_x%s' % e

Y = posets.SymmetricGroupBruhatOrderPoset(3)

H = Y.hasse_diagram()

print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))

R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])

rels = []
for u in H.vertices():
for v in set.union(*([set()]+[set(H.neighbors_out(w)) set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)])):
H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]

print('# rels:',len(rels))


To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).

J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)