Merken

# The Lonely Runner Conjecture

Zitierlink des Filmsegments

#### Automatisierte Medienanalyse

## Diese automatischen Videoanalysen setzt das TIB|AV-Portal ein:

**Szenenerkennung**—

**Shot Boundary Detection**segmentiert das Video anhand von Bildmerkmalen. Ein daraus erzeugtes visuelles Inhaltsverzeichnis gibt einen schnellen Überblick über den Inhalt des Videos und bietet einen zielgenauen Zugriff.

**Texterkennung**–

**Intelligent Character Recognition**erfasst, indexiert und macht geschriebene Sprache (zum Beispiel Text auf Folien) durchsuchbar.

**Spracherkennung**–

**Speech to Text**notiert die gesprochene Sprache im Video in Form eines Transkripts, das durchsuchbar ist.

**Bilderkennung**–

**Visual Concept Detection**indexiert das Bewegtbild mit fachspezifischen und fächerübergreifenden visuellen Konzepten (zum Beispiel Landschaft, Fassadendetail, technische Zeichnung, Computeranimation oder Vorlesung).

**Verschlagwortung**–

**Named Entity Recognition**beschreibt die einzelnen Videosegmente mit semantisch verknüpften Sachbegriffen. Synonyme oder Unterbegriffe von eingegebenen Suchbegriffen können dadurch automatisch mitgesucht werden, was die Treffermenge erweitert.

Erkannte Entitäten

Sprachtranskript

00:04

it is my pleasure to welcome you 2 the colloquium I will make his announcement in English because Our speaker today is a visiting professor from cannot ask here for 6 weeks and I it is visiting mathematics and I'll from

00:25

its industry but medicine optimization my group he

00:30

has that is undergraduate degrees from Simon Fraser University and is master and his Ph.D. from the University of Waterloo work was movies but with an abundance it's our own the cycle public cover conjecture and we 1st met in 93 then Rutgers when I was doing the people stop

00:55

and he was visiting there also for 6 weeks but then we only match and conference by chance and 90 8 but I was very

01:04

surprised when I was invited by a In 2000 to a business conference and passed flows and that was started working together and we have been doing since then and I thought it would be nice if you would give a lecture in this call-up and since I'll like not only the title of this lecture but also the contents I suggested to do this romantic view as errand it turned out that is a nice coincidence that the the origin of this conjecture actually is

01:41

from Germany but was about and bye who has been working

01:48

for quite a while in Siegen and Bob we're very happy that he took the chance ever to come here and meet the godfather of this conjecture and so the Godfather its the origin later which I consider another piece of romance in this setting and that of the US I like what Louis dust because he believes in beauty and mathematics and

02:15

so stages yours Luis group

02:19

thank you very much and could feel thinking and thank you for your kind hospitality here I've had a wonderful visit and I think you have a wonderful and beautiful institution with

02:31

wonderful people when I had to come up with a poster we went looking through pictures of a lonely runner and we discovered this 1 year you'll see a little

02:42

lonely running here this might be Ireland center in north of north of Germany I'm not quite sure where where they are from but

02:54

so I'm going to tell you the conjecture informally I'm lonely when conjecture and I imagine that you have a circular track here and other you have 6 runners and they're going to run around the track and you are 1 of the runners you're the Redmond there and at at at the same time we all started lending going around in circles

03:18

and if you have ever been on a track running around you'll find that sometimes

03:24

you look in front or behind and you're lonely there's nobody nearby as of dioceses nobody near the front door behind and on what this conjecture that basically says is that at some time you must be lonely that is the

03:42

informal statement still formally the so 1st of all is what do I mean by well if we have 6 runners then by lonely I mean that nobody in France by 1 6 of a circle and nobody behind by 1 6 of a circle that's exactly the right

04:01

notion of lonely and we'll see why later so I just

04:06

that little animation that I made here I I hope that it works my only only 1

04:14

that I'm going to do so imagine

04:17

that you're the red loans money and here I've marked off 1 6 of a circle in front and 1 behind and I forget the storage area the research running imagine you have speed for and you see still not lonely there's still people in there Will you ever be lonely there are no all of the world and lonely there is nobody within the red circle we within the Red Stripe and I did the video that the point of the conjecture is this cannot be avoided OK so here's

05:00

another formal statement of the conjecture and it was originated by your veils

05:05

and thank you again for coming if there are any manners the red runner will be at least

05:12

1 overran from all others at the same time now I have to give you some assumptions resuming at all the runners start at the same time the 2nd is all runners must have a speed that is different from you now I have somebody has the same

05:28

speed then they will never the lonely and the 3rd is that everyone maintains a constant velocity and that they

05:37

do not get tired yeah so that's a little bit unrealistic I suppose so here it is for 2 runners can you convince

05:48

yourself that is true for 2 runners so here you are well yes I just wait till the other runner is half and half way around and that must happen eventually what about 3 runners can you

06:04

prove it to yourself or 3 runners in the A 3 runners than at some time you will be known well if you get bored during the lecture I invite you to prove this for yourself I'll give you

06:16

a solution a little bit later the it's an exercise

06:23

OK so the 1st assumption within a summer sun as assumptions to simplify the problem 1st of all but the red 1 should have speed 0 so you are the red 1

06:35

