Guest User

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.  
  44. def monadGraph(G, n=10, onlyPrimitive=True):
  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)
  99. CAG, mcol = monadGraph(G,n)
  100.  
  101. print("extension graph")
  102. show(Gex.plot(vertex_colors=ecol, vertex_size=50, iterations=20000))
  103.  
  104. print("monad graph")
  105. show(CAG.plot(vertex_colors=mcol, vertex_size=50, iterations=20000))
  106.  
  107.  
  108. # An example of interest -- this is the counterexample from Cassals-Ruiz, Duncan, Kazachkov:
  109. Gamma = Graph([['a1','a2','b','c','d','e'],[('a1','a2'),('a1','d'),('a1','e'),('a2','d'),('a2','e'),('d','e'),('c','d'),('c','a1'),('b','e'),('b','a2')]])
  110.  
  111. # this renders the graph in a way that is almost illegible.
  112. testGraph(Gamma, 50)
RAW Paste Data