Square CoCalc Logo
FeaturesSoftwarePricingInfoPoliciesShareSupport Try Sign InSign Up
Views: 360
Image: ubuntu2004
| Embed | Download | Raw
Kernel: SageMath 9.2

Group Relationships in Homotopy Graph Category

-Research by Alexis Stahl and Ralph Studer ParseError: KaTeX parse error: Undefined control sequence: \$ at position 1: \̲$̲ -Under guidanc…$ -Funded by the Center for Undergraduate Research in Mathematics and NSF


This code was built to analyze graph transformations, specifically using the Homotopy Category established in the work of Chih-Scull. In the accompanying paper, we build upon the work of Chih-Scull and prove the existence of various group relationships within the Homotopy Category. The following functions cover some of the central concepts we developed including the Spider Nest, the Pleat, and the factor group Aut(G) mod Null(G).



A graph is defined as a set of vertices and a set of edges, G={V(G),E(G)}G=\{V(G),E(G)\}.

The graph category is finite, undirected graphs, where at most one edge connects any pair of vertices, though a vertex can be looped to itself.

The exponential graph, GHG^H, is defined by:ParseError: KaTeX parse error: Undefined control sequence: \$ at position 1: \̲$̲ -A vertex in V(G^H)isasetmap is a set map V(G) \to V(H) $ -There is an edge fgf \sim g if whenever v1v2E(G)v_1 \sim v_2 \in E(G), then f(v1)f(v2)E(H)f(v_1)\sim f(v_2) \in E(H).

A homomorphism ϕ:GH\phi: G \to H maps V(G)V(H)V(G)\to V(H) such that if vwG,v \sim w \in G, then ϕ(v)ϕ(w)H\phi(v)\sim \phi(w) \in H.

Given two graphs GG and HH, exponential_object returns the subgraph of homomorphisms within the exponential graph, GHG^H.

In [28]:
def exponential_object(G, H, show=False): set_map = FiniteSetMaps(G.vertices(), H.vertices()) exp_G_to_H = Graph(loops=True) exp_G_to_H.add_vertices(set_map) homomorphisms = Graph(loops=True) for f in set_map: for g in set_map: if (f, g, None) not in exp_G_to_H: edge = True for e in G.edges(): if ((f(e[0]), g(e[1]), None) not in H.edges()) or ((f(e[1]), g(e[0]), None) not in H.edges()): edge = False if edge: exp_G_to_H.add_edges([(f, g)]) if f == g: homomorphisms.add_vertices([f]) hom_graphs = exp_G_to_H.subgraph(homomorphisms) if show: hom_graphs.show(figsize=[100,4],dpi=100) else: return hom_graphs
In [3]:
exponential_homs(graphs.PathGraph(3), graphs.PathGraph(3), show=True)
Image in a Jupyter notebook


Given a graph, a spider pair is defined as follows: Let ϕ,ψ:GH\phi,\psi: G\to H be homomorphisms. ϕ,ψ\phi,\psi are a spider pair if \exists at most one vV(G)v\in V(G) such that ϕ(v)ψ(v)\phi(v)\neq\psi(v).

A spider web of two graphs, W(G,H)W(G, H), is defined as follows: Let ϕ:GH\phi: G\to H. V(W(G, H)) = {ϕ\phi: ϕ\phi is a homomorphism} and E(W(G, H)) = {ϕ1ϕ2\phi_1\phi_2: ϕ1\phi_1 and ϕ2\phi_2 are a spider pair}.

In [29]:
def spider_web(graph1, graph2, show=False): exp = exponential_object(graph1, graph2) for f in exp: for g in exp: count = 0 for num in range(len(f)): if f[num] != g[num]: count += 1 if count > 1: exp.delete_edges([(f,g)]) if show: exp.show(figsize=[100,4],dpi=100) else: return exp
In [24]:
spider_web(graphs.PathGraph(3), graphs.PathGraph(4), True)
Image in a Jupyter notebook