of your very lazy you should just sit there and watch the other runners now because if I'm running I can assume that I'm turning the track so that I'm not moving now so this makes it a little bit easier announces 6 runners have one-liner and 1 sister on the 2nd 1 is we can assume that all the speeds are rational numbers no this is not completely easy to prove that it was approved by Dr. Wells in 1967 you see

07:09

imagine if he had speed 1 and speed Part and

07:14

speedy suppose that the speeds were independent over the rational while the

07:20

behavior is going to be a Gothic In other words you can pre-specified a position on the track and if you wait long enough the runners will be within Absalon of where you predetermined it just completely messes so

07:37

if there is some linear dependence among the runners for example speed power and speed the and speed pipe well then you have to make a little bit more argument but I'm not going to go into that today but you can assume the speeds a rational if we can prove it in this case

07:55

and it's true for all speeds well we can make the speeds integers just multiplied by the denominator we can make the

08:06

greatest comment in divided to be 1 and also we

08:11

don't need any negative speeds a native speed means some running backwards and

08:17

and if I'm going to be a lonely running backwards or beer only lonely running from room to the front United symmetric so we have a velocity vector and our heroes but there you'll find them Maine many Louisiana 1 the red the 0 and then V-1 V-2 the fee of 2 billion minus 1 book is a better horse by 4 "quotation mark knocking I'm hoping this works so this summer this velocity vector is that all of actual positive images and then and if I take anyone

09:02

runner then at time he This is the distance please the

09:11

i in absolute value and this just means the smaller

09:16

of X minus a floor and the ceiling minus X now so how far you from half an integer essentially is a is in the distance now at time t the distance through the vector

09:30

is the smallest buddies and it is loneliness as measured by a distance to the law nearest right and I am when I'm interested in is the maximum loneliness overall

09:44

time so I'm going to take the

09:46

supremum overall but all the but this minimum and that's what I

09:52

call the LRC of the

09:55

the loneliness number of this factor and the conjecture Is

09:59

that for any as long as I don't

10:03

have 0 speeds but nobody else everybody should be running except me we have the loneliness loneliness director should have all the loneliness should be at least 1 over and at some OK so

10:17

here's a little but when the same we have a graphic way of viewing it so along the bottom we have the time going from 1 hour and and here we assume we have a runner speed 1 no wonder after half an hour at the other is far away distance one-half and then comes to this and 0 it's on the vertical axis is distance now imagine I had a on lower speed 3 so the blue Runner is doing 3 trends 3 laps in 1 hour suppose I had another runner speed for yeah the purple 1 and so the purported US 4 laps so how do you measure the loneliness while the loneliness as a distance to the nearest 1 so it's of the lower edge of this thing see that that is as loneliness at time t what I'm interested in is that the most lonely time which is 1 of these 2 peaks no and I'm hoping that about the the the the height of his peak is at least 1 quarter because we have 4 runners if you include me yeah myself and 3 more and so this out from this picture you can see them only 1 a conjecture holds true if those are the speeds them OK here's

11:50

another more complicated ones With without 5 different speeds so it should have a loneliness at least 160 and you see that it happened several times the

12:03

difficulty of this conjecture is that there is an infinity of love of speed factors attack

12:10

OK so here's a little bit of history it was stated in 67 by your wheels and restated by by choosing and 73 and is not clear it might have been independent Ross but I was all for 3 runners by year-end and then I he got

12:34

together was better care In 72 he suffered for 4 5 runners Cusick and Pomerantz solved

12:43

it proved it in 1984 but it was quite a long proof with some computer help and out with the help of for other people I improved does this proof In 1998 and I was

12:58

not interested directly in the conjecture I was using this this and this conjecture to help me proves something else but that's

13:06

why I needed to prove if refined manners I was not aware of the work of Cusick at the time

13:13

for 6 runners it was approved in 2001 In a very long paper 50 pages and Renault has simplified it to approve of 9 pages 4

13:24

7 runners there is a new part varying improved of

13:28

about 20 pages and I don't think that has been improved for 4 8 runners nobody knows the so there you go if you want to have a problem to drive you crazy you can try to prove there's a nice lower bound that I will show you 4 for any number of runners we can be a little bit lonely about half as lonely of what the other conjecture says the conjectures 1 over and we can prove 1 over 2 times and minus 1 for special speed said there are many papers now I didn't listen there's probably 20 papers what people that have proved well if the fastest runner as no more than twice as fast as the slowest 1 and it's true and well above many special cases of speed where the conjecture has been proved

14:24

on and wrote some work that I did with and with Eric 1 about 5 years ago I looked at the question Where

14:33

this is bound 1 over and achieved for watches speed sets do I actually never get lonelier than 1 over and so a lot will look at this event later while fearsome

14:45

applications Of this conjecture and that approximation this is so perhaps the origin of the conjecture it's quite a natural thing that venting approximation we're trying to do

14:58

users to approximate our real factors with rational vectors for example Cusick of reforming created this problem in terms of you obstruction and we'll talk about that later recently there's been some work with distance craft and the

15:18

chromatic number of these graphs so what is a distance graph imagine a graph where you have the vertices of the integers then I have a set of distances d and I joined to overseas with an edge if they are at distance whose that is a member of the no than 4 different sets the we can ask What is the chromatic number how many colors do I need to cover the vertices so that every edge connects to different colors and all this

15:48

is this sort of question the lonely mother conjecture that turns out to be a central tool in looking at these sorts of problems Graf and may

