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

Overview

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

Functions

`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:ParseError: KaTeX parse error: Undefined control sequence: \$ at position 1: \̲$̲ -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$ .

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)

`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}.

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)

`spider_nest`

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

In [4]:

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

In [23]:

spider_nest(graphs.CycleGraph(4))

`pleat`

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.

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

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

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(C_3) \mod Null(C_3) \cong Aut(C_3)$ . We know this is true because $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(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).

In [0]: