Dynamics on Graphs11

This video is part of the Dynamics on Graphs series, available to Members of the Wild Egg YouTube channel at https://www.youtube.com/channel/UCriF..., which explores remarkable exceptional structures in mathematics and physics associated to dynamics on graphs. We aim to develop a lot of fascinating mathematics with a minimum of mathematical and physical pre-requisites -- in particular no knowledge of Lie theory, Cayley numbers, Jordan algebras, conformal field theory etc. Patreon supporters also have access to this content.

In this video we introduce the Pentagon Game, which was Problem 3 from the 1986 International Mathematics Olympiad, and was contributed by Elias Wegert. This led to S. Mozes' generalization into what is now known as the Numbers Game, a dynamic game involving "firings" on a general graph.

The Pentagon Game Problem is well worth spending a few weeks thinking about (or a few hours, if you happen to be a brilliant math olympian). In fact we will see a variant of it emerge naturally at the end of this lecture.

Remarkably, the Numbers Game is exactly dual, in a precise sense, to the Mutation Game that we have been exploring so far in this series, yielding the remarkable mathematics around the ADE graphs and their affine variants.

In our approach, we want to emphasize this duality from the beginning, so we motivate the Numbers Game by looking at how mutations at different vertices naturally lead to a notion of a weight vector for a population on a graph. While this connects with the weight lattice in Lie theory, it should be kept in mind that the discussion here is much more general and applies to arbitrary simple graphs. In fact in subsequent lectures in this series, we will see how this all extends to directed graphs, and this will then also encompass the special series known as B,C,F and G in Lie theory.

To keep things down to earth, we proceed by explaining the duality via a concrete explicit example.

It is really important to understand these two games together -- they will be generating a huge amount of rich combinatorial structures, with lots of connections to other areas of mathematics and physics.

This is part of the Dynamics on Graphs series, available to Members of the Wild Egg YouTube channel at https://www.youtube.com/channel/UCriF....

*

Here are all the Insights into Mathematics Playlists:

Elementary Mathematics (K-6) Explained: https://www.youtube.com/playlist?

list=PL8403C2F0C89B1333

Year 9 Maths: https://www.youtube.com/playlist?list...

Ancient Mathematics: https://www.youtube.com/playlist?list...

Wild West Banking: https://www.youtube.com/playlist?list...

Sociology and Pure Mathematics: https://www.youtube.com/playlist?list...

Old Babylonian Mathematics (with Daniel Mansfield): https://www.youtube.com/playlist?

list=PLIljB45xT85CdeBmQZ2QiCEnPQn5KQ6ov

Math History: https://www.youtube.com/playlist?list...

Wild Trig: Intro to Rational Trigonometry: https://www.youtube.com/playlist?list...

MathFoundations: https://www.youtube.com/playlist?list...

Wild Linear Algebra: https://www.youtube.com/playlist?list...

Famous Math Problems: https://www.youtube.com/playlist?list...

Probability and Statistics: An Introduction: https://www.youtube.com/playlist?list...

Boole's Logic and Circuit Analysis: https://www.youtube.com/playlist?list...

Universal Hyperbolic Geometry: https://www.youtube.com/playlist?list...

Differential Geometry: https://www.youtube.com/playlist?list...

Algebraic Topology: https://www.youtube.com/playlist?list...

Math Seminars: https://www.youtube.com/playlist?list...

And here are some of the other Wild Egg Maths Playlists (some available only to Members!)

Solving Polynomial Equations: https://www.youtube.com/playlist?list...

Exceptional Structures in Maths and Physics via Dynamics on Graphs" https://www.youtube.com/playlist?list...

Triangle Centres: https://www.youtube.com/watch?v=iLBGX...

Six: An elementary course in pure mathematics: https://www.youtube.com/playlist?list...

Algebraic Calculus One: https://www.youtube.com/playlist?list...

Algebraic Calculus Two: https://www.youtube.com/playlist?list...

0:02

hello everyone i'm Norman Wildberger thanks for joining me on this adventure we are looking at

0:06

dynamics on graphs so today we're going to look at a very interesting new development i want

0:11

to introduce what's called the numbers game on a graph but there's actually another game that comes

0:16

before that which i'll mention called the pentagon game so these are uh in a quite very natural way

0:23

duels to the mutation game and it's going to be really important for us to to take these on board

0:28

so that we have a sort of balanced view of the the dynamics on a graph mutation game on one side

0:35

the numbers game on the other side okay so the very very interesting story here that really

0:41

starts with a an imo problem so imo stands for the international mathematics olympiad and in

0:48

1986 problem three of this this international competition was submitted by Elias Wegert and it's

0:56