15:58

trade flows this is my paper from 98 and all recently I've been done something with or without review Hochstetler which is not yet submitted but I think it's hoping it's a correct involving grass gravel may trade flows and we'll talk about that a little bit later on number theory there is a beautiful the problem at called Challacombe signed problem which is very close simulated to lonely manner and I'll I'll show you tell you a a bit of that later and YG Chan has came come up with a new conjecture

16:37

while not news media 20 years New that is a slightly generals it's a generalization of the Roney runner conjecture I put it up here for you to look out but I won't I won't go into the details of it but I will say that that chance conjecture is stronger than the lonely conjecture for every number and for every number of miners if Challis conjecture is true then the lonely manner conjecture is true and also Chen managed approval for at most 5 runners as far as I know the can conjecture

17:09

is still unsolved for 6 runners so if you if the lonely matter conjecture is not hot enough for you you can try to prove this 1 OK so

17:23

I promise you a lower bound why why so lonely

17:30

mother conjecture says

17:32

that every set of Spain's Yulia loneliness 1 well I can prove a week

17:38

around 1 over 2 times minus 1 and the proof is really quite simple so here is a circle and here's what I'm seeing the red 1 and when I'm within 1 over and minus 1 on either side sorry that should be at 2 times and minus 1 if I'm within 2 times and minus 1 on

18:00

this side the 2 Johnson minus 1 year then I will be needed if you're on fire so this I'm sorry about this but

18:09

there should be a tube down here but there is out there now that should be 2 2

18:17

times and minus 1 so just take a random time now I just stopped the clock and say OK what is it what is the expectation that all the runners were far I'm going to show that this number is positive yeah and then if it's all I ever if at the random time the expectation that all the runners fire then I know at time I will be slightly lonely we do well it's 1 minus the expectation that some runner is near and and since this is this is a union intersection of of story unions of expectations here this is a mole at least one-liners the sum of the expectations of the runner I is near and in fact this is strictly greater than because at 1st everybody is near so we're not going to get quality here but this number is at most 1 over to and minus 1 sorry yeah won over to minus 1 because that's I got this wrong but what the 2 in the wrong place leisurely No to here so far this summer 1 of Ramires 1 because that's the that's the length of the new regions and so that's equal to 0 OK so there goes my Ron incorrect proof that it has some typographical errors so the 2nd thing is why 1 over while I claim that 1 over and his best possible In other words if I use for example if I use a Speed said 1 and minus 1 then the lonely runner a number is equal to 1 over and here

20:11

is an example here's a speed

20:13

said 1 2 3 4 5 I notice that there is no peak goes above 1 over 6 so that's the best possible number for this the proof is really easy again

20:27

for us to prove greater than or equal to his I just have to show you at time when everybody is at least 1 of runaway well just at the time 1 over and and this is the positions of the other runners I noticed that the nearest Reiner is 1 over at that time so you will see right

20:46

here this is 1 over 6 everybody is and he's 1 overran to prove the other

20:54

direction I just have to show that it every time there is some runner that is close to you None of some at every time there exists a runner at a distance of most 1 overran well suppose that we stopped the clock at time t and you say OK what do we have we have an runners on the track including the young so there exist 2 runners butter closer than 1 overran the pigeonhole principle yes souls suppose were 2 runners I and J that is closer than 1 over and or at most 1 overran including myself while here it in enough in symbols 1 overran is at least the difference between the Times Jr and he turns up while I do respect throughout the and I have taken Jamal Anderson so what is J. well I have worlds

21:56

I have 2 numbers between 0 and minus 1 so Sergei minus I must be a number between 1 and minus 1 and and minus 1 yeah so this is the number of someone there was a writer and a runner that has US PGA design and at that time the runner has assistance at most 1 over so that shows that every time there was somebody new so I cannot improve I 1 over and 2 into a better numbers in the conjecture all right

22:27

so that anybody managed to solve the exercise How do you prove that there conjecture for 3 runners well good let's see we can assume the speeds of 0 B-1 and B-2 yeah now consider the time the 1 divided by 3 so where is the 1 at this point all the winners over here 1 3rd of the way around the circle yeah but the 2 faster the 2 is ahead the others 2 cases maybe becuase less than twice as fast yeah if he too lessened prices because then he must be some up here and we're finished I'm lonely about .period right the 2nd case it is the truth is more than twice as fast you also hear the Jews running over here and this letter feels like I better do more exercise because this 1 is so fast enough so in this case were not solid if the idea well I think about the next party if you want yeah almost just think about the time period when the slower runners is far along here so when the slow runner runs 1 3rd the fastest runner runs more than two-thirds so if you run more than two-thirds you cannot avoid the new regions you must be this at some time so every proof that I know for this case needs at least 2 cases now and that's typical for the proof of 8 runners you knew about 25 cases no against the proves that very complicated because you have to say Well if the this runner is more than twice as fast as this or that I have to divide up the cases in some clever way and have a different argument for each case this is 1 reason why we're not having very much success proving the conjecture OK the obstruction

24:59

so are Jews a could gave a nice geometrical interpretation of runner and this is how it goes so here in this corner I am not I'm standing in the red or and I have here but the plane and in the middle of each unit where I have a small blue square and imagine that I cannot see through I can see I can I can look but I cannot see through Blue Square now when the question is can I look in the direction of the positive often and see the stars can I look to infinity while its novel no fair of course I can look this direction look to infinity but if I have to look with positive slope then they can idea how far can look what In this case if I look in this direction I can look all the way to the to infinity while 1 of the major squares that now I can

