Dynamics on Graphs 23

26 views May 1, 2023

We review some basic facts about posets (partially ordered sets), lattices, distributive lattices and ideals of a poset. Two simple inductive families of examples lead to interesting patterns of posets, which in our next video will be seen to allow us to rethink where the "ADE" graph sequences come from!

0:02

hi everyone I'm Lauren Wahlberg thanks

0:04

for joining me we are exploring Dynamics

0:06

on graphs and today I want to talk about

0:08

ideals of a post set and introduce sort

0:12

of an inductive approach to creating

0:14

richer and richer combinatorial

0:16

structures starting from something very

0:17

simple in the following video I'm going

0:20

to show you that it's exactly this

0:21

procedure that will allow us to generate

0:26

basically the the Ade hierarchy from

0:31

little more than than nothing okay it's

0:34

it's really quite a remarkable thing and

0:37

so today some of the topics that we're

0:39

going to be talking about we've talked

0:40

about already we've talked about ideals

0:42

in the context of E6 and partial order

0:46

sense but I just want to be a little bit

0:47

more formal and to review some of that

0:49

material so a good place to start is

0:51

with the notion of a person which of

0:53

course is a partially ordered set so

0:55

that means that we have a set P together

0:57

with a relation R so relation R is a

1:00

subset of the

1:02

product P cross p

1:04

and it's often denoted by

1:07

is less than or equal to sign so we

1:09

write X is less than or equal to y

1:11

That's the short form for saying that

1:13

the pair X Y is in this given relation

1:17

so relation is very arbitrary it's an

1:19

arbitrary subset of this product

1:21

this Cartesian product of P cross B but

1:25

to make it a partially ordered set it

1:27

should satisfy these three additional

1:28

properties first of all X is less than

1:31

or equal to X for all X in p

1:33

that's the reflexive property secondly

1:36

if x is less than or equal to Y and Y is

1:38

less than or equal to X then x equals y

1:40

That's the anti-symmetric property and

1:43

the transitive property if x is less

1:45

than or equal to Y and Y is less than or

1:47

equal to Z then X is less than or equal

1:49

to Z okay so that's a post set and so a

1:53

very fundamental example is the subsets

1:55

M of a set s

1:58

with relation less than or equal to

2:01

being just inclusion so two sets

2:06

which are subsets of s x is less than

2:08

equal to Y is the same as X is a subset

2:11

of Y so for example if s equals one two

2:14

three then this post set can be

2:17

Illustrated with this diagram here so

2:19

the inclusion is then captured by the

2:21

hassa diagram which we've seen before

2:23

and I remind you that means that the

2:25

bonds here are showing covering

2:26

relations so uh where in those where X

2:31

is less than or equal to Y and there's

2:32

no intermediate point which is in

2:36

between X and Y other than x y itself

2:39

okay so we have the empty set we have

2:41

three Singletons we have three double

2:43

twins and we have the entire set now

2:45

this is a very special example actually

2:47

because it's

2:49

containing more structure it actually

2:51

has a strong additional property of

2:53

being a lattice so that's going to be an

2:55

important notion for us so let's um tell

2:57

you about that so A lattice is a partial

3:00

ordered set say l under less than or

3:03

equal to for which any two elements X

3:05

and Y have two things a least upper

3:08

bound

3:09

so written X so upper

3:13

v y also called a join such that if Z is

3:19

greater than or equal to this join X

3:21

join y

3:22

then Zed is bigger than or equal to x

3:26

and z is bigger than equal to Y and

3:28

conversely if if you find sub Z which is

3:31

bigger than or equal to both X and Y

3:33

then it's bigger than the bigger than or

3:36

equal to the join X

3:38

join y so it's an upper Bound in the

3:41

sense that this thing is bigger than X

3:43

and Y but it's the least such upper

3:47

bound

3:48

where does a least upper bound and also

3:51

there should be a greatest lower bound

3:54

with an X sort of downwards facing V

3:57

also called a meat

3:59

such that Z is less than or equal to

4:02

this meat precisely when Z is less than

4:05

