1

-Research by Alexis Stahl and Ralph Studer $\\$ -Under guidance of Dr. Tien Chih, Asst. Math Professor at Montana State University of Billings $\\$ -Funded by the Center for Undergraduate Research in Mathematics and NSF

2

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).

3

4

`exponential_object`

A **graph** is defined as a set of vertices and a set of edges, $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**, $G^H$, is defined by:$\\$
-A vertex in $V(G^H)$ is a set map $V(G) \to V(H) \\$
-There is an edge $f \sim g$ if whenever $v_1 \sim v_2 \in E(G)$, then $f(v_1)\sim f(v_2) \in E(H)$.

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

Given two graphs $G$ and $H$, `exponential_object`

returns the subgraph of **homomorphisms** within the **exponential graph**, $G^H$.

5

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

6

In [3]:

exponential_homs(graphs.PathGraph(3), graphs.PathGraph(3), show=True)

7

`spider_web`

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

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

8

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

9

In [24]:

spider_web(graphs.PathGraph(3), graphs.PathGraph(4), True)

10

`spider_nest`

11

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

12

In [4]:

def spider_nest(graph): return spider_web(graph, graph, show=True)

13

In [23]:

spider_nest(graphs.CycleGraph(4))

14

`pleat`

15

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

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

16

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)

17

In [22]:

# Pleat of C4 g = graphs.CycleGraph(4) g.show(figsize=[80,3],dpi=80) pleat(graphs.CycleGraph(4))

18

`factor_group`

An **automorphism** of a graph, G, is a permutation, $\phi$, of V(G) such that $v\sim w$ iff $\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) = \{a\in Aut(G)$ $|$ $a\simeq id_G\}$.

`factor_group`

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

19

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)

20

In [31]:

# Null(C3)/Aut(C3) g = graphs.CycleGraph(3) factor_group(g).list()

21

[(), (0,1,2), (0,2,1), (1,2), (0,1), (0,2)]

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

22

In [32]:

# Null(C4)/Aut(C4) graph = graphs.CycleGraph(4) factor_group(graph).list()

23

[(), (1,2)]

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

24

In [ ]:

25