Harmonic morphisms to P_4 – examples

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph \Gamma_2=P_4.
path4-0123

We only consider the cyclic graph on k vertices, C_k as the domain in this post. There are no non-trivial harmonic morphisms C_5 \to P_4, so we start with C_6. We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: \phi:\Gamma_1\to \Gamma_2=P_4 sends the red vertices in \Gamma_1 to the red vertex of \Gamma_2=P_4 (we let 3 be the numerical notation for the color red), the blue vertices in \Gamma_1 to the blue vertex of \Gamma_2=P_4 (we let 2 be the numerical notation for the color blue), the green vertices in \Gamma_1 to the green vertex of \Gamma_2=P_4 (we let 1 be the numerical notation for the color green), and the white vertices in \Gamma_1 to the white vertex of \Gamma_2=P_4 (we let 0 be the numerical notation for the color white).

To get the following data, I wrote programs in Python using SageMath.

Example 1: There are only the 4 trivial harmonic morphisms C_6 \to P_4, plus that induced by f = (1, 2, 3, 2, 1, 0) and all of its cyclic permutations (4+6=10). This set of 6 permutations is closed under the automorphism of P_4 induced by the transposition (0,3)(1,2) (so total = 10).cyclic6-123210

Example 2: There are only the 4 trivial harmonic morphisms, plus f = (1, 2, 3, 2, 1, 0, 0) and all of its cyclic permutations (4+7=11). This set of 7 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (2, 1, 0, 1, 2, 3, 3) and all 7 of its cyclic permutations (total = 7+11 = 18).
cyclic7-1232100
cyclic7-1233210

Example 3: There are only the 4 trivial harmonic morphisms, plus f = (1, 2, 3, 2, 1, 0, 0, 0) and all of its cyclic permutations (4+8=12). This set of 8 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 3, 2, 1, 0) and all of its cyclic permutations (12+8=20). In addition, there is f = (1, 2, 3, 3, 2, 1, 0, 0) and all of its cyclic permutations (20+8 = 28). The latter set of 8 cyclic permutations of (1, 2, 3, 3, 2, 1, 0, 0) is closed under the transposition (0,3)(1,2) (total = 28).
cyclic8-12321000
cyclic8-12333210
cyclic8-12332100

Example 4: There are only the 4 trivial harmonic morphisms, plus f = (1, 2, 3, 2, 1, 0, 0, 0, 0) and all of its cyclic permutations (4+9=13). This set of 9 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 2, 1, 0, 0, 0) and all 9 of its cyclic permutations (9+13 = 22). This set of 9 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 3, 2, 1, 0, 0) and all 9 of its cyclic permutations (9+22 = 31). This set of 9 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 3, 3, 2, 1, 0) and all 9 of its cyclic permutations (total = 9+31 = 40). cyclic9-123210000cyclic9-123321000cyclic9-123332100cyclic9-123333210

Harmonic morphisms to P_3 – examples

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph \Gamma_2=P_3.

The path graph P_3

If \Gamma_1 = (V_1, E_1) and \Gamma_2 = (V_2, E_2) are graphs then a map \phi:\Gamma_1\to \Gamma_2 (that is, \phi: V_1\cup E_1\to V_2\cup E_2) is a morphism provided

  1. if \phi sends an edge to an edge then the edges vertices must also map to each other: e=(v,w)\in E_1 and \phi(e)\in E_2 then \phi(e) is an edge in \Gamma_2 having vertices \phi(v)\in V_2 and \phi(w)\in V_2, where \phi(v)\not= \phi(w), and
  2. if \phi sends an edge to a vertex then the edges vertices must also map to that vertex: if e=(v,w)\in E_1 and \phi(e)\in V_2 then \phi(e) = \phi(v) = \phi(w).

As a non-example, if \Gamma_1 is a planar graph, if \Gamma_2 is its dual graph, and if \phi:\Gamma_1\to\Gamma_2 is the dual map V_1\to E_2 and E_1\to V_2, then \phi is not a morphism.

Given a map \phi_E : E_1 \rightarrow E_2 \cup V_2, an edge e_1 is called horizontal if \phi_E(e_1) \in E_2 and is called vertical if \phi_E(e_1) \in V_2. We say that a graph morphism \phi: \Gamma_1 \rightarrow \Gamma_2 is a graph homomorphism if \phi_E (E_1) \subset E_2. Thus, a graph morphism is a homomorphism if it has no vertical edges.

Suppose that \Gamma_2 has at least one edge. Let Star_{\Gamma_1}(v) denote the star subgraph centered at the vertex v. A graph morphism \phi : \Gamma_1 \to \Gamma_2 is called harmonic if for all vertices v \in V(\Gamma_1), the quantity
\mu_\phi(v,f)= |\phi^{-1}(f) \cap Star_{\Gamma_1}(v)|
(the number of edges in \Gamma_1 adjacent to v and mapping to the edge f in \Gamma_2) is independent of the choice of edge f in Star_{\Gamma_2}(\phi(v)).

An example of a harmonic morphism can be described in the plot below as follows: \phi:\Gamma_1\to \Gamma_2=P_3 sends the red vertices in \Gamma_1 to the red vertex of \Gamma_2=P_3, the green vertices in \Gamma_1 to the green vertex of \Gamma_2=P_3, and the white vertices in \Gamma_1 to the white vertex of \Gamma_2=P_3.

