Stable populations and ADE
Wild Egg Maths
4.6K subscribers
Having introduced the Mutation Game on a general simple graph, we now look for graphs that have stable populations: those which are unchanged under any mutation. It turns out that this is another interesting classification problem closely related to the question about which which graphs have a finite set of root populations.
This gives us a chance to introduce the ADE ~ graphs on their own terms. And it also allows us to revisit the argument of the previous video to clarify the above classification of graphs with a finite number of root populations.
The ADE~ graphs also are characterized by a spectral condition on their adjacency matrices, and we will see that these stable populations are closely related to the associated eigenvectors.
00:00
hello everyone i'm noah wahlberger and
00:02
thank you for joining me on this
00:03
adventure
00:04
in exploring dynamics on graphs
00:07
[Music]
00:09
so today we're going to talk about
00:10
stable populations
00:12
and ade tilde graphs these ad tilde
00:15
graphs we
00:16
saw them already in our last video i
00:18
hope you've already watched
00:19
that and today we're going to sort of
00:22
explain why they are actually of
00:24
independent interest relating to
00:27
this important notion of a stable
00:29
population
00:30
and this will also give us a chance to
00:32
go back to the argument of the previous
00:34
video
00:35
and tighten it somewhat so the framework
00:39
is
00:40
that we have x a simple graph and
00:44
i often don't say it but in effect
00:46
usually it's
00:47
a connected simple graph right so you
00:49
probably can assume that i'm talking
00:51
about a connected one even if i
00:52
forget to say that and p of x
00:56
is the the type of
00:59
populations on x so a population is a
01:03
an integer valued function on the
01:05
vertices of the graph
01:07
and for x a vertex of the graph we have
01:10
this mutation s
01:11
sub x which takes populations to
01:13
populations and here is the crucial
01:16
definition all right that if you take
01:19
a population p and you apply
01:22
s sub x to it we write that with the s
01:25
of x on the right
01:26
then the new function the new population
01:30
its value at y is defined as follows
01:34
if y happens to be equal to x
01:38
then the value is then
01:41
the negative of p of x in other words we
01:45
negate the current value
01:46
and then we add the sum over all z which
01:50
are
01:50
neighbors of x direct neighbors of x of
01:53
p of z
01:53
so we negate the value at
01:56
x and we add the values of the
01:59
population at all the direct neighbors
02:01
that's if y equals x and otherwise
02:05
s sub x leaves the population values
02:08
unchanged
02:09
so s sub x only changes the population
02:11
at
02:12
x
02:18
okay right so now we are going to define
02:20
a population p
02:22
to be stable precisely when
02:26
it's left invariant under
02:29
every mutation that p
02:36
p s sub x
02:39
equals p for any vertex x in other words
02:43
no matter where you mutate the
02:45
population is not
02:46
changing now if we go back to our
02:50
expression for the
02:53
mutation we can see that this is
02:55
immediately equivalent
02:56
to the following condition that for
02:59
any vertex x of x we have
03:03
two times the population at x equals
03:06
the sum of the
03:10
neighboring values the sum over z a
03:13
neighbor of x
03:14
p of z okay and why is that well we just
03:16
go back up to here we look at this
03:18
line here if p is
03:22
maintained or invariant under s sub x
03:26
then this this the value along the first
03:29
line is going to be equal to
03:30
p of x in other words it doesn't change
03:32
so we get p of x
03:34
equals minus p of x plus the sum and we
03:37
bring the p of x to the other side then
03:38
we get 2 p
03:39
x equals the sum z in nx
03:42
p of z okay so that's the um
03:47
the definition of a stable population
03:48
and we note that we could just trivially
03:50
rewrite this
03:51
one-half of the sum of the
03:55
neighboring values of p and this should
03:58
be true for
03:59
any vertex x so i want to
04:02
just point out here that it's a kind of
04:04
an averaging okay
04:06
we're saying that p of x is sort of like
04:08
an average but it's
04:09
not crucially an average because if it
04:11
was an average we would have to divide
04:13
by the number of
04:15
neighbors but we're not doing that we
04:17
are dividing by
04:18
2 always independent of how many
04:20
neighbors there are
04:21
okay that's an important point that's
04:24
interesting
04:25
okay so now we are going to have some
04:27
look at some examples
04:30
and i'm going to show you some graphs
04:33
that have
04:34
stable populations and our first one is
04:36
a n tilde
04:39
remember that's the graph you get when
04:40
you start with the a n graph
04:42
written horizontally vertices 1 through
04:44
n and you add an extra node
04:47
star which is joined both to 1 and to n
04:51
and it's pretty simple to write down
04:54
a stable population i'm going to do that
04:56
right here one
04:58
one one one
05:02
one one everywhere okay so if you
05:05
look at any particular value say that
05:07
value there then it is
05:08
of course true that the value at that
05:12
point
05:12
is one half the sum of the neighbors the
05:14
sum of the neighbors is two you take one
05:16
half you get one which is the value
05:17
there
05:18
that is a stable population for a
05:21
and tilde and of course since things are
05:24
linear we could
05:25
multiply this population by any
05:28
integer and we get another stable
05:30
population but it would be constant
05:34
okay let's go to d4 tilde
05:37
which is the d4 graph with this extra
05:42
node star down here at the bottom and
05:43
notice that i'm
05:46
i'm labeling the vertices of the graph
05:49
just to get you familiar with the way
05:50
we're going to label them okay so zero
05:52
up at the top and then one two three
05:54
along the horizontal bar and the stars
05:56
down the bottom
05:57
okay can we write down a
06:00
a stable population well it's kind of
06:03
symmetric
06:04
so you know it probably should be
06:05
symmetric so let's put one one
06:07
one one there all over there and what
06:10
would the
06:10
middle one have to be if it's going to
06:13
be
06:13
one half the sum of the neighbors well
06:15
it'll have to be two
06:17
okay and that is in fact
06:20
a stable population we've just seen that
06:24
it's
06:24
certainly sort of in stable it fulfills
06:27
the stable condition at
06:29
the vertex 2 the central vertices but it
06:30
also fulfills it any any of these other
06:32
vertices
06:33
so for example if we look at the vertex
06:36
labeled one
06:37
then the sum of the neighbors
06:40
populations is
06:41
two and the value at one is indeed one
06:44
half
06:44
of that okay so d4
06:48
tilde has a stable population and here
06:51
it is
06:51
right here how about dn
06:55
tilde and n is greater than or equal to
06:59
five
06:59
it's a little bit of a separate case
07:01
from d4 tilde okay
07:03
this is the case when we have a
07:05
horizontal
07:06
dn and then on the other side making it
07:09
a little bit more symmetrical we add an
07:11
extra node
07:12
star okay so there's a certain number of
07:14
intermediate nodes here
07:16
and we want to know how can we cook up a
07:19
stable population
07:20
well let me illustrate that actually
07:22
with this case here
07:24
d7 tilde okay
07:28
i'm going to put a 1 here and a one here
07:32
and i'm going to think about what i
07:34
should put
07:35
here well actually what i need to what
07:38
what i'm going to put here
07:40
well actually what i'm going to put at
07:41
this vertex is determine because
07:43
the value here at the vertex 1 and i'm
07:46
referring to this
07:48
labeling the value at the vertex 1 has
07:50
to be
07:51
half of the sum of its neighboring
07:53
values but it only has one neighbor
07:55
namely at the vertex 2 okay so the value
07:58
of the population at 2
08:00
better be twice the value at 1. so this
08:03
has to be 2.
08:05
that's good that ensures that we also
08:08
have the
08:09
half sum of neighbors condition at that
08:11
vertex 0.
08:12
now what about at 2
08:16
the sum of the neighbors at 2 should be
08:18
twice
08:19
the value at the vertex 2. so in other
08:22
words
08:22
- that means that that
08:26
right most vertex there better be a
08:29
value of 2
08:30
there so that the sum of the neighbors
08:32
is altogether 4
08:34
which is twice times 2. okay
08:37
and now we can kind of proceed going
08:39
right so um
08:40
in order for this value 2 to be half of
08:44
the sum of the neighbors
08:45
well we need to have this one over here
08:47
be 2 as well
08:48
and then in order for the value here to
08:50
be half of the sum of the neighbors we
08:51
need this to be 2
08:53
and then these guys are both going to be
08:55
one and we can check that at every
08:56
vertex it
08:57
fulfills this condition that the sum of
09:00
the neighbors is twice the value
09:02
of the population at that vertex so
09:05
there's
09:06
um the case for d7 tilde and it's
09:09
obvious
09:10
how to generalize it to dn tilde we're
09:13
gonna have ones
09:14
at the boundary or leaf
09:17
nodes and along the central string
09:20
there'll be a whole bunch of twos
09:24
so it's like kind of an extension of d4
09:26
tilde
09:28
okay now we get to e6 tilde
09:32
e6 tilde has a pleasant symmetry
09:36
the three branches look all the same so
09:38
let's start with this
09:40
branch here at the vertex one let's put
09:42
a population of one there we're looking
09:44
for a stable population
09:47
well then the population at two better
09:50
be
09:50
two so that the condition is satisfied
09:53
at one
09:54
same kind of thing we've already seen
09:57
and now
09:57
what must the population at three be in
10:00
order for the condition to be satisfied
10:02
at the vertex 2.
10:04
so if we multiply 2 by 2 we get 4
10:08
that should be the sum of the neighbors
10:10
well on one side there's one
10:11
so on the other side there better be 3.
10:15
so that has to be 3.
10:19
and then it's kind of symmetrical so
10:21
there's going to be a 2 here a 1 there a
10:23
2 here and a 1 there
10:24
and that ensures that the condition is
10:26
satisfied at all the
10:28
vertices except we haven't yet checked
10:30
at the
10:31
central vertex label 3 let's check that
10:35
twice the value of the population is 2
10:37
times 3 which is 6
10:38
and happily that is the sum of the
10:41
neighboring values 2 plus 2 plus 2.
10:43
so that's a stable population for e6
10:46
tilde and what about e7 tilde there it
10:51
is there
10:53
okay notice the labeling of e7 with zero
10:57
up at the top and then one two three
10:58
four five six along the horizontal
11:01
and our star our new vertex is off to
11:03
the left making it a little bit more
11:05
symmetrical
11:06
okay so the same kind of argument you
11:09
start with one there then that has to be
11:10
two
11:11
that has to be three and indeed that has
11:13
to be then before
11:15
and then by symmetry that's going to be
11:16
one two three
11:18
and now it just remains to ask what
11:20
could be the value at zero
11:22
well the value at zero has to be half of
11:24
the value at its neighbor because it
11:26
only has that one neighbor so its
11:28
value is going to be 2. that
11:31
is the stable population for e7 tilde
11:35
and what about e 8 tilde
11:39
now we've taken e8 notice its labeling
11:42
zero also at the top one through seven
11:44
along the bottom
11:45
and now the star the new vertex is off
11:48
to the right making it
11:50
even more lopsided than it already was
11:53
okay
11:53
so how can we proceed well let's start
11:56
here with the star
11:57
it's sort of the furthest down if that's
11:58
say one then this forces
12:00
that to be two and then this has to be
12:02
three and this has to be four and this
12:04
has to be five
12:05
and this has to be six just to ensure
12:07
that for each one of these like say for
12:09
4
12:09
it really has the property that the
12:12
value
12:13
at 4 the value there times 2 which is 2
12:17
times 4 is 8
12:18
is indeed the sum of the neighboring
12:20
values
12:22
okay now how can we fill in the rest
12:25
so that um things are working well
12:28
uh we we
12:32
the six here that has to be three
12:34
because it has to be half of it
12:36
and over here it's the same kind of
12:37
thing as one two three but we sort of
12:39
multiplied by two so it's got to be two
12:40
four
12:41
six and now there's still one more thing
12:43
to check we should check that the value
12:45
here
12:46
if we multiply it by two we get twelve
12:48
that that is indeed the sum of the four
12:50
the 3 and the 5 and that's in fact true
12:54
which reminds me that i didn't do that
12:55
check up here for e7 let's do that also
12:58
so if we take the value there multiplied
13:00
by 2
13:01
that's 8 which is indeed 3 plus 2
13:04
plus three so yes we've checked all
13:06
these values so those are
13:08
stable populations for all
13:12
the ade tilde graphs that we
13:16
that we've discussed so far so here now
13:19
is a question for you an exercise for
13:22
you to think
13:23
about there's
13:28
two things um to to maybe obviously
13:30
think about
13:31
um check that
13:36
up to up to a scale up to a factor
13:42
these are the only
13:46
stable populations
13:51
on these a
13:54
d e tilde graphs
13:58
okay so they really are unique at least
14:00
up to a scalar because we can multiply
14:02
any one of these
14:03
by a scalar that's fine
14:07
and now a little bit more challenging
14:09
let's ask the question
14:11
are there any other graphs
14:16
there any other okay let's be specific
14:19
connected simple
14:24
graphs
14:28
x that have
14:32
uh okay obviously non-zero
14:35
zero the zero population is not going to
14:38
be included
14:39
that have a non-zero stable
14:43
population or is this a complete list
14:49
if it's a complete list then this is a
14:52
sort of a separate reason why
14:56
these are sort of interesting families
14:57
of graphs right because we
14:59
this particularly simple condition that
15:01
there is a stable population
15:03
which is um you know it's almost
15:07
like an eigenvalue well we'll see the
15:09
next uh
15:10
one of our next videos that it is a very
15:12
much an eigenvalue thing
15:14
okay so are there any other connected
15:15
simple grass x that have a non-zero
15:17
stable population
15:18
that's an interesting question to think
15:20
about
15:23
so in our last video we were looking at
15:24
this argument that showed that
15:27
the ade graphs were the only ones that
15:30
had a finite
15:31
set of root populations and i remind you
15:35
those are the populations obtained from
15:37
a singleton
15:38
by performing arbitrary sequences of
15:41
mutations
15:42
and the way we did it is that we
15:44
actually looked at these ade tilde
15:46
graphs and tried to convince ourselves
15:48
that each one of them had an unbounded
15:51
number
15:52
of root populations and that meant that
15:55
we could exclude those
15:57
from being sub graphs of the ones that
16:00
we were interested in and that
16:01
allowed us to narrow things down to the
16:03
ade graphs
16:05
okay so recall
16:09
that last time the aede
16:13
tilde graphs
16:18
each have
16:21
an unbounded
16:26
number of root populations
16:34
but the argument that i gave was a
16:36
little bit ad hoc
16:37
so to tighten that
16:42
we can use
16:48
these stable populations
16:52
and i'm going to leave you to
16:56
check the majority of these things it's
16:57
a very excellent exercise but i'm going
16:59
to show you how to do it
17:00
and i might start with our d7 graph
17:04
all right one two three
17:08
four five six seven and then we put an
17:10
extra one here so here was d7
17:13
tilde okay and i remind you i better
17:17
remind you of our
17:18
labeling zero one two three four
17:22
five six and star over there okay
17:25
actually i might keep that labeling
17:26
right in front of us so we can see the
17:28
labeling
17:29
and i'm gonna copy the graph down here
17:39
okay and i'm
17:42
going to show you an argument to
17:45
convince you a little bit more carefully
17:48
that in fact this thing has an unbounded
17:52
number of roots so let's start with a
17:55
singleton
17:56
so let's say we have a singleton at one
17:59
so let's start with a singleton
18:02
at the vertex 2. so i'm going to
18:05
denote that by a delta so delta often
18:09
means
18:09
like a delta function it's 1 at some
18:11
value and 0 elsewhere
18:13
so let's let delta sub 2 represent
18:16
the singleton
18:20
the singleton population uh with
18:25
1 at vertex
18:29
- all right so now let's perform some
18:32
mutations on
18:34
this delta two okay so we're starting
18:36
with delta two
18:39
and we're gonna apply some mutations
18:41
let's start with
18:42
s sub zero mutation at zero which is
18:46
this one up here
18:47
this one right here okay and so that'll
18:51
turn the current zero there to a one and
18:54
then we're gonna apply
18:55
s sub 1. and we just apply
18:58
more mutations by adding them on our
19:01
list
19:02
to the right okay because we read from
19:04
left to right these are just
19:06
operations which are adding successively
19:08
to what we already have
19:09
okay so now an s sub 1 will turn the
19:12
current
19:13
0 there into a 1.
19:16
and now let's do s sub 3 that'll
19:20
give us a 1 there and then s sub 4 will
19:23
give us a 1 there s sub
19:24
5 will give us a 1 there s sub 6 will
19:27
give us a 1 there and s
19:28
sub star will give us a 1 there
19:32
and now we're going to come back we're
19:33
going to do s5 again
19:36
okay so what happens with s5 well
19:39
we get minus one plus a total of three
19:41
that's two
19:42
we'll write the two like this okay
19:44
there's two now
19:46
two at at vertex five
19:50
and now s4 well the one becomes minus
19:54
one and then we have to add a total of
19:55
three to get
19:56
two so there'll be another two there and
19:58
then we'll do s3
20:00
we'll get two there maybe we'll put it
20:02
on that side
20:04
and then s2 and what do we get with
20:08
there it is two um we get minus one plus
20:11
one plus one plus
20:12
two so minus one plus four is a total of
20:14
three
20:15
so we'll put three there okay let's
20:18
pause
20:19
and see what we have
20:23
[Music]
20:24
i claim that what we have now is the
20:27
original
20:28
delta two okay
20:32
plus a population
20:35
which looks like what so we just take
20:37
the delta two out
20:39
then we get a population which has ones
20:42
in the uh the leaf vertices and two
20:46
around down the middle okay that's
20:48
exactly our stable population for d7
20:51
tilde that we identified already
20:53
we haven't given it a name let's give it
20:54
a name let's call it alpha sub zero
20:57
where alpha sub zero
21:00
is the stable population
21:07
for d7 tilde
21:10
obtained earlier
21:18
now i'm going to write this in a
21:21
slightly more
21:22
efficient way so instead of writing all
21:24
these s's so
21:25
let's introduce alternative notation all
21:28
right let's
21:29
agree that we're going to write this as
21:32
delta 2
21:35
times s and i'm just going to list all
21:38
the vertices
21:39
that we're using 0 and then 1 and then 3
21:42
and then 4 and then five and then
21:44
six and then star and then five and then
21:47
four and then three and then two
21:48
okay so that's like a shorthand
21:53
shorthand for a product of the
21:55
corresponding
21:56
mutations so what
22:00
we get we get this is delta two plus
22:03
alpha zero
22:08
now uh why does that prove
22:12
very easily now that we have an
22:13
unbounded
22:15
um an unbounded
22:18
set of root populations for this graph
22:21
the reason is we can just perform this
22:23
same
22:24
sequence of mutations again so if we
22:28
apply
22:31
okay let's give this name let's say w
22:34
happens to be
22:35
this sequence of mutations s 0 1 3
22:38
4 five six star five four
22:41
three two okay that's uh that's a
22:44
sequence of
22:46
mutations but so it's it's a it's
22:48
another transformation
22:49
from populations to populations then we
22:54
well we what we currently know is that
22:57
delta 2
22:59
followed by w if we apply w we get delta
23:02
2 plus
23:03
alpha 0. so what happens if we apply it
23:06
twice so delta to
23:10
w squared which means delta two
23:13
and then apply w and then apply w again
23:16
well that's going to be equal to
23:19
the delta two w is delta 2
23:23
plus alpha 0 our stable population so
23:26
then we have to apply
23:28
w to that but
23:32
these are all linear transformations and
23:34
so their composition
23:36
also is a linear transformation
23:39
so maybe i should say a
23:42
linear transformation okay a linear
23:45
transformation
23:49
transformation on populations
23:53
so that means that this can be written
23:55
as delta two
23:57
acted on by w plus alpha zero
24:00
acted on by w
24:04
okay but what's that
24:08
well delta two of w we already know
24:11
we're getting the same thing that we
24:14
have already got we get delta two plus
24:17
alpha zero but what is w acting on
24:20
alpha zero alpha zero is the stable
24:22
population so
24:23
all of these mutations that we apply to
24:25
it none of them has any
24:27
effect whatsoever so we just get alpha
24:30
zero
24:30
in other words we get delta two plus two
24:33
alpha zero and now you can see very
24:37
systematically
24:38
how we can generate bigger and bigger
24:40
populations
24:41
because all what we do is we hit this
24:44
with
24:45
with this composite transformation w
24:48
and what we're ending up doing is just
24:50
jacking up
24:51
the coefficient of alpha 0.
24:55
so further
24:59
applications of
25:02
w just increase
25:07
the coefficient
25:11
of alpha zero so we can get
25:17
an unbounded
25:22
number of root
25:26
populations for
25:30
d seven tilde
25:33
but it this argument does depend on us
25:36
having found
25:37
this particular sequence it should put
25:40
it in
25:41
green okay so we found this we found
25:44
this particular sequence right here
25:47
and that was the key to
25:50
starting with the delta function and at
25:52
the end of applying all of that we got a
25:54
stable population plus another delta
25:56
function
25:58
so now there's a great exercise for you
26:02
okay another exercise
26:06
find corresponding
26:13
mutation sequences
26:20
for the other
26:24
a d e tilde
26:27
graphs to
26:31
more firmly
26:36
established
26:40
they have unbounded
26:45
number of root
26:50
populations
26:52
so you get to roll up your sleeves and
26:56
really get to work understanding these
26:58
mutations and starting to think about
27:01
not just individual mutations but
27:03
sequences of mutations acting together
27:06
to come up with more
27:10
richer or more complicated
27:16
[Music]
27:18
transformations