26:05

only look as far no well many of my still look in a different direction I can see farther and 0 yes I can have a look in this direction I can just yes I can just see to infinity all of those so the question is what size of blue squares completely obstructs my vision if I go even bigger I'm completely

26:30

obstructed this year cannot see to infinity anywhere and the sky is black and I think the world is going to end no so In this case the answer is

26:43

1 3rd 1 3rd as soon as I have the squares of size one-third I'm completely obstructed if it's smaller one-third than I can see if I could just in the right direction OK so that the are question can be asked

27:02

for higher dimensions if I'm a three-dimensional grid standing where am I say I'm standing right here now can look into the path of positive Worthington see this How big little squares have to be the choose how they didn't have to be and here here's the answer is one-half well this is why it's called you obstruction those cues are obstructions to your view of the sky and here is

27:37

a connection with only minor it turns out that this problem is exactly equivalent to the lonely conjecture so In dimension he the minimum size queues which obstructs the strictly positive is this number here 1 minus 2 times lonely run a number 4 GPs one-liners so I made a little table we know the amount conjecture is true for up to 7 runners and so we know exactly how big the cubes must be to obstruct all the way to 6 dimensions for 7 dimensions we don't know the answer yes because we don't know that only minor number between 1 or 14 and 1 over 8 so as soon as we prove the lonely monarch conjecture here we will know something about the 7 dimensional view obstruction OK the nice thing about view

28:39

obstruction is that makes a nice if possible to make interesting variations on the question so here is a lonely mother conjecture game for kids and instead of asking that all of the points or at least 1 over em away while many always under back for a 2nd

29:01

I want to tell you why the lonely runner conjecture is equivalent Our the direction

29:12

that I look here here this direction is a vector 1 too yeah so this that this direction this vector 1 2 is the saddest speeds that will avoid being far but that there will avoid hitting of the area know what does it mean to be a veterinarian to be in a blue

29:34

area means that all the runners on the farm From 0 None of all the runners are far from 0 then you will be obstructed so far what you're asking is how big business region have to be before I guaranteed that at some some point everybody will be far it's equivalent to saying how big do the kids have to be before my view is obstructed so

30:05

saying that everybody is at his distance I and from me is the same as saying everybody is the most distance and minus to over to and from the opposite side of the track him so this is just a restatement of Iran conjecture is that there exists at times when among all the runners the 1 that is furthest from one-half half distance at most and to over to and from 1 house I call this the AL infinity norm because we have a maps so what if instead of 1 being lonely according to the max and I'm worried about being lonely on average so this is being L 1 only so I suppose I'm very sociable and I'm running and I will be lonely even if there's somebody near I'll be lonely if most of the people are far away now In other words that I want the average distance to the FAA so this changes the definition of lonely to the L 1 on I'm here I'm now obstructing the view with what did he go you're a cross-party talks in general ya well we can have different types of questions what about death L

31:32

True North how big fears have to be before the abstract the the sky and that is just asking the How and I'm looking forward the furthest for them the air minimum value all of this but I can guarantee that sometimes so that's being alone in the mean square you here's 1 which which accuse it did not know about there was a there is a problem from 1965 it's well known from number theory called

32:13

the Italico problem and the problem is as follows here I want to minimize the sum of the call signs of this so what am I doing while the shape that you get here you lose something between a sphere and Lockheed no source the kind of rounded and what it means if we go back to the track

32:42

is a time here and the runners a running no as a call sign the call sign is going to be the X coordinator no so where so I will be lonely if the average of the X coordinates is small this far from me so what is the smallest average of the X coordinates that I can guarantee and the number of theories

33:08

have really put a lot of effort

33:10

into this question and that all admonish approved is at the center of mass is between minus and 1 . 3 4 to the power of rude like so it's quite a big gap nobody knows very much more about the charmer "quotation mark problem which is not surprising because it's not going to be any easier then the lonely runner conjecture I want to tell you

33:40

about some work that I did with Eric won in 2006 some Eric Wong was supposed stock Boveja student at at the time at the University of British Columbia and and he came to me 1 day and said you know I was wondering at what speed said satisfied equality you might say Well yeah speed said 1 2 3 4 Upton minus 1 suggest but are there any others any other Speed said Fernando what would you do if you wanted to answer this question he wrote a computer program that so we will become a computer program to look for sport speeds of runners under tight so for 2 runners 0 1 that's the only 1 while of course 0 2 0 3 but I'm assuming the greatest common devises 1 4 3 miners this is the only Speed said that achieves a quality every other speeds said has a peak the goes above the line for any calls for this is unique but for equals 5 we found it very strange said if you used if you take away runner number 2 and put him on a number 7 you also get another state Speed said and then we found some more for 6 runners we found take away the Truman substitute 9 we get another trades he said 4 7 runners we found no others for 1 as found to others results of 2 and 3 by 11 13 or substitute speed 6 and double at to 12 so with this keep running the program I'll just show you another you have it I took

35:31

