Notebook Summary
The purpose of this notebook is to introduce some basic properties of graphs and provide examples and proofs that demonstrate these properties. It will also introduce the "mutation game" which can be used to demonstrate these properties.
These notes are based on Prof. Norman Wildberger's lectures on Dynamics on Graphs which can be found here. Note that the notes for this lecture have been spread ovver two notebooks (ES1_1, ES1_2)
They notes are are being hosted at my website ladatavita.com and the Jupyter notebook is also available from my Github repo at: https://github.com/jgab3103/Jamie-Gabriel/tree/main/MathNotebooks
import pyvis.network as nt
import numpy as np
import sympy as sp
from IPython.display import HTML
import ipywidgets as widgets
import matplotlib as mpl
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
mpl.rcParams['legend.fontsize'] = 10
import pandas as pd
import networkx as nx
Aim: Provide a foundational intuition of graphs using the mutation game.
Reference: The Mutation Game, Coxeter–Dynkin Graphs, and Generalized Root Systems, Normal Wildberger, March 2020.
Observe: A good introduction to the structure and properties of graphs can be found in the mutation game, presented in the Reference above.
Observe: The mutation game that can intuited as having two "levels". The first level takes place on some simple graph, here denoted $X$. $X$ is a graph that has the following properties:
Let $F4$ be a visualisation of a simple graph, created from the set of verticies $F1$ and the set of edges $F2$.
F1 = {'1', '2', '3', '4'}
F2 = [('1','2'),
('2','3'),
('2','4'),
('3','4')]
F3 = nx.Graph()
F3.add_nodes_from(F1)
F3.add_edges_from(F2)
F4 = nt.Network(width = "600px", notebook = True)
F4.from_nx(F3)
F4.show('nx.html')
Observe: Simple graphs can be categorised into 3 types:
Observe: The second level of the mutation game allows for the use of directed graphs, or multigraphs. Edges have directions, multiple edges are allowed and loops are allowed.
Observe: Mutigraphs can be viewed as an extension of simple graphs, meaning that second level of the mutation game can be regarded as an extension of level one.
Let $F8$ be a visualisation of a multigraph with directed edges and self loops.
F5 = {'1', '2', '3', '4'}
F6 = [('1','2'),
('2','3'),
('2','4'),
('2','4'),
('3','4'),
('1', '1')]
F7 = nx.DiGraph()
F7.add_nodes_from(F5)
F7.add_edges_from(F6)
F8 = nt.Network(width = "600px", notebook = True, directed = True)
F8.from_nx(F7)
F8.show('nx.html')
Observe Multigraphs can also be characterised into the following types:
Let $F12$ be a simple graph with the of vertices, $F9$, and the set of edges, $F10$ to be used as a motivating example.
F9 = {'x', 'y', 'w', 'z'}
F10 = [('x','y'),
('y','z'),
('y','w'),
('w','z')]
F11 = nx.Graph()
F11.add_nodes_from(F9)
F11.add_edges_from(F10)
F12 = nt.Network(width = "600px", notebook = True)
F12.from_nx(F11)
F12.show('nx.html')
Observe: The vertices, $F9$ visualised in the above example, can be given the structure of an unordered set which can be denoted as $\{\text{ x } \text{ y } \text{ z } \text{ w }\}$
Observe The edges, $F10$, of the above example, are an unordered set of unordered sets, $\{ \{\text{ x y }\} \{\text{ y z }\} \{\text{ z w }\} \{\text{ z w }\}\}$. $F10$ can also be denoted as also a 2-set of vertices.
Observe: From a combinatorial point of view, any graph ($X$) can be denoted as an ordered pair of vertices ($V$) and edges ($E$):
$$X = \{ V, E\} $$Definition: For any given vertice, $i$, in a simple graph, $N(i)$ is the unordered set of neighbouring vertices, which is an unordered set of those vertices connected to the $i$ by a single edge, denoted as $N(x) = \{y\} $ or $N(y) = \{ \text{x z w}\} $
Definition A graph population for some simple graph, often denoted $X$ is an integer valued function on the vertices.
Definition A vertex population for some vertex on a simple graph is the result of the integer valued function on a specific vertex.
Let $F15$ be a simple graph where vertices have been given integer labels to denote population.
F12 = {'4:x', '3:y', '5:w', '-1:z'}
F13 = [('4:x','3:y'),
('3:y','-1:z'),
('3:y','5:w'),
('5:w','-1:z')]
F14 = nx.Graph()
F14.add_nodes_from(F12)
F14.add_edges_from(F13)
F15 = nt.Network(width = "600px", notebook = True)
F15.from_nx(F14)
F15.show('nx.html')
Observe: It is possible to impose order on vertices arbitrarily and $F15$ can be written as: $\{\text{x, y, z, w} \} $
Observe: The graph population of $F15$, can also be written as an arbitrarily ordered set: $ P = [4, 3, -1, 5] $
Definition: A Singleton Population is a graph population where all vertices have a an integer value of 0 except for a single vertice of of 1
Let $F19$ be an example of a singleton population, which an be arbitrarily ordered by the list $[\text{0, 0, 0, 1}]$
F16 = {'0:x', '0:y', '1:w', '0:z'}
F17 = [('0:x','0:y'),
('0:y','0:z'),
('0:y','1:w'),
('1:w','0:z')]
F18 = nx.Graph()
F18.add_nodes_from(F16)
F18.add_edges_from(F17)
F19 = nt.Network(width = "600px", notebook = True)
F19.from_nx(F18)
F19.show('nx.html')
Observe: There is the same number of singleton populations as there are vertices
Definition: The space of populations, usually deonoted $P(X)$ is a linear space over the integers (i.e. all possible graph populations on a graph). The Space of Populations has the following pointwise operations:
$P(X)$ can be intuited as a vector space whose basis consists of all singleton populations of a graph. Note it vector space over integers with basis being a $\{\text{set of singleton populations} \}$
Aim: Introduce the notion of a mutation
Defintion: A mutation is a transformation of a population of a vertex which will result in a changed graph and vertex population
Definition: If $x$ is a vertex of some simple graph $X$, then $S_x$ is defined as the mutation of $x$ which is a transformation of the vertex population of $x$ (which will also change the graph population).
If $p \in P(X) $ where $p$ is a population and $P(X)$ is the space of populations on a simple graph $X$ and $N(x)$ is the neighbouring vertices of $x$, then the population function, $ps_x$ on some population $y$ can be described as:
$$ ps_x(y) \equiv \begin{cases} -p(x) + \Sigma_{z \in N(x)} \text{ } p(z) & \text{if y = x}\\ p(y) & \text{if y $\ne$ x} \end{cases} $$Let F20 be a implementation of the population function $ps_x(y)$ for the case when $y=x$ (in the case where $y \ne x$, there is no population change).
def F20(graph, nodeChoice, printSummary = True, returnUpdatedGraph = True):
edgesOfChosenNode = list(nx.edges(graph, [nodeChoice]))
neigborOfChosenNode = [edgesOfChosenNode[i][1] for i in range(len(list(edgesOfChosenNode)))]
nodeChoicePopulation = graph.nodes[nodeChoice]['population']
sumOfNeighborsOfChosenNode = np.sum([graph.nodes[i]['population'] for i in neigborOfChosenNode])
populationOfNode = -nodeChoicePopulation + sumOfNeighborsOfChosenNode
updatedGraph = graph.copy()
updatedGraph.nodes[nodeChoice]['population'] = populationOfNode
newPopulations = [updatedGraph.nodes[i]['population'] for i in list(updatedGraph)]
if printSummary:
print("Node choice",
nodeChoice,
"\nNode details",
nx.nodes(graph)[nodeChoice],
"\nChange in node population ",
nx.nodes(graph)[nodeChoice]['population'],
"->",
populationOfNode)
print("Updated node populations of graph: ", newPopulations, "\n")
return(updatedGraph)
Observe: If $F23$ is a simple graph, each node can be mutated using the the population function $ps_x$, implemented in $F20$. This will result in new vertex populations for each node $x, y, z$ and $w$
F21 = [
("x", {"population": 4}),
("y", {"population": 3}),
("z", {"population": -1}),
("w", {"population": 5})]
F22 = [("x","y"),
("y","z"),
("y","w"),
("w","z")]
F23 = nx.Graph()
F23.add_nodes_from(F21)
F23.add_edges_from(F22)
F24 = nt.Network(width = "600px", notebook = True)
F24.from_nx(F23)
F24.show('nx.html')
Observe: The mutation function $F20$ can be applied at each vertice.
F20(F23, "x", returnUpdatedGraph=False)
F20(F23, "y", returnUpdatedGraph=False)
F20(F23, "z", returnUpdatedGraph=False)
F20(F23, "w", returnUpdatedGraph=False)
Node choice x Node details {'population': 4, 'size': 10} Change in node population 4 -> -1 Updated node populations of graph: [-1, 3, -1, 5] Node choice y Node details {'population': 3, 'size': 10} Change in node population 3 -> 5 Updated node populations of graph: [4, 5, -1, 5] Node choice z Node details {'population': -1, 'size': 10} Change in node population -1 -> 9 Updated node populations of graph: [4, 3, 9, 5] Node choice w Node details {'population': 5, 'size': 10} Change in node population 5 -> -3 Updated node populations of graph: [4, 3, -1, -3]
<networkx.classes.graph.Graph at 0x7f1ad12542b0>
Observe: the population function , $ps_x$ has the following properties:
If $p$ and $q$ are populations, $P(X)$ is a space of populations, and $p, q \in P(X)$, then $(p + q)s_x = ps_x + qs_x$ so it is a linear operator and can be applied pointwise and if $n \in \text{Int}$, then $(np)s_x = n(ps_x)$
$s_x^2 \equiv \text{Identity}$. Performing the same mutation in succession will produce the original graph population.
If $x$ and $y$ are non-neighboring vertices, then the $S_xS_y \equiv S_yS_x$, meaning they are commutative
Observe: A consequence of property $3$, it is the case that:
$$ (pS_x)S_y = p(S_xS_y) \equiv (pS_y)S_x = p(S_yS_x) $$Note that the mutation functino, $S_i$ is, by convention, written on the rhs of the populations it is are acting on. This means that However in general they do not have to
Observe: It can be shows that the relation $(S_xS_y)^3 = \text{identity}$
Observe: The first property can be tested using 2 graphs with different populations using the following example.
Let: $F27$ and $F30$ be graphs with given populations and recall that a graph population can be denoted as an ordered set of integers.
F25 = [
("x", {"population": 4}),
("y", {"population": 3}),
("z", {"population": -1}),
("w", {"population": 5})]
F26 = [("x","y"),
("y","z"),
("y","w"),
("w","z")]
F27 = nx.Graph()
F27.add_nodes_from(F25)
F27.add_edges_from(F26)
F28 = [
("x", {"population": 2}),
("y", {"population": 4}),
("z", {"population": 6}),
("w", {"population": -4})]
F29 = [("x","y"),
("y","z"),
("y","w"),
("w","z")]
F30 = nx.Graph()
F30.add_nodes_from(F28)
F30.add_edges_from(F29)
print("F27 graph population: ", [F27.nodes[i]['population'] for i in F27])
print("F30 graph population: ", [F30.nodes[i]['population'] for i in F30])
F27 graph population: [4, 3, -1, 5] F30 graph population: [2, 4, 6, -4]
Let $F31$ be the addition of graph populations fo the $F27$ and $F30$
F31 = np.array([F27.nodes[i]['population'] for i in F27]) + np.array([F30.nodes[i]['population'] for i in F30])
F31
array([6, 7, 5, 1])
Let $F34$ be the a graph population created from $F31$, being the addition of $F27$ and $F30$
F32 = [
("x", {"population": 6}),
("y", {"population": 7}),
("z", {"population": 5}),
("w", {"population": 1})]
F33 = [("x","y"),
("y","z"),
("y","w"),
("w","z")]
F34 = nx.Graph()
F34.add_nodes_from(F32)
F34.add_edges_from(F33)
Let $F35$ be the addtion of populations of $F27$ and $F30$ after applying the mutation on $x$
F35 = F20(F27, "x")
F36 = F20(F30, "x")
F37 = np.array([F35.nodes[i]['population'] for i in F35]) + np.array([F36.nodes[i]['population'] for i in F36])
F37
Node choice x Node details {'population': 4} Change in node population 4 -> -1 Updated node populations of graph: [-1, 3, -1, 5] Node choice x Node details {'population': 2} Change in node population 2 -> 2 Updated node populations of graph: [2, 4, 6, -4]
array([1, 7, 5, 1])
Let $F38$ be mutation of $F34$ on the vertice $x$
F38 = F20(F34, "x")
Node choice x Node details {'population': 6} Change in node population 6 -> 1 Updated node populations of graph: [1, 7, 5, 1]
Observe that as $F37 = F38$ this property is satisfied for this example.
Observe: It is also possible to show this algebraically.
Let: Let $a, b, c, d, e, f, g, h$ be unknown types
a, b, c, d, e, f, g, h = sp.symbols('a, b, c, d, e, f, g, h')
Let: $F41$ and $F44$ be graphs with given populations created from unknown types.
F39 = [
("x", {"population": a}),
("y", {"population": b}),
("z", {"population": c}),
("w", {"population": d})]
F40 = [("x","y"),
("y","z"),
("y","w"),
("w","z")]
F41 = nx.Graph()
F41.add_nodes_from(F39)
F41.add_edges_from(F40)
F42 = [
("x", {"population": e}),
("y", {"population": f}),
("z", {"population": g}),
("w", {"population": h})]
F43 = [("x","y"),
("y","z"),
("y","w"),
("w","z")]
F44 = nx.Graph()
F44.add_nodes_from(F42)
F44.add_edges_from(F33)
print("F41 graph population: ", [F41.nodes[i]['population'] for i in F41])
print("F44 graph population: ", [F44.nodes[i]['population'] for i in F44])
F41 graph population: [a, b, c, d] F44 graph population: [e, f, g, h]
Let $F45$ be the addition of graph populations fo the $F41$ and $F44$
F45 = np.array([F41.nodes[i]['population'] for i in F41]) + np.array([F44.nodes[i]['population'] for i in F44])
F45
array([a + e, b + f, c + g, d + h], dtype=object)
Let $F48$ be the a graph population created from $F31$, being the addition of $41$ and $F44$
F46 = [
("x", {"population": a + e,}),
("y", {"population": b + f}),
("z", {"population": c + g}),
("w", {"population": d + h})]
F47 = [("x","y"),
("y","z"),
("y","w"),
("w","z")]
F48 = nx.Graph()
F48.add_nodes_from(F46)
F48.add_edges_from(F47)
Let $F51$ be the updated populations of $F27$ and $F30$ after applying the mutation on $x$
F49 = F20(F41, "x")
F50 = F20(F44, "x")
F51 = np.array([F49.nodes[i]['population'] for i in F49]) + np.array([F50.nodes[i]['population'] for i in F50])
F51
Node choice x Node details {'population': a} Change in node population a -> -a + b Updated node populations of graph: [-a + b, b, c, d] Node choice x Node details {'population': e} Change in node population e -> -e + f Updated node populations of graph: [-e + f, f, g, h]
array([-a + b - e + f, b + f, c + g, d + h], dtype=object)
Let $F52$ be mutation of $F48$ on the vertice $x$
F52 = F20(F48, "x")
Node choice x Node details {'population': a + e} Change in node population a + e -> -a + b - e + f Updated node populations of graph: [-a + b - e + f, b + f, c + g, d + h]
Observe that as $F51 = F52$ so this property can be satisfied algebraically.