Dynamics on Graphs 27

25 views Jul 8, 2023

We introduce a famous theorem of G. Birkhoff from the 1930's, where he establishes a fundamental connection between general partially ordered sets (posets) and general distirbutive lattices (which are of course also posets, but with additional structure). This connection has to do with ideals of the poset, and so-called join irreducibles in the lattice. It turns out that this connection plays a natural and important role in the Dynamics on Graphs story. We will illustrate the richness of this situation explicitly by looking at mutation and firing frames, coming from both the Mutation and Numbers Games, on the ADE graph D5.

0:00

Hello everyone thanks for joining me we are going to be looking at a famous theorem in lattice

0:07

Theory combinatorics due to Garrett Birkhoff it's around 1937 which is a strong connection between

0:17

arbitrary posets or partial ordered sets and distributive lattices and this particular result

0:24

figures very importantly in this sort of General framework that we're discussing here where we're

0:30

starting with the ADE graphs although we're also considering more graphs but generally and playing

0:35

the mutation and the numbers games and we're interested in combinatorial structures that

0:42

arise by looking at what happens when we play the mutation in numbers games we are generating

0:49

patterns of a combinatorial nature okay so to illustrate everything because I want to be really

0:56

concrete so we can really uh get the grips what's going on I'm going to talk about D5 today okay so

1:02

we'll look at D5 from a number of points of view mutation and firing frames are going to be the

1:08

main things we're going to discuss so we're going to introduce this new thing called firing frames

1:11

but we're also going to look at the connections with root population post sets so in a previous

1:18

video we did look at mutation frames for D5 and we started with a Singleton population Delta X

1:24

and that was in the space of populations so I remind you yet again that we have some graph like

1:29

D5 here there are sort of two ways that we have of thinking about things we think about integer

1:33

valued functions on the graph as being populations but sometimes we think of some alternate integer

1:38

valued functions called weights and so distinguish between these two situations we sort of have these

1:44

closed nodes and open nodes to distinguish between this story here what we do with populations where

1:50

the corresponding Transformations are called mutations and over here where we're talking

1:55

about weights or the fundamental objects and the Transformations are called firings

2:00

okay so we're going to be looking at both of these things but let last time what we

2:04

we started with was a Singleton population okay so represented by this thing here okay so we started

2:11

with the population where there was a Singleton at the vertex that we're labeling one so the labeling

2:15

is one two three four along the bottom and zero up here and we mutated increasingly so we're sort

2:21

of increasing the population until we get to this maximum population which I hope you recognize one

2:26

two two one and one on top and the way we did it is by taking S2 first and then S0 and S3 in some

2:33

order and then S2 and S4 and some border and then finally S3 and then we can express this

2:37

more simply just with this little diagram it's actually a lattice that contains the vertices

2:43

that were subsequently mutating on so it's a nice little rectangular lattice and we'll call this a

2:52

mutation frame okay so and we'll denote it by M plus D5 is the graph and the vertex that we're

3:00

starting with is one so this is sort of a record of the mutations that we can perform by starting

3:06

with a Singleton corresponding to this particular vertex in the context of the populations and

3:14

mutating on them now Associated to this is a post set of positive roots okay the positive

3:22

roots that are obtained from the singleton so as a result of doing these various mutations we get

3:28

various positive roots and they're Illustrated in this little diagram here so there is the original

3:34

one there should be a zero on top of that is there okay this should be a zero over here to the top

3:40

of the zero of course so this is the Delta sub 1 root that we're starting with and then we do an

3:47

S2 mutation to get this one over here and then we can mutate in this direction or in this direction

3:52

to get these two roots and then you know here are the list of all the various Roots down to this

3:58

maximal root down here one one two two one and this particular posit this is not all the positive

4:06

Roots these are just the positive roots that are obtainable by starting with the Singleton at one

4:11

and Performing these increasing mutations so yeah each step here we are increasing the population

4:20

and the edges here are labeled by the mutations that we're actually performing and notice that you

4:25

know that these edges like the one here between here and here and here in on the graph have the

4:30

same label they're both labeled by three this edge here this edge here this edge here you might say

4:35

these are sort of parallel that just they're all labeled by the same mutation vertex four

4:43

So we see that this M plus D5 originally sort of corresponds to the edges somehow of R plus so let

4:53

me just just connect that all right so here's the original thing if you look at these just mutations

4:57

two on the top and then 0 and 3 and then two and then four and then three we see the same sort of

5:04

pattern in the blue edges here there's a 2 up at the top and then there's a zero in the three okay

5:09

then those are sort of repeated but then there's a a 2 and a four and then finally another three

5:17

and so to make this correspondence um more clear we're going to understand a famous theorem due to

5:25