away all the boring ones these are all the interesting ones that we found that the 20 so the 1 4 5 or 6 2 2 4 8 we found 1 441 for 20 well we looked at this for a while said do we see any patterns well maybe you will notice that here we took 6 and double his Speed-the-Plow here we took 12 double the speed to 24 the last 1 we take 18 double the speed 36 In those 3 cases got another set of runners that's never got more than 1 over and lonely well as soon as you see a pattern mathematicians are happy right let's see if we can prove something so the question is when can I take as a runner and double his speed and get another tight set of runners here is

36:33

a summary these are the stories strange ones I don't know where they come from I cannot explain why they work but these are the ones that pattern where I've doubled the speed but I notice that the speed that I double is 1 of the fastest in the 2nd 2 passes In each case so we said Well let's see what else we can do we will a special program that would take up the speed of a nearly fastest runner and Double-A Triple-A and we

37:04

found more examples 1st of all I want to show you just what happens with this strange 1 with 2 2 7 so here's a year so that the dispute of what happens with 5 runners speeds 1 to 5 now I take away 1 I took away the pink ones and so notice of this peak is going above the line where great it's going above the line because because this is pink when is not there to stop you from going there is so you're you're you're very lonely at this point but now I'm going to set a substitute 7 a Notice of 7 comes down and jails exactly cuts off In the then that just happens to be that just just cut it off perfectly and we get another Tate said there's something special about substituting 2 was 7 similarly thing

38:10

happens when I doubled from 6 to 12 with 8 runners and I take away the pain I get a peek that's too high but if I double the runner double the speed it's still isn't enough to cut away the peak so something very special about having this number of runners and and doubling the 2nd fastest runner because if it doesn't happen very often so here is

38:39

our special programs we found very many others examples doubling 18 to 26 24 to 48 doubling the 3rd fastest runner From the 13 260 or from 1 from 60 to 120 these taste sometimes I can multiply the speed of a runner by 4 so here I took this the runners 1 0 sorry this is the 4th graf passes have a set of runners from 0 to 73 74 runners cyclists runners 17 a double his speed the 140 and its state so that we look at this do we have any patterns while this took us a little while but we

39:27

managed to prove something windows accelerating the single runner make a speed a tight Speed said so here I've taken it has run a number of fire are and multiplied speed by and and I got another tight Speed said so I would be noticed are of M R & Co colon and so this means I multiply are by em In this for I haven't runners the and here's the thing I

40:03

want to out just state that their Manokin approving the Speed said the RMN is tight if and only if are is not relatively prime to any of the numbers between S & M S minus 1 and as is the difference between armed in an hour so for example also asked would be too if I celebrate the second-fastest runner forestry if I accelerate the third-fastest 1 in so here is an example Our here I am going to accelerate the 2nd fastest runner by a factor of 2 yeah so I checked I I rate the set to 3 up to MR minus 1 so just 2 and 3 and I want to find a number that's not relatively prime to 2 and 3 while 6 is the smallest wondering so this means that if poor article 6 then it will satisfy there so this and this case history all are resolved that we take the runners from 1 to 8 and speed number 6 double his speed it's another takes place and here's another example From this role here if I want to take the 2nd fastest runner and multiplied his speed by 4 revised 3 I should take part of Article 70 selected 72 runners I multiplied this 1 speed by 3 United States speeds so we're very happy with this and the proof is just elementary number theory but is actually quite intricate it was quite complicated several pages and but but it was good enough to get published anyhow you might ask about accelerating

42:02

many speeds now he is just another example of a lot of

42:08

separating many speeds so here I took on several miners are 1 2 up to Arcade and I accelerate them like this it turns out that sometimes this will also give us the plate speeds it will give us a tight speed said under a very similar condition that each number are is not relatively prime to any of the numbers in this interval now unfortunately this theorem is only a sufficient condition it's not necessary so the previous result was if and only

42:42

if and the other 1 is only

42:45

if we could not through the Congress so of course there's something for you to try to prove if you like an obvious question

42:57

can we find any other tight speed sets that are not covered by this theory except for the 3 history sporadic once we don't have a patent for them but those are the only ones checked and we checked all the speed sets up to I think 50 US speed 150 runners or something we did a huge computer check and we never found any other tight speed sets OK I think it is going to

43:26

