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


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

Observe: Simple graphs can be categorised into 3 types:

  1. ADE graphs
  2. ADE~ graphs
  3. All other simple graphs

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.

Observe Multigraphs can also be characterised into the following types:

  1. BCFG Graphs
  2. BCFG~ graphs
  3. All other directed multigraphs


Aim: Explore the properties of simple graphs


Let $F12$ be a simple graph with the of vertices, $F9$, and the set of edges, $F10$ to be used as a motivating example.

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.

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}]$

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

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$

Observe: The mutation function $F20$ can be applied at each vertice.


Aim: Demonstrate the properties of the mutation function on simple graphs


Observe: the population function , $ps_x$ has the following properties:

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

  2. $s_x^2 \equiv \text{Identity}$. Performing the same mutation in succession will produce the original graph population.

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

  1. (The braid relation) If $x$ and $y$ are neighbors, then:
$$ S_x S_y S_x = S_y S_x S_y $$

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.

Let $F31$ be the addition of graph populations fo the $F27$ and $F30$

Let $F34$ be the a graph population created from $F31$, being the addition of $F27$ and $F30$

Let $F35$ be the addtion of populations of $F27$ and $F30$ after applying the mutation on $x$

Let $F38$ be mutation of $F34$ on the vertice $x$

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

Let: $F41$ and $F44$ be graphs with given populations created from unknown types.

Let $F45$ be the addition of graph populations fo the $F41$ and $F44$

Let $F48$ be the a graph population created from $F31$, being the addition of $41$ and $F44$

Let $F51$ be the updated populations of $F27$ and $F30$ after applying the mutation on $x$

Let $F52$ be mutation of $F48$ on the vertice $x$

Observe that as $F51 = F52$ so this property can be satisfied algebraically.