or equal to x and z is less than or

4:07

equal to y

4:09

so in the case of subsets of a set

4:14

these least upper bounds and greatest

4:17

lower bounds are just intersection and

4:21

Union well this one here is Union and

4:22

this one is intersection

4:25

okay so here's an example of a post set

4:28

which is not a lattice okay it's this

4:31

thing here and you know our usual

4:33

convention just to remind you is that

4:34

that we're increasing as we're going

4:36

down okay so we usually have the

4:38

smallest elements up at the top of the

4:39

bottom is the heaviest of the biggest

4:41

elements so here's an example which is

4:44

not a lattice because if you look at B

4:46

and C well D is an upper Bound for b and

4:50

c and so is e but D and E are not

4:53

related

4:56

okay so there's also a special

4:59

additional property that a lattice has

5:00

so there's all kinds of lattices that

5:03

has very rich scary but um when these uh

5:07

meet and join operations obey the usual

5:10

distributive properties okay namely

5:13

these ones here that you find you know

5:15

in in elementary set theory then the the

5:18

post set is called a Distributive

5:20

lattice okay and the lattice of subsets

5:23

of a set as the first example we had a

5:26

look at is an example of a Distributive

5:28

lattice

5:30

and here are two interesting and

5:33

somewhat important examples of lattices

5:34

which are not distributive okay so

5:37

there's this one here

5:39

often called The Diamond example a b c d

5:43

e

5:44

sometimes also called M3 and over here

5:47

the Pentagon a here b c down to E and A

5:51

D E down this way also that's something

5:53

that's called N5

5:54

so these are not distributive lattices

5:57

you can check that

5:58

and it's an important fact that the

6:01

distributivity of a lattice is basically

6:04

equivalent to not containing these two

6:08

examples or one of these two examples as

6:10

sublattices

6:12

so a lattice is distributive it turns

6:14

out precisely when it has no sub

6:17

lattices that means

6:19

um

6:20

subsets which are closed under the uh

6:25

the the join and the meat

6:27

and so no sub lattices isomorphic to M3

6:31

or N5

6:35

okay so now let's review ideals of a

6:38

posset so I remind you if we have a post

6:40

set P then a subset I is an ideal

6:44

precisely when it satisfies the

6:45

following condition that if x is an

6:48

element of I and Y is less than or equal

6:50

to X then Y is also in I

6:54

so if you have an element of an ideal

6:56

then everything less than or equal to

6:58

that element is also in the ideal

7:03

so

7:04

the set of ideals okay the set of ideals

7:08

is itself a Post-It under inclusion

7:13

this is a really important sort of

7:16

secondary

7:18

more complicated structure typically

7:20

that we can associate to a post set and

7:23

we'll use the terminology jfp to denote

7:27

the the post set of ideals of a given

7:32

Pro Set p

7:34

so some examples if x is in P then the

7:39

ideal generated by it

7:42

denoted by x with some some pointy

7:44

brackets that's just those elements in P

7:47

those elements y so that Y is less than

7:50

or equal to X that is an ideal

7:53

like a principle ideal and we can

7:57

generalize that if we have a number of

7:58

elements X1 through X K and P then the

8:01

ideal generated by them

8:04

is consisting of this it's the set of Y

8:06

so that's that Y is less than or equal

8:08

to X1 or Y is less than or equal to X2

8:11

Etc or Y is less than or equal to x k so

8:14

it's actually a union of such principle

8:16

ideals so this is also an ideal so these

8:19

are kind of

8:20

um

8:21

easy ways of creating ideals

8:24

okay so and now in general the

8:26

intersection and the union of ideals are

8:28

also ideals okay but because the

8:32

the the inclusion relation is

8:34

essentially a set theoretical inclusion

8:36

relation

8:38

this post set jfp is actually a lattice

8:44

because the elements are actually

8:45

subsets of the original poke set and the

8:50

operations that we're talking about

8:52

are the usual set theoretical

8:55

unions and intersections

8:57

and in fact jfp is actually a

9:00

Distributive lattice

9:03