Garrett Birkhoff in 1937 which is a fundamental result for distributive lattices so let me remind

5:32

you that if p is any pose set okay then by J of P we mean the lattice of ideals of pay

5:41

and let me remind you that an ideal of a post set p is a subset which has the property that

5:47

if x is an element of that subset then anything less than or equal to X is also in the subset

5:55

okay and that's then a lattice there's a natural partial order given by inclusion okay so the sort

6:05

of set theoretic operations of join and meat or Union intersection apply to this family of ideals

6:13

and so that way the ideals become a lattice so we get in fact what's a Distributive lattice

6:20

and Theorem of Birkhoff is that in fact any finite distributor of lattice L is of the

6:27

form J of P for some posts at p so given a post set P we can always take J of P which is the

6:37

set of ideals of p and that's a lattice that's a Distributive lattice and conversely

6:42

any distributive lattice actually comes from some post at P by this Construction

6:49

and moreover how do you get this P well P turns out to be or can be taken to be the post set of

6:59

join irreducibles of L right so there's a certain notion which I'm going to describe to you called

7:04

a join irreducible and inside L if you look at the join irreducibles then you can see this sort

7:11

of underlying post set P from which L can be constructed by taking the ideals of P this is

7:19

a very beautiful fact and of course it extends also more generally but we're just going to look

7:24

at it from the finite combinatorial point of view so this does give us a one-to-one correspondence

7:30

P going to J of P or L between post sets p and distributive lattices l some sense these

7:38

two things are the same although they appear to be quite different and I'm going to illustrate

7:45

this um this correspondence by uh convincing you hopefully that that R plus of d51 is isomorphic to

7:56

J of M Plus d51 in other words that's exactly the relationship that's happening between

8:05

this poset here this one here which is just a poset it is also actually a lattice but

8:11

that's irrelevant we're just thinking this as a poset and then we're claiming that if you look

8:14

at the ideals of this thing well then you get um this and in fact this this statement is one that

8:23

we've already seen before we've already looked at ladders you know of taking starting with a

8:28

poset and then taking ideas of it so this is actually already a familiar fact for us

8:33

but let's illustrate it here any in any case in this particular example but before we do

8:39

that let's talk uh just to make sure that we understand about joins and join irreducibles

8:44

so in a poset P an element Z is the join of X and Y if X is uh less than or equal

8:52

to Z and Y is less than or equal to Z okay so Z is bigger than both X and Y

8:57

and if it's the least such biggest or common based element in other words if for any W also

9:04

satisfying X is less than or equal to W and Y is less than or equal to W we must have W is bigger

9:10

than or equal to Z okay so that's then called the join of X and Y so in other words Z is the least

9:18

upper bound of X and Y and we write this sort of using a union notation and if these were all sets

9:24

then that's exactly what we're talking about if we have one set X and then another set of Y then

9:29

the union is the smallest set that contains both of them okay so in the post set made of subsets

9:38

of set as the the join of substance is just the union okay so for example in R plus d five one the

9:45

join of this element 1 1 0 0 and 0 1 1 is 1 1 1 1 1. so let's have a look at that okay so the the

9:56

join of this element right here and this element here okay it's an element which is bigger than or

10:02

equal to both of them and that's this one right here so this is the join of this element and this

10:08

element it's bigger than or equal to both of them it's not the only one that's bigger than or equal

10:13

to so this one here is also bigger than or equal to both of these and so is this one here but this

10:18

is the least such in the sense that the other ones are bigger than or equal to this one here

10:27

okay so now what do we mean by a joint irreducible so in a lattice L okay in a lattice joins and

10:35

meets are well defined and element X is called join irreducible precisely when first of all it

10:41

is not the minimal element okay it's not at the top okay and it's not the join of other elements

10:52

not the join of other elements so for example here's a lattice l in blue okay The Join

11:02

irreducible elements are circled in red so here's a join irreducible element first of all it's not

11:08

the minimal element so this one is not included this is not join in join your decimal but this one

11:13

is join irreducible because it's not the minimal element and it's not the join of others okay

11:20

um this one here is the join of others this X here so this X is the join of of this element here and

11:26

this element here so this is not join your just one similarly this is not joint irreducible this

11:31

vertex here because it's the join of this one and this one this one's also not join reducible

11:37

because it's the joint of this one and this one but this one is joined reducible because you can

11:42

see there's only sort of one Edge coming towards it from from up from the top okay this one also

11:49

has one Edge coming towards from the top so does this one so does this one so does this one that's

11:53

the easy way of finding the joint irreducibles so if you look at just the red joint irreducibles of

12:00

this lattice they form a pole set because you can just take the partial order given by this Hasse

12:07

diagram and restrict it to the red ones okay then if we do that these red ones are going to form a

