# 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$.

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

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

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

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

# 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$.

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:

Example 2:

Example 3:

# 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 $\Gamma_2$ in Sagemath

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