give you 1 last applications In this is some work that I've done within the Hochstetler and it's a little bit technical and I'm not going to motivate very much drama In the end the theory of flows and calories of graphs a lot of Lord of the properties of of of flows and graphs and countries of grass come from the property that the but incidence matrix of a graph is totally you know so what do I mean by this so what is a graph I have some points yeah for 82 points I draw edge that has a table and ahead yeah from here to there from here to here now and that's a graph With directions and then you can ask a question how many colors to I need in order to cover the vertices so that if 2 marriages are connected than they get different colors that's a coloring problem progress it's a very a fundamental problem in referee while we can represent a graft by matrix so the matrix for for every edge that I for every vertex have a role yeah every vertex have a role and for every edge I put it :colon With a minus 1 and A 1 now a minus 1 at the tail and a 1 at the head so I get a special make matrix but it's called the incidence matrix of a graph well 1 of the special properties of this matrix is that if I take any square some matrix and find calculate the determinant the determination is always either 0 or plus or minus 1 it's a very special property about incidence matrix of directed graphs and this property is is very important in operations research it has a name totally know margin matrix is totally you know modular if every sub determined lies In this sense 0 plus or minus 1 so I 1 question you can ask you what do totally matrices looked like where they come from the 1 1 example comes from grafts like the 1 I just told you you can make other examples by doing it Arroyo operations now that permitting Collins multiplying rows and columns by negative 1 their operations that you can use that preserve the property of totally in the model another thing you can do it is taking the inverse matrix we're not the universe as sort of a dual matrix of this the Paula matrix all that and that also has a total you larger representation so we have these examples of of matrices that told you know Marjorie and it was a beautiful there Paul Seymour 1971 I think and he proved that every totally you know modular matrix comes from a grass In this way In other words I can take a graph and I do some operations to get another matrix take another graph do some operations to get another matrix and then I conclude these matrices together In 1 of 3 special ways and I'll get a totally you know matrix and there's 1 other special matrix that is out 5 by 5 but which is also told the United and by gluing together those matrices in special ways we can get every possible total unilateral matrix and it's a very famous there and it's also known as the composition of regular Majorie as maybe operations reaches people very happy so why do operations research people like this told United well suppose and solving in an integer linear program yeah I'm aware serial matrix to constrain matrix wow since the determinant is plus or minus 1 every solution if the right hand side is integer every solution Will the integer value every solution of a linear program will be integer value because of Cramer's rule cream Israel tells you how to solve for the coordinates the level of vertex they all must be averages because on the numerator we have an integer determined and on the nominator we have plus or minus 1 so well for this reason it's easy to solve integer programs for network flows yet we all learn about network flows and we have this nice integer property and that's because of told you modulated so here is a property of total you know Marjorie matrices which seems a little bit artificial it becomes a little more natural when you've been studying flows and calories of of grass and so the question is I'm going to give you a set of not of real number and I want to know Is there a vector that it is in the null space in the kernel of this matrix and every entry of Long to assess so if I give you a matrix and asset then the answer is yes or no so here's a suppose that I give you a sense of fewer than different elements then I have another error on the side because I also want the property that s does not contain the number 0 In case so I have a set of non-zero real numbers S and supposedly better no so we have we have it in and an S flow F as flow suppose we haven't as where as then the matrix hasn't as prime flow where all the entries Art from this particular said so what does this mean if I can find but an element of the null space where the entries are 1 8 and 13 then I can find another element of another element of the of the null space where all the entries are 1 2 and 3 yes in absolute value I only do things up to us and value so this is somehow saying that the most difficult coloring problems were the most difficult flow problems come when you're targets set is an interloper 1 and and this is a property with people study flows would find comforting because these things are known as Noah 0 and and they were studied and and introduced by Bill Totten 19 so here is a relationship 2 lonely runner conjecture if the lonely runner conjecture is true for and runners then this theory is true foreign runners so this is a weaker version of the law only minor conjecture it is this well however we prove that well we just assume that the entries in Nassau the speeds of the runners yeah and we ran runners until until the lonely and then at that point we get some other kind of flow With the entries are in here that's a very rough description we have to talk we have to know what do some modular arithmetic and and some other traits using told you modularity but that's roughly the idea if we could prove that loaning money conjecture then we could prove this another injure 1 interesting artifact about this proof is that in order to prove this we had to use that fact alone amounted conjecture is true for 5 runners we don't need it for 6 runners or war because of another beautiful theorem of Seymour regarding called the 6th Floor theory regarding graphs the 4 5 runners unless we knew them only when a conjecture to prove this theory so maybe this is a little bit of evidence that lonely kind rather lonely runner conjecture might be true because here's something that's a little bit weaker which is true and the proof is really not trivial OK I'm going to finish just talk now with just the 1 question I don't know of

53:19

anybody who has looked at the problem is 1 of the runners do not have to start at the same place on the track yeah he just arrived and people around .period jogging around the track and you start running with them now now do you have to be lonely well yes at some point you will be lonely as long as the the other people don't have exactly the same speed and are not running beside you then at some point you will be quite lonely but how long will you be or perhaps it's just my ignorance or I don't the literature but I don't know anybody who has looked at this problem as far as you obstruction goes this is equivalent to saying well maybe I want to see this guy but I don't have to stand at the origin I can stand somewhere else and said look for the sky no on the eye can see and hear so I leave you with this question and I also thank you very much for listening to this talk the

54:32

Louise posts in the government the lecture other questions His 1st

54:41

thing during much of the wonderful when we thank you for your wonderful told to remarks wanders through the last question and I think that in connection with a view obstruction problems that there are 2 research students of Mumbai Bombay was money year and I think the legend 100 here and in the years that Nunavut I don't know his 1st name maybe I have the feeling that at least the question was posed by In the

55:17

2nd historical remark cuisine I mean the

55:20

name you look selection is definitely due to Quezergue yes but he knew of the problem from myself it's clear we met at the conference and niece where all the but we will love us fears and I talked to many always with him about this problem because he's my 1st papers were written in German he didn't understand and will explain what I wanted to find out and I mean he made progress but definitely had the problem of and his wife didn't mention me in the last

55:57

newspapers I don't know I mean it hopefully will assist in oversight of gas from time to time while OK thank you and these are the real grandfather of this conjecture and long may very well thank you no further

56:15

questions well it's not

56:23

then thank you

00:00

Erweiterung

Mathematik

Minimierung

Dreiecksfreier Graph

Gruppenkeim

Mathematik

Computeranimation

