# Sage graphs

a guest
Aug 21st, 2020
66
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import itertools
2.
3. def raag(G):
4. # the default notion of raag is backwards...
5. return RightAngledArtinGroup(G.complement())
6.
7. def words(G):
8. """
9. A lazy list of all the words in the generators of G
10. """
11. gens = list(G.gens()) + [g.inverse() for g in list(G.gens())]
12. i = 1
13. while 1:
14. for g in itertools.product(*([gens] * i)):
15. yield g
16. i += 1
17.
18. def extensionGraph(G, n=10):
19. """
20. Kim and Koberda define the 'extension graph' and give a related conjecture, which we're testing.
21.
22. The conjecture is that raag(G) embeds in raag(H) if and only if G embeds in extension(H),
23. and is stated in their paper "embedability between right angled artin groups"
24.
25. @n controls how big we want this finite approximation to extension(G) to be.
26. """
27. AG = raag(G)
28. gens = list(AG.gens())
29.
30. colors = {gens[i]: rainbow(len(gens))[i] for i in range(len(gens))}
31.
32. new_vertices = list(AG.gens())
33. color = {colors[g]: [g] for g in gens}
34. for g in itertools.islice(words(AG),n):
35. g = product(list(g))
36. for v in gens:
37. x = g*v*g.inverse()
38. if x not in new_vertices:
39. new_vertices.append(x)
40. color[colors[v]] += [x]
41.
42. return (Graph([new_vertices, lambda x,y: x*y == y*x and x != y]), color)
43.
45. """
46. Send G to comm(raag(G))
47.
48. @n controls how big we want the finite approximation to be
49.
50. @onlyPrimitive will filter out only the primitive elements
51. of the graph. Each of these corresponds to a complete countable
52. graph given by its powers. But if you want an embedding, you
53. can only pick one vertex from each of these clusters, so for
54. clarity of the image, we might as well only show one.
55. """
56. AG = raag(G)
57. gens = list(AG.gens())
58.
59. colors = {gens[i]: rainbow(len(gens))[i] for i in range(len(gens))}
60.
61. new_vertices = list(AG.gens())
62. color = {colors[g]: [g] for g in gens}
63. color['white'] = []
64. for g in itertools.islice(words(AG),n//2): # make the conjugates be of about the right length
65. g = product(list(g))
66. for v in gens:
67. x = g*v*g.inverse()
68. if x not in new_vertices:
69. keep = True
70. if onlyPrimitive:
71. for (seen, i) in itertools.product(new_vertices,range(-n,n+1)):
72. if seen^i == x:
73. keep = False
74. break
75. if keep:
76. new_vertices.append(x)
77. color[colors[v]] += [x]
78.
79. for g in itertools.islice(words(AG),n):
80. g = product(list(g))
81. if g not in new_vertices:
82. keep = True
83. if onlyPrimitive:
84. for (seen, i) in itertools.product(new_vertices, range(-n,n+1)):
85. if seen^i == g:
86. keep = False
87. break
88. if keep:
89. new_vertices.append(g)
90. color['white'] += [g]
91.
92. return (Graph([new_vertices, lambda x,y: x*y==y*x and x != y]), color)
93.
94. def testGraph(G,n):
95. """
96. Show both the extension graph and the monad graph to compare them.
97. """
98. Gex, ecol = extensionGraph(G,n)
100.
101. print("extension graph")
102. show(Gex.plot(vertex_colors=ecol, vertex_size=50, iterations=20000))
103.