a very interesting challenge problem it's actually probably one of the most difficult problems that's

1:02

appeared on the international mathematics olympiad and if you would like to know more about the story

1:08

of how this problem sort of generated a lot of interesting things i highly recommend the paper

1:13

relaxation procedures on graphs by E Wegert and C Rayer which appeared here in discrete applied math

1:20

2009 and it's available on sciencedirect so you can just download it directly okay so here is the

1:27

pentagon game okay and i want you to think about this because this is going to be very relevant

1:31

to our to our approach to dynamics on graphs okay so it's a very simple case but it's still

1:38

highly non-trivial so five integers with positive sum are assigned to the vertices of a pentagon

1:46

if there is at least one negative number the player may pick one of them say y

1:52

add it to its neighbors x and z because we're in a pentagon so any vertex has exactly two neighbors

2:00

and then reverse the sine of y okay so that's what you do you pick a negative number you add that

2:07

negative number to its direct neighbors and then you reverse the sign of y so it becomes positive

2:15

the game terminates when all the numbers are non-negative prove that this game must always

2:22

terminate so um a great exercise um challenging because international mathematics olympiad

2:32

problems are are challenging at best and this is one of the harder ones so it's well worth you know

2:38

being modest about trying to to solve it but i think it's really great for you to think about

2:43

it because it'll be a great introduction to this this whole approach of the numbers game so this

2:49

game was then extended by shahar moses to become the numbers game so quite a big generalization

2:56

and that was introduced in a paper in 1990 called reflection processes on graphs and while groups

3:04

in the journal of combinatorial theory and here it is there so we are very interested in these

3:09

these two games well the numbers game especially but the historical aspect of connecting with the

3:14

pentagon game is interesting too but we are going to look at the numbers game in a very

3:20

different way so i want to introduce this as essentially a dual game to the mutation game

3:28

so this will involve some some new objects which are sort of dual to populations so populations you

3:33

know are typically row vectors these dual objects are going to be column vectors and we'll call them

3:38

weight vectors or just weights so that has some resonance with people who know about lead theory

3:44

and there's some connection with the terminology that appears in lay theory but this is in fact

3:50

a much more general than what's happening there because it works pretty well for any graph okay so

3:54

i want to illustrate the story okay by looking at a specific example where i can illustrate things

4:01

very concretely so let's have a look at this favorite graph bars that we've seen a number

4:07

of times let's label it now as with verses 1 2 3 along the bottom and four up on top all right and

4:15

then the adjacency matrix will be this one here a okay so the first column you see the number one

4:21

is is connected with number two and in the second column number two or vertex two is connected with

4:27

1 3 and 4. and in the third column vertex 3 is connected with 2 and 4 and in the fourth column

4:34

vertex 4 is connected with 2 and 3. so that's the adjacency matrix of a graph since we're talking

4:39

about simple graphs here this is necessarily just consisting of zeros and ones and it's symmetric

4:46

okay so now population remember is just a function integer valued function on the vertices so that

4:53

can be now identified with a row vector because we've we've organized these vertices we basically

4:59

ordered them so one two three four so a population can then just be exhibited by the row vector which

5:05

just enumerates the the values at one two three and four say p1 p2 p3 p4

5:12

and let's just remind you that if you take this row vector and you multiply it by a

5:19

then um well you're getting sort of the each at each vertex position you're getting the sum of

5:27

the neighbors so at one you're getting you're getting p2 and at 2 you're getting p1 plus p3

5:33

plus p4 and so on and each of the columns of a is responsible for one of these entries

5:40

so so for example this p2 is is really coming from from this first column you know that's how

5:49

you multiply things and this one here is is coming from the second column and so on okay great now

5:57

corresponding to this graph there are mutations okay and these mutations i remind you um act on

6:06

populations they they change a population so if you mutate a population at say at the vertex 2

6:12

then something's going to happen at two and let me remind you what happens okay that first of

6:17

all the population at two negates and sort of to combat that each of the directly adjacent

6:26

vertices which in this case are one three and four will clone their populations and

6:31

send those populations down these roads into the mutating city to to to sort of cancel perhaps the

6:38

mutations that appear there okay so we've seen that when we express populations with vectors

6:45

like this then these mutations can be expressed with with matrices the matrices act on the right

6:53

of these row vectors okay so for example s1 is given by this matrix let's just actually

7:00

make some def let's clear definitions okay and i'm just going to make these definitions so that's s1

7:08

so we have that that's the mutation matrix for the mutation at first vertex here's s2

7:16

here's s3 and here's s4 let's just check that we have them there s1 s2 s3 s4 okay good

7:26

so for example if we take p this thing here okay p1 p2 p3 p4 a general population

