Notebook Summary
The purpose of this notebook is a continuation of ES1_1, which introduced some basic properties of graphs and provided examples and proofs that demonstrated these properties.
These notes are based on Prof. Norman Wildberger's lectures on Dynamics on Graphs which can be found here.
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
import string
Observe: Recall that the population function (introduced in ES1_1), $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}$
Let $F1$ be an implementation of the population function $ps_x$
def F1(graph, nodeChoice, printSummary = True,
returnUpdatedGraph = False,
returnListOfPopulations = False,
returnAllAsDict = False):
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")
if returnUpdatedGraph:
return(updatedGraph)
if returnListOfPopulations:
return(np.array(newPopulations))
if returnAllAsDict:
return({"graph": updatedGraph,
"population": np.array(newPopulations)})
Observe: The first property was demonstrated in the previous notebook (ES1_1). The second propert,y, $s_x^2 \equiv \text{Identity}$ can be demonstrated using the following example
Let $a, b, c$ and $d$
a, b, c, d = sp.symbols('a, b, c, d')
F2 = [
("x", {"population": a}),
("y", {"population": b}),
("z", {"population": c}),
("w", {"population": d})]
F3 = [("x","y"),
("y","z"),
("y","w"),
("w","z")]
F4 = nx.Graph()
F4.add_nodes_from(F2)
F4.add_edges_from(F3)
Let: $F5$ be the application fo $S_x^2$
F5 = F1(F1(F4, 'x', returnUpdatedGraph=True), 'x', returnUpdatedGraph=True)
[F5.nodes[i]['population'] for i in F5]
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': -a + b}
Change in node population -a + b -> a
Updated node populations of graph: [a, b, c, d]
[a, b, c, d]
Observe: that $F5$ proves property 2.
Observe: To test property 3, a function is required that returns a list of non-neighboring vertices for any given vertice in a graph.
Let: Let $F6$ be a function that returns all non neighboring vertices for all vertices on a graph.
def F6(graph):
listOfNonNeigbors = []
nodes = list(graph.nodes)
for x in nodes:
y = [i for i in nx.non_neighbors(F5, x)]
listOfNonNeigbors.append({x: y})
return(listOfNonNeigbors)
Let $F7$ be a list of all non-neighboring vertices for each vertice in $F4$
F7 = F6(F4)
F7
[{'x': ['z', 'w']}, {'y': []}, {'z': ['x']}, {'w': ['x']}]
Let $F8$ be a function that tests commutativity between graph vertices and non-neighboring vertices.
def F8(graph, printSummary = True):
commutativityCheck = True
listOfNonNeighbors = F6(graph)
for i in listOfNonNeighbors:
currentVertice = list(i.keys())[0]
currentNonNeighbors = list(i.values())[0]
for nonNeighbor in currentNonNeighbors:
currentVerticeMutation = F1(graph, currentVertice, returnUpdatedGraph=False, returnListOfPopulations=True, printSummary = False)
nonNeighborMutation = F1(graph, nonNeighbor, returnUpdatedGraph=False, returnListOfPopulations=True, printSummary = False)
if printSummary:
print("\nCurrent vertice * non-neighboring vertice: ", currentVerticeMutation * nonNeighborMutation)
print("Non-neighboring vertice * current vertice: ", nonNeighborMutation * currentVerticeMutation)
equalityCheck = currentVerticeMutation * nonNeighborMutation == nonNeighborMutation * currentVerticeMutation
for k in equalityCheck:
if not k:
commutativityCheck = False
return(commutativityCheck)
Let $F9$ be a verification of commutativity between graph vertices and non-neighboring vertices
F9 = F8(F4)
Current vertice * non-neighboring vertice: [a*(-a + b) b**2 c*(b - c + d) d**2] Non-neighboring vertice * current vertice: [a*(-a + b) b**2 c*(b - c + d) d**2] Current vertice * non-neighboring vertice: [a*(-a + b) b**2 c**2 d*(b + c - d)] Non-neighboring vertice * current vertice: [a*(-a + b) b**2 c**2 d*(b + c - d)] Current vertice * non-neighboring vertice: [a*(-a + b) b**2 c*(b - c + d) d**2] Non-neighboring vertice * current vertice: [a*(-a + b) b**2 c*(b - c + d) d**2] Current vertice * non-neighboring vertice: [a*(-a + b) b**2 c**2 d*(b + c - d)] Non-neighboring vertice * current vertice: [a*(-a + b) b**2 c**2 d*(b + c - d)]
Observe: Property 3 is verified for this graph
Observe: Property 4 (the braid relation) states that, if $x$ and $y$ are neighbors, then $ S_x S_y S_x = S_y S_x S_y $. This can be verified in the example below.
Let $F12$ be an example showing the result of applying the left hand side of property $4$ using the graph $F4$.
F10 = F1(F4, "x", returnUpdatedGraph=True)
F11 = F1(F10, "y", returnUpdatedGraph=True)
F12 = F1(F11, "x", returnUpdatedGraph=True)
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 y
Node details {'population': b}
Change in node population b -> -a + c + d
Updated node populations of graph: [-a + b, -a + c + d, c, d]
Node choice x
Node details {'population': -a + b}
Change in node population -a + b -> -b + c + d
Updated node populations of graph: [-b + c + d, -a + c + d, c, d]
Let $F15$ be the result of applying the right hand side of property $4$ using the graph $F4$.
F13 = F1(F4, "y", returnUpdatedGraph=True)
F14 = F1(F13, "x", returnUpdatedGraph=True)
F15 = F1(F14, "y", returnUpdatedGraph=True)
Node choice y
Node details {'population': b}
Change in node population b -> a - b + c + d
Updated node populations of graph: [a, a - b + c + d, c, d]
Node choice x
Node details {'population': a}
Change in node population a -> -b + c + d
Updated node populations of graph: [-b + c + d, a - b + c + d, c, d]
Node choice y
Node details {'population': a - b + c + d}
Change in node population a - b + c + d -> -a + c + d
Updated node populations of graph: [-b + c + d, -a + c + d, c, d]
Observe: that the example supports property 4, that $ S_x S_y S_x = S_y S_x S_y $
Aim Introduce the idea of a Root System
Definition: For a simple graph with a singleton graph population, the root of this graph, here denoted $X$, is any population that is obtainable from any number of successive mutations (i.e. successive applications of the function $ps_x$ a singleton population)
Definition All the possible roots of the graph can be denoted as $R(X)$
Observe: A critical question in the study of graphs asks: which simple graphs, denoted $X$ have a finite number of roots or root populations?
Observe: Whether or not a graph has a finite number of root populations will depend on the structure of the graphs.
Observe Consider the example below with successive applications.
Let $F18$ be a new graph with a singleton population, visualised with $F19$.
F16 = [
("x", {"population": 0}),
("y", {"population": 1}),
("z", {"population": 0}),
("w", {"population": 0})]
F17 = [("x","y"),
("y","z"),
("y","w"),
("w","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')
Let $F20$ be a function that that applied the population transformation function, $ps_x$ to a graph over a chosen number of iterations for a chosen list of verticies
def F20(graphChoice, vertices, iterations, returnSetOfAllPopulations = True):
setOfAllPopulations = []
graph = graphChoice
for i in range(iterations):
for j in vertices:
udpatedGraphAndPopulation = F1(graph, j, returnAllAsDict=True, printSummary = False)
graph = udpatedGraphAndPopulation['graph']
population = udpatedGraphAndPopulation['population']
setOfAllPopulations.append(population)
print("Number of unique populations: ", len(list(set([tuple(i) for i in [list(i) for i in setOfAllPopulations]]))))
if returnSetOfAllPopulations:
return(setOfAllPopulations)
Let $F21$ be the successive application of $F20$.
F21 = F20(F18, ['x', 'w', 'z', 'y'], 5)
F21
Number of unique populations: 20
[array([1, 1, 0, 0]), array([1, 1, 0, 1]), array([1, 1, 2, 1]), array([1, 3, 2, 1]), array([2, 3, 2, 1]), array([2, 3, 2, 4]), array([2, 3, 5, 4]), array([2, 8, 5, 4]), array([6, 8, 5, 4]), array([6, 8, 5, 9]), array([ 6, 8, 12, 9]), array([ 6, 19, 12, 9]), array([13, 19, 12, 9]), array([13, 19, 12, 22]), array([13, 19, 29, 22]), array([13, 45, 29, 22]), array([32, 45, 29, 22]), array([32, 45, 29, 52]), array([32, 45, 68, 52]), array([ 32, 107, 68, 52])]
Observe: There appears to be non-finite number of root populations.
Observe: Consider a second example, which resemembles an $A_n$ graph
Let: $F24$ be a $A_n$ simple graph with a singleton population, visualised in $F25$
F22 = [
("u", {"population": 0}),
("v", {"population": 1}),
("w", {"population": 0}),
("x", {"population": 0}),
("y", {"population": 0}),
("z", {"population": 0}),]
F23 = [("u","v"),
("v","w"),
("w","x"),
("x","y"),
("y","z")]
F24 = nx.Graph()
F24.add_nodes_from(F22)
F24.add_edges_from(F23)
F25 = nt.Network(width = "600px", notebook = True)
F25.from_nx(F24)
F25.show('nx.html')
Let $F26$ be number of unique root populations obtained from 50 iterations of the function $F20$ with the duplicate results removed.
F26 = F20(F24, ['u', 'v', 'w', 'x', 'y', 'z'], 50)
Number of unique populations: 22
Observe: It can be seen when increasing the number of iterations, the maximum it appears to reach will be 22 root populations
[F20(F24, ['u', 'v', 'w', 'x', 'y', 'z'], i, returnSetOfAllPopulations=False) for i in range(10)]
Number of unique populations: 0 Number of unique populations: 2 Number of unique populations: 8 Number of unique populations: 14 Number of unique populations: 16 Number of unique populations: 18 Number of unique populations: 20 Number of unique populations: 22 Number of unique populations: 22 Number of unique populations: 22
[None, None, None, None, None, None, None, None, None, None]
Observe: that after 7 iterations for $A_6$ graph, 22 unique results are always returned
Let $F27$ be a function to create graphs with a given population and edges to faciliate testing the root populations of different graph types.
def F27(population, edges):
numberOfVerticies = len(edges) + 1
verticeLabels = list(string.ascii_lowercase)[0:numberOfVerticies]
vertices = [(verticeLabels[i], {"population": population[i]}) for i in range(numberOfVerticies)]
graph = nx.Graph()
graph.add_nodes_from(vertices)
graph.add_edges_from(edges)
return(graph)
Let $F28$ be an example of an $A_8$ population.
F28 = F27([0, 1, 0, 0, 0, 0, 0, 0], [("a","b"),("b","c"),("c","d"),("d","e"),("e","f"), ("f","g"), ("g","h")] )
Let $F29$ be another example of a $A_n$ graph, with 8 vertices.
Observe: that the order of mutations can be changed but it appears the same ceiling value will be reached.
F29 = [F20(F28, ['a', 'b', 'd', 'c', 'e', 'f', 'h', 'g'], i) for i in range(12)]
print()
F30 = [F20(F28, ['b', 'a', 'd', 'c', 'e', 'f', 'h', 'g'], i) for i in range(12)]
print()
F31 = [F20(F28, ['b', 'a', 'd', 'e', 'c', 'f', 'g', 'h'], i) for i in range(12)]
Number of unique populations: 0 Number of unique populations: 2 Number of unique populations: 5 Number of unique populations: 12 Number of unique populations: 17 Number of unique populations: 19 Number of unique populations: 22 Number of unique populations: 24 Number of unique populations: 27 Number of unique populations: 30 Number of unique populations: 30 Number of unique populations: 30 Number of unique populations: 0 Number of unique populations: 3 Number of unique populations: 8 Number of unique populations: 11 Number of unique populations: 16 Number of unique populations: 18 Number of unique populations: 21 Number of unique populations: 24 Number of unique populations: 27 Number of unique populations: 30 Number of unique populations: 30 Number of unique populations: 30 Number of unique populations: 0 Number of unique populations: 3 Number of unique populations: 9 Number of unique populations: 12 Number of unique populations: 17 Number of unique populations: 19 Number of unique populations: 21 Number of unique populations: 24 Number of unique populations: 27 Number of unique populations: 30 Number of unique populations: 30 Number of unique populations: 30
Observe: The graph $D_6$ can also be explored.
F32 = F27([0, 0, 0, 0, 1, 0], [("a","b"),("b","c"),("c","d"),("c","e"),("e","f")] )
F33 = [F20(F32, ['a', 'b', 'd', 'c', 'e', 'f'], i) for i in range(15)]
print()
Number of unique populations: 0 Number of unique populations: 3 Number of unique populations: 7 Number of unique populations: 10 Number of unique populations: 13 Number of unique populations: 14 Number of unique populations: 16 Number of unique populations: 21 Number of unique populations: 25 Number of unique populations: 28 Number of unique populations: 31 Number of unique populations: 35 Number of unique populations: 36 Number of unique populations: 36 Number of unique populations: 36