Überlagerung <Mathematik>

00:54

sinc-Funktion

Mathematik

Inhalt <Mathematik>

Massestrom

Computeranimation

01:39

Mathematik

Gruppenkeim

Mathematik

Computeranimation

02:31

Weg <Topologie>

Kreisfläche

Formale Potenzreihe

Mathematik

Computeranimation

Normalvektor

03:17

Weg <Topologie>

Kreisfläche

Schmelze

Einheit <Mathematik>

Rechter Winkel

Formale Potenzreihe

Mathematik

Gravitationsgesetz

Computeranimation

Gesetz <Physik>

04:00

Punkt

Kreisfläche

Flächeninhalt

Verschlingung

Formale Potenzreihe

Gewichtete Summe

Mathematik

Computeranimation

04:55

Formale Potenzreihe

Mathematik

Computeranimation

Gesetz <Physik>

05:47

Mathematik

Computeranimation

Gesetz <Physik>

06:34

Weg <Topologie>

Rationale Zahl

Mathematik

Computeranimation

07:18

Bruchrechnung

Lineare Abhängigkeit

Parametersystem

Ganze Zahl

Ortsoperator

Mathematik

Computeranimation

Leistung <Physik>

08:06

Geschwindigkeit

Ganze Zahl

Vorzeichen <Mathematik>

Mathematik

Symmetrische Matrix

Computeranimation

09:00

Abstand

Betrag <Mathematik>

Rechter Winkel

Extrempunkt

Ganze Zahl

Mathematik

Vektorraum

Abstand

Extrempunkt

Gesetz <Physik>

Obere Schranke

Computeranimation

09:42

Extrempunkt

Zahlenbereich

Kartesische Koordinaten

Mathematik

Extrempunkt

Teilbarkeit

Obere Schranke

Computeranimation

Prädikatenlogik erster Stufe

Abstand

Minimum

Abstand

Neunzehn

11:49

Vorlesung/Konferenz

Mathematik

Teilbarkeit

Computeranimation

Gesetz <Physik>

Unendlichkeit

12:33

Beweistheorie

Mathematik

Gleitendes Mittel

Zeitzone

Computeranimation

13:24

Offene Menge

Mereologie

Zahlenbereich

Mathematik

Menge

Computeranimation

14:22

Offene Menge

Diophantische Gleichung

Approximation

Kartesische Koordinaten

Mathematik

Vektorraum

Ausgleichsrechnung

Term

Menge

Ereignishorizont

Teilbarkeit

Computeranimation

Approximation

Menge

Reelle Zahl

Rationale Zahl

Schätzung

TVD-Verfahren

Vorlesung/Konferenz

Abstand

Zeitzone

15:17

Diophantische Gleichung

Graph

Mathematik

Ungerichteter Graph

Massestrom

Computeranimation

Approximation

Graph

Abstand

Knotenmenge

Elementare Zahlentheorie

Menge

Verschlingung

Ganze Zahl

Sortierte Logik

Zahlenbereich

Physikalische Theorie

Endlicher Graph

TVD-Verfahren

Kantenfärbung

Abstand

Innerer Punkt

16:35

Graph

Abstand

Diophantische Gleichung

Zahlenbereich

Physikalische Theorie

Endlicher Graph

TVD-Verfahren

Zahlenbereich

Mathematik

Computeranimation

Approximation

17:21

Kreisfläche

Mathematik

Gleitendes Mittel

Untere Schranke

Ausgleichsrechnung

Computeranimation

Gesetz <Physik>

Zufallszahlen

Menge

Gewicht <Mathematik>

Beweistheorie

Beweistheorie

Aussage <Mathematik>

18:08

Länge

Gewichtete Summe

Schmelze

Zahlenbereich

Mathematik

Gleitendes Mittel

Untere Schranke

Stichprobenfehler

Computeranimation

Erwartungswert

Zufallszahlen

Gewicht <Mathematik>

Beweistheorie

Vorlesung/Konferenz

Beweistheorie

Aussage <Mathematik>

20:08

Ortsoperator

Beweistheorie

Zahlenbereich

Mathematik

Extrempunkt

Computeranimation

Gesetz <Physik>

Aussage <Mathematik>

20:52

Abstand

Subtraktion

Weg <Topologie>

Verschlingung

Zahlenbereich

Mathematik

Abstand

Extrempunkt

Computeranimation

Aussage <Mathematik>

Gesetz <Physik>

Richtung

22:26

Parametersystem

Punkt

Kreisfläche

Mathematik

Frequenz

Computeranimation

Richtung

Unendlichkeit

Quadratzahl

Einheit <Mathematik>

Beweistheorie

Quadratzahl

Geometrie

Beweistheorie

26:03

Quadratzahl

Länge

Mathematik

Quadratzahl

Computeranimation

Gesetz <Physik>

Richtung

27:01

Ortsoperator

Extrempunkt

Tabelle

Hausdorff-Dimension

Länge

Zahlenbereich

Vorzeichen <Mathematik>

Mathematik

Extrempunkt

Pi <Zahl>

Computeranimation

Quadratzahl

Verschlingung

Würfel

Dimension 3

Würfel

Warteschlange

Quadratzahl

28:36

TVD-Verfahren

Länge

Mathematik

Vorzeichen <Mathematik>

Vektorraum

Extrempunkt

Computeranimation