and then a very nice theorem is that

9:05

every distributive lattice L is actually

9:09

of the form J of P for some poset p

9:14

so this is a characterization of

9:17

distributive lattices in some sense that

9:20

they come from

9:21

being

9:23

being lattices of ideals of typically

9:27

smaller post-sets

9:29

so this is an excellent exercise to

9:31

describe to consider trying to prove

9:33

this thing so you might look at some

9:36

examples of distributive lattices and

9:38

try you know to figure out how are you

9:39

going to find this P that

9:43

is playing the role of the underlying

9:46

pole set of the lattice in other words

9:49

the percent P for which L is equal to J

9:52

of P

9:53

and the answer to that might become more

9:56

clear as we proceed so we're going to

9:58

have a look at some examples here the

9:59

idea of sort of building up

10:01

interesting commentarial structures by

10:03

starting with poets and creating

10:06

lattices of them

10:08

okay so a very simple first example

10:11

is just this simple bow set with two

10:13

elements A and B

10:16

with B greater than or equal to a

10:19

so what are the the ideals of this thing

10:21

well it turns out that the empty set is

10:24

always an ideal because the condition is

10:27

sort of vacuous so that's something that

10:29

we always get for free and then there's

10:31

the ideal generated by a which in this

10:34

case is just a and then there's the

10:36

ideal generated by B which in this case

10:38

is all of it namely A and B together and

10:42

these three ideals are ordered in sort

10:45

of the obvious linear way the empty set

10:49

and then a and then the full ideal a b

10:54

foreign

10:55

more generally if we have what's called

10:58

a chain that is a post set just

11:01

consisting of a single sort of vertical

11:03

diagram for the hasset diagram so A1

11:07

less than or equal to A2 less than or

11:09

equal to all the way up to a k then J of

11:12

p is also going to be a chain and it's

11:15

just going to consist of first of all

11:17

the empty set and then the various

11:19

ideals generated by by each of the

11:21

elements so the first idea of just A1

11:24

the next ideal

11:26

ideal generated by A2 is just A1 and A2

11:29

so that that's subset and then so on we

11:32

just choose more and more increasing

11:35

subsets

11:36

emanating from the top down and the the

11:39

bottom one is the ideal generating by a

11:41

is okay that's all of the whole thing

11:43

so this thing here had K elements J of P

11:47

turns out then to have K plus one

11:50

elements

11:52

that's relatively simple but the general

11:54

thing is not at all so simple

11:57

okay here's a bit more of a complicated

11:59

example let's have a look at this

12:01

whole set p with four elements a b c d

12:06

okay so what are ideals of this thing

12:09

well there's the empty set

12:12

there's a itself

12:14

there's the ideal generated by B which

12:17

is which is essentially the subset

12:19

subset A and B there's the ideal

12:21

generated by C which is this subset a

12:25

C and then there's

12:28

the

12:29

ideal generated by B and C which

12:31

consists of these three elements up at

12:34

the top here B A and C and finally

12:37

there's the ideal generated by D which

12:40

is the whole thing okay so the ideals of

12:46

P form this kind of poet set under

12:49

inclusion

12:54

here's another one that's also pretty

12:57

simple in this case we have a post set P

12:59

consisting of just two elements again

13:02

but now they're unrelated so A and B and

13:06

they're not related

13:07

well then the ideals of this consist of

13:10

the empty set just a itself just B

13:12

itself and the union of A and B

13:16

and you could think of this as being the

13:19

starting pole set of the previous

13:21

example or remember so we started with

13:23

this sort of

13:25

square or parallelogram kind of poet set

13:28

and so this thing here actually is also

13:32

J of something in fact it's j of this

13:36

post set

13:40

so that motivates us maybe to uh to go

13:44

one step further so if we go back to to

13:46

this one here okay the J of the p in

13:50

this example and maybe just rewrite it a

13:52

little bit to make it perhaps a little

13:53

bit more streamlined because since

13:55

debatable so we'll write it like this

13:56

and we'll also rename it so now the

13:58

elements are just a b c d e f okay this

