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

Paley graphs in Sage

Let $q$ be a prime power such that $q\equiv 1 \pmod 4$. Note that this implies that the unique finite field of order $q$, $GF(q)$, has a square root of $-1$. Now let $V=GF(q)$ and

$E = \{(a,b)\in V\times V\ |\ a-b\in GF(q)^2\}.$
By hypothesis, $(a,b)\in E$ if and only if $(b,a)\in E$. By definition $G = (V, E)$ is the Paley graph of order $q$.

Paley was a brilliant mathematician who died tragically at the age of 26. Paley graphs are one of the many spin-offs of his work. The following facts are known about them.

1. The eigenvalues of Paley graphs are $\frac{q-1}{2}$ (with multiplicity $1$) and
$\frac{-1 \pm \sqrt{q}}{2}$ (both with multiplicity $\frac{q-1}{2}$).
2. It is known that a Paley graph is a Ramanujan graph.
3. It is known that the family of Paley graphs of prime order is a vertex expander graph family.
4. If $q=p^r$, where $p$ is prime, then $Aut(G)$ has order $rq(q-1)/2$.

Here is Sage code for the Paley graph (thanks to Chris Godsil, see [GB]):

def Paley(q):
K = GF(q)
return Graph([K, lambda i,j: i != j and (i-j).is_square()])



(Replace “K” by “$K.\langle a\rangle$” above; I was having trouble rendering it in html.) Below is an example.

sage: X = Paley(13)
sage: X.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: X.is_vertex_transitive()
True
sage: X.degree_sequence()
[6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
sage: X.spectrum()
[6, 1.302775637731995?, 1.302775637731995?, 1.302775637731995?,
1.302775637731995?, 1.302775637731995?, 1.302775637731995?,
-2.302775637731995?, -2.302775637731995?, -2.302775637731995?,
-2.302775637731995?, -2.302775637731995?, -2.302775637731995?]
sage: G = X.automorphism_group()
sage: G.cardinality()
78



We see that this Paley graph is regular of degree $6$, it has only three distinct eigenvalues, and its automorphism group is order $13\cdot 12/2 = 78$.

Here is an animation of this Paley graph:

The frames in this animation were constructed one-at-a-time by deleting an edge and plotting the new graph.

Here is an animation of the Paley graph of order $17$:

The frames in this animation were constructed using a Python script:

X = Paley(17)
E = X.edges()
N = len(E)
EC = X.eulerian_circuit()
for i in range(N):
X.plot(layout="circular", graph_border=True, dpi=150).save(filename="paley-graph_"+str(int("1000")+int("%s"%i))+".png")
X.delete_edge(EC[i])
X.plot(layout="circular", graph_border=True, dpi=150).save(filename="paley-graph_"+str(int("1000")+int("%s"%N))+".png")


Instead of removing the frames “by hand” they are removed according to their occurrence in a Eulerian circuit of the graph.

Here is an animation of the Paley graph of order $29$:

[GB] Chris Godsil and Rob Beezer, Explorations in Algebraic Graph Theory with Sage, 2012, in preparation.