Richtung

Gesetz <Physik>

Flächeninhalt

Spieltheorie

TVD-Verfahren

Würfel

Quadratzahl

29:33

Subtraktion

Punkt

Konvexe Hülle

Extrempunkt

Länge

Vorzeichen <Mathematik>

Mathematik

Extrempunkt

Fastring

Computeranimation

Unendlichkeit

Gesetz <Physik>

Weg <Topologie>

Flächeninhalt

TVD-Verfahren

Würfel

Quadratzahl

Abstand

Normalvektor

31:31

Gewichtete Summe

Extrempunkt

Unrundheit

Mathematik

Gerichteter Graph

Computeranimation

Gesetz <Physik>

Elementare Zahlentheorie

Weg <Topologie>

Quadratzahl

Kugel

Vorzeichen <Mathematik>

TVD-Verfahren

Zeitzone

32:40

Länge

Zahlenbereich

Ruhmasse

Vorzeichen <Mathematik>

Mathematik

Extrempunkt

Physikalische Theorie

Computeranimation

Verschlingung

Vorzeichen <Mathematik>

Mittelwert

TVD-Verfahren

Würfel

Quadratzahl

Koordinaten

33:36

Resultante

t-Test

Zahlenbereich

Mathematik

Extrempunkt

Menge

Computeranimation

Eins

Differenzkern

Menge

Mathematikerin

Substitution

Optimierung

Gerade

Aggregatzustand

36:29

Punkt

Mathematik

Substitution

Optimierung

Menge

Gerade

Computeranimation

Gesetz <Physik>

Eins

38:09

Last

Vier

Menge

Einheit <Mathematik>

Raum-Zeit

Zahlenbereich

Mathematik

Optimierung

Innerer Punkt

Menge

Computeranimation

39:27

Subtraktion

Theorem

Zahlenbereich

Mathematik

Teilbarkeit

Menge

Computeranimation

Elementare Zahlentheorie

Menge

Zustandsdichte

Beweistheorie

Mereologie

Aggregatzustand

42:02

Inklusion <Mathematik>

Resultante

Theorem

Rechter Winkel

Zahlenbereich

Theorem

Konditionszahl

Zahlenbereich

Mathematik

Gleitendes Mittel

Menge

Computeranimation

42:45

Randverteilung

Matrizenrechnung

Punkt

Mathematik

Kartesische Koordinaten

Element <Mathematik>

Ungerichteter Graph

Kardinalzahl

Inzidenzalgebra

Massestrom

Gesetz <Physik>

Determinante

Raum-Zeit

Computeranimation

Eins

Richtung

Übergang

Sechs

Deskriptive Statistik

Gruppendarstellung

Regulärer Graph

Theorem

Nominalskaliertes Merkmal

Nichtlinearer Operator

Kategorie <Mathematik>

Tabelle

Bimodul

Menge

Betrag <Mathematik>

Ganze Zahl

Sortierte Logik

Rechter Winkel

Zahlenbereich

Beweistheorie

Lineare Optimierung

Ordnung <Mathematik>

Beweistheorie

Nebenbedingung

Theorem

Total <Mathematik>

Fächer <Mathematik>

Matrizenrechnung

Vektorraum

Zahlenbereich

Auflösung <Mathematik>

Stichprobenfehler

Physikalische Theorie

Knotenmenge

Arithmetische Folge

Reelle Zahl

Grundraum

Aussage <Mathematik>

Beobachtungsstudie

Fundamentalsatz der Algebra

Matrizenring

Determinante

Graph

Operations Research

Schlussregel

Primideal

Vektorraum

Menge

Invertierbare Matrix

Energiedichte

Übergangswahrscheinlichkeit

Quadratzahl

Hill-Differentialgleichung

Kantenfärbung

Numerisches Modell

53:18

Weg <Topologie>

Punkt

Weg <Topologie>

Mathematik

Computeranimation

Gesetz <Physik>

54:37

Einfach zusammenhängender Raum

Weg <Topologie>

t-Test

Mathematik

Computeranimation

Gesetz <Physik>

55:20

Arithmetische Folge

Weg <Topologie>

Trennschärfe <Statistik>

Mathematik

Computeranimation

56:13

Weg <Topologie>

Mathematik

Computeranimation

### Metadaten

#### Formale Metadaten

Titel | The Lonely Runner Conjecture |

Serientitel | Kolloquium der Fakultät für Mathematik und Informatik der FernUniversität in Hagen |

Autor | Goddyn, Luis |

Lizenz |
Keine Open-Access-Lizenz: Es gilt deutsches Urheberrecht. Der Film darf zum eigenen Gebrauch kostenfrei genutzt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden. |

DOI | 10.5446/18565 |

Herausgeber | FernUniversität in Hagen |

Erscheinungsjahr | 2012 |

Sprache | Englisch |

Produzent | FernUniversität in Hagen |

#### Inhaltliche Metadaten

Fachgebiet | Mathematik |

Abstract | Suppose that N runners are running laps on a circular track. Each runner has a constant speed that is different from all the others. A runner is lonely whenever there is no other runner closer than 1/N of a lap. Is it true that every runner will be lonely at some time? Jörg Wills conjectured in 1965 that the answer is always yes. This problem is not yet solved for more than seven runners. Yet its solution would have consequences in computational geometry, diophantine approximation and graph coloring. |