This is a site meant to let you easily compute the B-Symmetric Chromatic Function. If you're unfamiliar with the B-Symmetric Chromatic Function, perhaps try looking at Dr. Sergei Chmutov's Presentation or Rushil Raghavan's Presentation to learn more if you're interested.
xxxxxxxxxx# The SignedGraph strucutre gives utilities for dealing with deletion contraction and signs.class SignedGraph(): def __init__(self, g = None, weights = None, signs = None, edge_id = 0): if (g): self.g = g else: self.g = Graph(loops = True, multiedges = True) if (weights): self.weights = weights else: self.reset_weights() if (signs != None): self.signs = signs else: self.signs = {} self.edge_id = edge_id def copy(self): return SignedGraph( g = self.g.copy(), weights = dict(self.weights), signs = dict(self.signs), edge_id = self.edge_id ) # ************************** # Graph Manipulation Methods # ************************** def reset_weights(self): self.weights = {} for vertex in self.g.vertices(sort = False): self.weights[vertex] = (1, 0) def add_vertex(self, name = None): v_name = self.g.add_vertex(name) v_name = v_name if v_name != None else name self.weights[v_name] = (1, 0) return v_name def add_vertices(self, count): for i in range(count): v_name = self.g.add_vertex() self.weights[v_name] = (1, 0) def add_edge(self, edge, sign = 1, name = None): e_name = name if (e_name == None): e_name = "e" + str(self.edge_id) self.edge_id += 1 self.g.add_edge(edge[0], edge[1], e_name) self.signs[e_name] = sign def get_edge_with_name(self, name): for edge in self.g.edges(): if (edge[2] == name): return edge # *********************** # Graph Operation Methods # *********************** def _contract_edge_unsigned(self, name): # Doesn't handle sign logic edge = self.get_edge_with_name(name) self.g.contract_edge(edge) if (edge[0] != edge[1]): w0 = self.weights[edge[1]] w1 = self.weights[edge[0]] self.weights[edge[0]] = (w0[0] + w1[0], w0[1] + w1[1]) del self.weights[edge[1]] def contract_edge(self, name): if (self.signs[name] == -1): edge = self.get_edge_with_name(name) self.vertex_switch(edge[0]) self._contract_edge_unsigned(name) def delete_edge(self, name): edge = self.get_edge_with_name(name) self.g.delete_edge(edge) def vertex_switch(self, v): self.weights[v] = (self.weights[v][1], self.weights[v][0]) for edge in self.g.edges_incident([v]): if (edge[0] != edge[1]): self.signs[edge[2]] = -self.signs[edge[2]] # ********************* # Graph Reading Methods # ********************* def getSubgraph(self, S): g1 = Graph(loops = True, multiedges = True) g1.add_vertices(self.g.vertices()) g1.add_edges(S) return g1 def sign_color_component(self, cc): partition = {} for v in cc.depth_first_search(cc.random_vertex()): if (len(partition) == 0): partition[v] = 1 continue for v1 in cc.neighbors(v): if (v1 in partition): sign = self.signs[cc.edge_label(v, v1)[0]] partition[v] = sign * partition[v1] for v1 in cc.neighbors(v): if (v1 in partition): for edge in cc.edge_boundary([v], [v1]): if(partition[v1] * self.signs[edge[2]] != partition[v]): return None return partition# ****************************# We next define Signed Posets# ****************************class SignedPoset(): def __init__(self, n, roots = {}): self.n = n self.r = RootSystem("B" + str(n)) self.roots = set({ self.r.ambient_space().from_vector(root) for root in roots }) self.extend_to_implied_set() def __repr__(self): return str(self.roots) def copy(self): return SignedPoset(self.n, [root.to_vector() for root in self.roots.copy()]) def extend_to_implied_set(self): def get_size(p): return sum([abs(coord[1]) for coord in list(p)]) root_system_roots = set(self.r.ambient_space().roots()) self.roots = set(self.roots) roots_original = None try: while (roots_original == None or roots_original != self.roots): roots_original = set(self.roots) for p1, p2 in Combinations(self.roots, 2): p = p1 + p2 p = len(list(p)) * p / get_size(p) if (p in root_system_roots): self.roots.add(p) except ZeroDivisionError: raise ValueError("Error! The poset violates antisymmetry/transitivity!") def get_jordan_holder_set(self): L = [] positive_roots = set(self.r.ambient_space().positive_roots()) for w in WeylGroup(self.r): inv_w = w^-1 if (all([inv_w.action(p) in positive_roots for p in self.roots])): L.append(w) return L def plot_digraph(self): d = Graph(self.n, loops = True, multiedges = True) for p in self.roots: coords = list(p) if (len(coords) == 1): # Then it's a loop label = str(coords[0][0]) + ("<" if coords[0][1] > 0 else ">") d.add_edge(coords[0][0], coords[0][0], label) elif (len(coords) == 2): label = str(coords[0][0]) + ("<" if coords[0][1] > 0 else ">") + \ (">" if coords[1][1] > 0 else "<") + str(coords[1][0]) d.add_edge(coords[0][0], coords[1][0], label) else: print("An error occurred") d.show(edge_labels = True, layout = "circular")# *********************************************# Next utilities for working with Signed Posets# *********************************************def list_acyclic_orientations(wg): orientations = set() n = wg.g.num_verts() V = VectorSpace(QQ, n) V._assign_names(["e" + str(i) for i in range(n)]) e = V.gens() edges = wg.g.edges() rs = SignedPoset(n).r.ambient_space() for t in Tuples({-1, 1}, wg.g.num_edges()): try: P = SignedPoset(n, [ \ tau * vector(e[edge[0]] - wg.signs[edge[2]] * e[edge[1]]) for edge,tau in zip(edges, t)]) orientations.add(P) # Constructor for SignedPoset throws error if the set you give it isn't a poset except ValueError: continue return orientations# *************************************************# We next define the B-Symmetric Chromatic Function# *************************************************n = 9p = matrix(n + 1, n + 1, [ var("p_{}_{}".format(i, j), latex_name="p_{{{},{}}}".format(i, j)) for i in [0 .. n] for j in [0 .. n]] )prefer_first_coord_subs = {}for i in range(n+1): for j in range(n+1): if (i < j): prefer_first_coord_subs[p[i][j]] = p[j][i]def prefer_first_coord(f): return f.subs(prefer_first_coord_subs).expand()def BSymmetricChromaticFunction(wg1): poly = 0 for loop in wg1.g.loops(): if (wg1.signs[loop[2]] == 1): return 0 wg = wg1.copy() wg.g.remove_loops() for S in powerset(wg.g.edges()): ccs = wg.getSubgraph(S).connected_components_subgraphs() term = (-1) ** len(S) for cc in ccs: for loop in cc.loops(): if (wg.signs[loop[2]] == 1): return 0 partition = wg.sign_color_component(cc) if (partition == None): term = 0 break w = [0, 0] for key, sign in partition.items(): w[(1 - sign)/2] += wg.weights[key][0] + wg.weights[key][1] term *= p[w[0]][w[1]] poly += term return prefer_first_coord(poly)# ********************************************************# The rest of the file is just giving some built in graphs# ********************************************************def create_path(n, signs = None): if (signs == None): signs = [1] * (n - 1) wg = SignedGraph() wg.add_vertices(n) for i in range(n - 1): wg.add_edge((i, i + 1), signs[i]) return wgdef create_cycle(n, signs = None): if (signs == None): signs = [1] * n wg = SignedGraph() wg.add_vertices(n) for i in range(n): wg.add_edge((i, (i + 1) % n), signs[i]) return wgdef create_star(n, signs = None): if (signs == None): signs = [1] * (n - 1) wg = SignedGraph() wg.add_vertices(n) for i in range(n - 1): wg.add_edge((0, i + 1), signs[i]) return wgxxxxxxxxxx# An example of constructing a graphwg = SignedGraph()wg.add_vertices(3)for i in range(3): wg.add_edge((i, (i + 1) % 3), (-1) ** i)wg.g.show() # I still have to make it show the edgespretty_print(BSymmetricChromaticFunction(wg))# Alternatively, use premade functions:pretty_print(BSymmetricChromaticFunction(create_cycle(3, [1, -1, 1])))