Example 1:

P3-C3-V

Example 2:
D3-2110

Example 3:
cyclic4-2101

Examples of graph-theoretic harmonic morphisms using Sage

In the case of simple graphs (without multiple edges or loops), a map f between graphs \Gamma_2 = (V_2,E_2) and \Gamma_1 = (V_1, E_1) can be uniquely defined by specifying where the vertices of \Gamma_2 go. If n_2 = |V_2| and n_1 = |V_1| then this is a list of length n_2 consisting of elements taken from the n_1 vertices in V_1.

Let’s look at an example.

Example: Let \Gamma_2 denote the cube graph in {\mathbb{R}}^3 and let \Gamma_1 denote the “cube graph” (actually the unit square) in {\mathbb{R}}^2.

This is the 3-diml cube graph

This is the 3-diml cube graph \Gamma_2 in Sagemath

The cycle graph on 4 vertices

The cycle graph \Gamma_1 on 4 vertices (also called the cube graph in 2-dims, created using Sagemath.

We define a map f:\Gamma_2\to \Gamma_1 by

f = [[‘000’, ‘001’, ‘010’, ‘011’, ‘100’, ‘101’, ‘110’, ‘111’], [“00”, “00”, “01”, “01”, “10”, “10”, “11”, “11”]].

Definition: For any vertex v of a graph \Gamma, we define the star St_\Gamma(v) to be a subgraph of \Gamma induced by the edges incident to v. A map f : \Gamma_2 \to \Gamma_1 is called harmonic if for all vertices v' \in V(\Gamma_2), the quantity

|\phi^{-1}(e) \cap St_{\Gamma_2}(v')|

is independent of the choice of edge e in St_{\Gamma_1}(\phi(v')).

 
Here is Python code in Sagemath which tests if a function is harmonic:

def is_harmonic_graph_morphism(Gamma1, Gamma2, f, verbose = False):
    """
    Returns True if f defines a graph-theoretic mapping
    from Gamma2 to Gamma1 that is harmonic, and False otherwise. 

    Suppose Gamma2 has n vertices. A morphism 
              f: Gamma2 -> Gamma1
    is represented by a pair of lists [L2, L1],
    where L2 is the list of all n vertices of Gamma2,
    and L1 is the list of length n of the vertices
    in Gamma1 that form the corresponding image under
    the map f.

    EXAMPLES:
        sage: Gamma2 = graphs.CubeGraph(2)
        sage: Gamma1 = Gamma2.subgraph(vertices = ['00', '01'], edges = [('00', '01')])
        sage: f = [['00', '01', '10', '11'], ['00', '01', '00', '01']]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        True
        sage: Gamma2 = graphs.CubeGraph(3)
        sage: Gamma1 = graphs.TetrahedralGraph()
        sage: f = [['000', '001', '010', '011', '100', '101', '110', '111'], [0, 1, 2, 3, 3, 2, 1, 0]]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        True
        sage: Gamma2 = graphs.CubeGraph(3)
        sage: Gamma1 = graphs.CubeGraph(2)
        sage: f = [['000', '001', '010', '011', '100', '101', '110', '111'], ["00", "00", "01", "01", "10", "10", "11", "11"]]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        True
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f, verbose=True)
        This [, ]] passes the check: ['000', [1, 1]]
        This [, ]] passes the check: ['001', [1, 1]]
        This [, ]] passes the check: ['010', [1, 1]]
        This [, ]] passes the check: ['011', [1, 1]]
        This [, ]] passes the check: ['100', [1, 1]]
        This [, ]] passes the check: ['101', [1, 1]]
        This [, ]] passes the check: ['110', [1, 1]]
        This [, ]] passes the check: ['111', [1, 1]]
        True
        sage: Gamma2 = graphs.TetrahedralGraph()
        sage: Gamma1 = graphs.CycleGraph(3)
        sage: f = [[0,1,2,3],[0,1,2,0]]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        False
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f, verbose=True)
        This [, ]] passes the check: [0, [1, 1]]
        This [, ]] fails the check: [1, [2, 1]]
        This [, ]] fails the check: [2, [2, 1]]
        False

    """
    V1 = Gamma1.vertices()
    n1 = len(V1)
    V2 = Gamma2.vertices()
    n2 = len(V2)
    E1 = Gamma1.edges()
    m1 = len(E1)
    E2 = Gamma2.edges()
    m2 = len(E2)
    edges_in_common = []
    for v2 in V2:
        w = image_of_vertex_under_graph_morphism(Gamma1, Gamma2, f, v2)
        str1 = star_subgraph(Gamma1, w)
        Ew = str1.edges()
        str2 = star_subgraph(Gamma2, v2)
        Ev2 = str2.edges()
        sizes = []
        for e in Ew:
            finv_e = preimage_of_edge_under_graph_morphism(Gamma1, Gamma2, f, e)
            L = [x for x in finv_e if x in Ev2]
            sizes.append(len(L))
            #print v2,e,L
        edges_in_common.append([v2, sizes])
    ans = True
    for x in edges_in_common:
        sizes = x[1]
        S = Set(sizes)
        if S.cardinality()>1:
            ans = False
            if verbose and ans==False:
                print "This [, ]] fails the check:", x
        if verbose and ans==True:
            print "This [, ]] passes the check:", x
    return ans
            

For further details (e.g., code to

star_subgraph

, etc), just ask in the comments.