12:13

post that looks exactly like this okay so these four elements here are just these ones here and

12:19

then if you think about this one here well it's less than or equal to this one and this one so it

12:23

fits right there and this one here is less than or equal to in fact all of them so it fits down

12:29

here so this is just another way of describing the post set of join irreducibles of of this lattice L

12:37

and here's where we see that that other lattice that we started with so the claim then is that

12:44

this poset of join irreducibles is the poset that creates the lattice in the sense that the lattice

12:52

can be thought of as being isomorphic to the poset of ideals of P so for example here's an ideal of

13:02

P these top three elements okay so what's the element corresponding to to this ideal well

13:09

it's this element X because this element X is uh the one that's you know directly underneath

13:16

it's the join of all of these ones okay it's the join of all of the three that we've got

13:22

in particular this one up here corresponds to the empty set which is also an ideal okay and you

13:30

can convince yourself that the the ideals of this thing here exactly correspond to these things here

13:39

so the elements of L correspond to ideals of P and notice also that the vertices of P are naturally

13:46

labeled by the edges of L that end in those vertices so if we were going to label in this case

13:53

the edges of this L are indexed by the mutations that were required to get to them right so we had

14:01

two and then 0 3 and and four and two and so on so these join irreducibles only have one Edge coming

14:08

into them from the from on top and so we can label them by the label of that edge that's coming into

14:15

them right so this top guy here we can label it too and this one here we can label it zero

14:20

Etc so we get a natural labeling of the vertices of P from the edges here and you will see that

14:28

that does indeed correspond as we originally saw with that original lattice over here

14:34

okay so the ideals of this thing correspond there that's basically a picture of this thing

14:42

correspond to the elements of this thing here and this is an illustration of um Birkhoff's theorem

14:52

so in the previous lecture we considered starting not with a Singleton population but rather a

14:58

Singleton weight okay and we got another kind of frame by performing these dual mutations well

15:05

sometimes we call them firings at vertices where there are strictly positive weight values and to

15:10

make this canonical we considered the ADE graphs as being bipartite so this is a general thing that

15:16

we can do for a general bipartite graphs and we alternated between taking say S sub E which is

15:21

the product of even vertex firings and S sub O the product of odd vertex firings so let's now

15:29

because we want to clarify I think let's redefine such a pole set as as a firing frame for the graph

15:36

x okay so let's look at the same graph with also a Singleton at one but now not a Singleton

15:45

population but a Singleton weight okay so you can see we're talking about dual mutations or

15:52

firings because the vertices are all uh sort of open here so we're starting with this Singleton

16:00

weight and we're performing the Dual mutation story so let me remind you you mutate at this

16:06

positive vertex and it changes to a minus one and the neighbor gets the value added to it so we get

16:12

a one there okay and then we fire at this one and we get a minus one there and a one there there and

16:20

there the nearby neighbors and the one that is added to this one here cancels that to get zero

16:25

and I of course I'm using my preferred notation uh for negative numbers where I put a bar on top

16:32

of things to denote native numbers rather than a minus sign in front of things okay so then at this

16:38

stage here we are going to adopt the same kind of thing and fire at both of these vertices together

16:45

simultaneously because they commute so we get a minus one here and minus 1 here and then these two

16:51

ones add to this thing here to give us a total of plus one and also uh one gets transferred for from

16:57

here to here and so you can just check that you know the sequence goes like this until eventually

17:03

we get to the stage where we just fired this one here that becomes a minus one and this thing here

17:10

has become a zero and then at this stage here there are no more strictly positive entries so

17:15

there are no more firings that we could do that would increase the corresponding population on the

17:24

other on the other side okay and that's where the the kind of thing closes and so now if we sort of

17:30

record you know what mutations did we do well we mutated at the vertex one we did actually a firing

17:37

at the vertex one and then a firing at the vertex two and then a firing at the bird sees zero and

17:42

three Etc so then we can record that and we get let's call it a firing frame so let me introduce a

17:49

slightly different notation just to clarify this distinction okay so let's call it F for firing

17:55

as opposed to M for mutating okay so f plus we're still interested in essentially

18:00

increasing populations but we're working on the weight side so F plus of D5 starting with a one

18:08

so we had a one and then a two and then zero three two four one three two zero you can check that's

18:12

what I actually was doing with this pattern here all right so we get this firing frame

18:21

and we note that as a lattice this is isomorphic to R Plus d51

18:29

see that lattice that we're getting there happens to be isomorphic to

18:39

this thing here this R Plus d51 so is this a coincidence well um that's an interesting

18:47

question um and what happens more more generally if we started with some different vertex and

18:55

not vertex once that's an interesting question which we're going to explore in our next video