14:02

structurally as opposed at the same as

14:04

the previous so then what is J of this

14:06

thing going to be

14:08

well here's what ju it looks like okay

14:12

there's a b c d e a f and here we have

14:15

the empty set

14:17

a itself

14:19

the ideal generated by B that's nothing

14:23

there the ideal generated by C the ideal

14:26

generated by D which is all this the

14:28

ideal generated by D and C which is all

14:30

of this and then the idea of generating

14:32

by E which is all of that and finally

14:34

the whole thing the ideal carried by f

14:39

so we get that picture there

14:42

so we're going from this shape here

14:44

to this somewhat more elongated shape

14:47

but still you sort of see the original

14:49

somehow contained inside it

14:54

okay so motivated by

14:57

sort of plasma Source sequence this idea

14:59

of building up richer structures by just

15:01

taking J of whatever Post-it we have

15:04

let's do something similar starting with

15:06

this particular post set P where we now

15:09

have a union of just two chains

15:13

A B C D and this is a post set

15:19

then what is J of that going to look

15:21

like well it's not too hard to see this

15:23

empty set there's a itself there's C

15:26

itself there's this thing here which is

15:29

generated by B there's this one here

15:31

generated by D and then there's a c just

15:36

the union of A and C that's also an

15:38

ideal and then there's

15:41

the ideal generator by B and C so it's

15:44

these three elements and also these

15:47

three elements generated by A and D

15:50

and finally there's the whole thing

15:52

being

15:54

d and notice this is a nice rectangular

15:57

pose set

15:58

um also so that's called a product of

16:00

Chains It's like a union of chains this

16:03

is a product of change we have a chain

16:05

here and a chain here and get a

16:07

rectangular uh post set

16:11

and to

16:12

go one step further and to analyze what

16:15

J of this thing is let's rewrite it in

16:18

other words we'll give these things some

16:19

different names

16:21

use a b c d e f g h i rather arbitrarily

16:26

okay that's the thing that we just

16:28

obtained but it's the same as opposed

16:30

that we've just relabeled it and then

16:31

we're able to write down what J of it is

16:35

in uh in a nice way okay so there's the

16:40

original thing and you can check all the

16:42

various ideals of this okay are

16:44

described by the elements in this posted

16:48

which is the lattice starting with the

16:50

empty set going down to the whole thing

16:52

which is the ideal generated by I

16:55

okay and you may notice that in here

16:58

there's a sort of a layer there's

17:02

these nine elements here forming this

17:05

sort of rectangular

17:07

uh post it just like the one that we

17:09

started and then there's another kind of

17:11

copy of it so down here and in some

17:14

sense you can sort of visually imagine

17:15

these things as being almost in three

17:17

dimensions here is one plane sort of

17:20

stacked on top of the other and inside

17:23

here there's a cube formed by these

17:26

eight here so this is the top of the

17:27

cube there is the bottom of the cube

17:29

there let's see so it has a little bit

17:32

of a three-dimensional aspect

17:36

okay so as we'll see this is a hugely

17:39

interesting line of inquiry in other

17:42

words the general issue what happens if

17:45

you start with some simple post set and

17:47

start taking J of it in other words

17:50

considering the ideals of that

17:53

particular post set and that generates a

17:55

new Post-it okay so it's a a natural way

17:57

of creating richer structure from

17:59

simpler structure

18:01

and it's um

18:03

a really interesting way of doing that

18:06

and

18:07

this will become a really interesting

18:09

for us as we investigate an example

18:11

which is sort of halfway between the two

18:13

that I showed you today where we'll

18:15

start with this post set P which has a

18:18

two chain and a single element A B C and

18:22

we'll see that just by playing this very

18:24

simple game of taking J's that were

18:28

essentially in some sense generating a

18:30

lot of the Ade story

18:33

so that there's this interesting sort of

18:36

combinatorial inductive approach to the

18:39

entire Ade picture which uh

18:43

which I think has a lot sheds a lot of

18:46

light on on further structure associated

18:50

with this Ade

18:52

this ad business