7:35

and we act on it by s2 that is we multiply this row vector by the matrix on the right then we

7:42

get p1 p1 minus p2 plus p3 plus p4 p3 p4 so we see that we're just getting effectively the mutation

7:49

at the vertex 2. it's negated the population at 2 and it's added a copy of the neighboring

7:57

populations and let me remind you how you get one of these mutation matrices okay you can get a very

8:04

simple and direct way basically just if you have the adjacency matrix in front of you so

8:10

for example to get this s2 how do you how do you get that well you start with the identity matrix

8:16

in this case the four by four identity matrix has ones down the diagonal and then you change the one

8:22

in the i diagonal position i is two in this case so in the second position we change that one into

8:29

a minus one okay and then you're also going to change the elements in that corresponding column

8:36

through that diagonal entry by basically looking here to the adjacency matrix picking out that

8:44

second column and basically adding that second column to what you have here okay so there's

8:51

various zeros that were there and the zeros have been replaced with once so let's just show you

8:56

the same thing for s3 for example you start with the identity matrix you negate the third

9:02

diagonal entry so that becomes a minus one and then you look over here on the third

9:07

column of the adjacency matrix and you basically just add that to what we have over here so you're

9:12

adding the one here and the one here okay so it's very simple actually how to get these

9:17

mutation matrices basically just filling around the identity matrix and with the adjacency matrix

9:26

okay so now i want to introduce the weight vector w of a population

9:31

okay so i'm going to introduce this duality so for every population there is a corresponding

9:38

column vector called a weight or a weight vector and i want to you know proceed with an example

9:44

so suppose that we consider a particular population p on on this graph x up here and

9:50

let me just remind you maybe i'll just copy that just so it's clear in your mind

9:59

okay there's our graph all right okay so we have a population five four two minus one so there's

10:05

five but this vertex there's four at this vertex there's two with this vertex there's minus one

10:09

at this vertex four so now let's um let's copy that so now the computer knows where p is so i how

10:18

much well it went from five to minus one so all together the change is minus six okay what about

10:25

if we go back to the the population p and perform mutation s2 well we're getting 5 2 2 minus 1. so

10:35

none of them change except for the second one and that becomes a minus 4

10:40

and then we have to add minus 4 on the sum of the neighbors which is all of the above that's six so

10:47

minus four plus six is two that's where there's a two there okay so what happened to this entry

10:54

well the second entry when we perform the mutation s2 changes by

11:02

in this case -2 good okay what happens if we happen to do s3 to the original thing well we

11:10

get 5 4 it only changes here so the 2 changes to a one so we can say that the third entry

11:20

the third entry changes by the two goes to a minus one and finally if we do the fourth mutation

11:29

s4 then only the last entry changes the minus one goes to a seven and we can record that by saying

11:38

the fourth three changes by we went from minus one to seven so it's a change of eight

11:49

so suppose for example that you know your your aim was to play the mutation game in such a way as to

11:56

increase the population that's a kind of a nice orientation to have right we start with

12:01

the population we're interested in increasing the population by judiciously making mutations

12:07

so this information that's down here in this little column here it would be very convenient

12:12

for you because you you would know that if you're faced with this particular population

12:17

that these numbers would be telling you how much you can expect the population to change by

12:26

with respect to the successive mutations in this particular case all of the mutations decrease

12:34

the population except for the last one so if your your aim was to increase the population you know

12:41

that you would have to do an s4 to this particular thing okay so we record we record

12:49

all this information record this information by a well we'll call it a weight vector okay

12:59

so it records um records all the changes all the changes to the population

13:10

p for all possible mutations okay and we're going to make a vector

13:21

so let me take one of these maybe i'll take a transpose okay there's a vector there's a

13:28

column vector okay and what do i have to fill it with the first one will be -6

13:33

the next one minus two the next one minus one and the next one eight

13:41

okay so there is then a correspondence there is then a correspondence between the population

13:54

p

13:58

equals that and maybe we'll give this a name and say w for weight how's that

14:03

between the population p

14:08

and the corresponding weight

14:14

this thing maybe i'll make a new line so we can see both of them hopefully on the same thing right

14:18

so there is a correspondence between the population p and the corresponding weight w

14:28

here is the essential duality that's going to play a huge role okay so that now we

14:33

we have a kind of a balance situation we have this population but now we have a corresponding

14:40

weight sort of associated to it and now i'm going to um let's say i'm i'm interested in um

14:47

in in playing this mutation game and increasing the population so i've said that okay i should

14:52

really multiply by the mutation s4 here to increase the thing so so we saw

15:02

we saw that let's say q equals p of s4 so if we apply the mutation s4 to p we end up with this

15:13

population let's call it q all right let's now calculate what the associated what the associated

15:22

weight is for this q okay so this is a fun calculation let's find the corresponding weight

15:34

wait for q okay so what am i going to do well i'm going to first define q so over here

15:44

i will get rid of that and we'll just make a definition q

15:48

all right and now i'm basically going to copy the same thing that i did over here

15:55

three changes by how much um five goes to minus one um that five goes to minus one

16:02

that's a minus six that's the same thing it was once before okay what if we apply s2 to q okay

16:16

what has happened to the second entry so

16:18

going from 5 4 to 7 to 5 10 to 7 we see that the 4 has gone up to 10. so the second entry

16:30

changes by plus 6. okay good what if we do

16:37

mutation s3 we get five four nine seven then the third

16:45

the third entry went from two to nine all the others stay where they are which is a

16:50

change of seven and finally we do qs4 um the fourth entry has gone from seven to minus one

17:01

the fourth entry changes by from seven to minus one that's minus eight

17:11

okay so now we record this information we can just copy this thing here record this information by

17:19

a weight vector record all the changes to the population q now okay and what is this weight

17:24

vector uh the first one is minus six that hasn't changed then the minus two is now a six the minus

17:33

one here changed to a seven and this one changed to a minus eight okay so i'm going to copy this

17:45

so there's then a correspondence between the population uh q

17:51

which is 5 4 2 7

17:56

and the corresponding weight which is this one here maybe we'll call it something else

18:02

w say you all right

18:07

okay so now i want you to observe the relationship between these two things here okay

18:15

so we started with the population p and here were was its corresponding weight vector

18:20

and then we applied what did we actually apply we applied s4 right to get from p the

18:25

population p to the population q what happened uh to the s4 so that changed the fourth entry

18:33

okay now let's have a look at what happened to the corresponding weights the corresponding weight

18:37

went from w minus six minus two minus one seven to minus 6 6 7 minus 8. what's the relationship can

18:47

you see a relationship between this vector and this vector what's actually happened

18:54

and i better remind you about our graph we're actually looking at this graph

19:00

okay we're looking at the graph maybe i'll put it over here

19:07

and to go from p to q what we did is we changed we mutated at s at s4 at the vertex four okay that's

19:18

there's there's a there's a mutation s4 linking this thing to this thing okay so correspondingly

19:25

what is the relationship between this and this well it probably has something to do with the the

19:30

fourth the fourth entry increased by eight the minus two has gone to six that's also increased

19:36

by eight and notice that two is also a neighbor of four but the minus six at one has not changed

19:46

so the effect is well here's one way of explaining how to go from here to here okay that

19:52

what's happened is that we've taken this eight at vertex four and added it to each of its neighbors

20:04

added it to each of its neighbors and then

20:09

so and then negated the sign and then negated the side of it you see so that's somewhat sort

20:16

of opposite to what happens with the mutation right if we mutated a population at the vertex

20:21

4 then what would happen is that the the value at 4 would change sine yes but it's the directly

20:30

neighboring vertices that would add a copy of the and then negated the sign of it

20:38

you see so that's somewhat sort of opposite to what happens with the mutation right if we mutated

20:44

a population at the vertex 4 then what would happen is that the the value at 4 would change

20:51

sign yes but it's the directly neighboring vertices that would add a copy of their

21:00

population to four what's happening here now on this weight level is sort of some kind of sense

21:05

the opposite the weight value at the vertex in question does change sign just like in the other

21:10

case but before that happens that is copied to each of the direct directly adjacent neighbors

21:21

okay so this should sound very much like the pentagon game right does it sound very much

21:28

like it right in pentagon game what happened what happened to this value y well we add it to its

21:34

neighbors x and z and then we reverse the sine of y that's exactly what we're finding here so what's

21:41

happening with the pentagon game is the same kind of thing that's happening with these weights

21:51

all right so here's a great little exercise for you to see if you understand this and if you can

21:56

make it work for something else so suppose we want to increase the population here further right then

22:01

this weight vector will tell us the most efficient way of doing that is to mutate at the vertex 3

22:07

because that's going to result in the biggest increase in the population so you might try that

22:12

you could mutate at vertex 3 here and see what happens to the corresponding weight see if the the

22:22

the transition from this weight to the to the the weight of the new population is given by

22:29

the same kind of rule okay so this is opening up a whole new um sort of aspect to this dynamics on

22:38

the graphs story because now we have another kind of dynamic uh which actually has quite

22:45

different properties as we'll see well there's many many similar properties but it also has a

22:49

has quite a different nature somehow it really has maybe almost like more of a dynamic aspect.