A spider nest of a graph, SN(G)SN(G), is defined as W(G,G)W(G,G).

In [4]:
def spider_nest(graph): return spider_web(graph, graph, show=True)
In [23]:
Image in a Jupyter notebook


A graph, G, is in its stiff form when there exist no distinct vertices vv and ww such that N(v)N(w)N(v) \subseteq N(w).

We then define the pleat of a graph GG as follows: Pl(G)Pl(G) is the unique stiff subgraph of GG such that \exists ρ:GPl(G)\rho:G\to Pl(G) where ρ\rho can be expressed as a series of folds.

In [20]:
# Find a graph's unique stiff subgraph def pleat(graph): for vert in graph.vertices(): orig_neighbors = graph.neighbors(vert) for neighbor in orig_neighbors: moves = [x for x in graph.neighbors(neighbor) if x != vert and set(orig_neighbors).issubset(graph.neighbors(x))] if len(moves) > 0: try: graph.delete_vertex(vert) except: ValueError pass no_moves_count = 0 for vert in graph.vertices(): moves = [] for neighb in graph.neighbors(vert): for neighb2 in graph.vertices(neighb): if neighb2 != vert and set(graph.neighbors(vert)).issubset(graph.neighbors(neighb2)): moves.append(neighb2) if len(moves) == 0: no_moves_count += 1 if no_moves_count != len(graph.vertices()): return pleat(graph) else: return graph.show(figsize=[80,3],dpi=80)
In [22]:
# Pleat of C4 g = graphs.CycleGraph(4) g.show(figsize=[80,3],dpi=80) pleat(graphs.CycleGraph(4))
Image in a Jupyter notebookImage in a Jupyter notebook


An automorphism of a graph, G, is a permutation, ϕ\phi, of V(G) such that vwv\sim w iff ϕ(v)ϕ(w)\phi(v)\sim \phi(w).

The automorphism group, Aut(G), is defined as the group of automorphisms of a graph.

We define Null(G) as follows: Null(G)={aAut(G)Null(G) = \{a\in Aut(G) | aidG}a\simeq id_G\}.

factor_group returns the quotient Null(G)/Aut(G)Null(G)/Aut(G) also written Aut(G)modNull(G)Aut(G) \mod Null(G).

In [30]:
def factor_group(graph1): null_g = [] aut_g = graph1.automorphism_group() for comp in spider_web(graph1, graph1).connected_components_subgraphs(): vert_list = [] for mapping in comp.vertices(): vert_list.append(mapping[:]) if graph1.vertices() in vert_list: count = 1 for aut in aut_g: aut_dict = aut.dict() aut_vals = [x for x in aut_dict.values()] if aut_vals in vert_list and aut_vals != graph1.vertices(): count += 1 null_g.append(str(aut)) for num in range(2, len(null_g)): if null_g[1] or null_g[2] in null_g[num]: null_g.remove(null_g[num]) if count == len(aut_g): null_g = aut_g elif count <= 1: return aut_g else: null_g = PermutationGroup(null_g) if len(null_g) < 1: return aut_g else: return aut_g.quotient(null_g)
In [31]:
# Null(C3)/Aut(C3) g = graphs.CycleGraph(3) factor_group(g).list()
[(), (0,1,2), (0,2,1), (1,2), (0,1), (0,2)]

In the example above, we can see that Aut(C3)modNull(C3)Aut(C3)Aut(C_3) \mod Null(C_3) \cong Aut(C_3). We know this is true because Null(C3)={}Null(C_3)=\{\}

In [32]:
# Null(C4)/Aut(C4) graph = graphs.CycleGraph(4) factor_group(graph).list()
[(), (1,2)]

In the above example, we see that Aut(C4)modNull(C4)Z2Aut(C_4)\mod Null(C_4) \cong \mathbb{Z}_2. We know this is true because Null(C4)Null(C_4) contains all autmorphisms of C4C_4 except any permutation that sends vnvn+1v_n \to v_{n+1} (or vertices to their opposite parities).

In [0]: