Merken
The Lonely Runner Conjecture
Zitierlink des Filmsegments
Automatisierte Medienanalyse
Diese automatischen Videoanalysen setzt das TIBAVPortal 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 callup 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 oneliner 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 prespecified 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 V1 V2 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 onehalf 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 yearend 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 oneliners 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 B1 and B2 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 twothirds so if you run more than twothirds 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 onethird I'm completely obstructed if it's smaller onethird 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 threedimensional 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 onehalf 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 oneliners 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 onehalf 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 crossparty 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 SpeedthePlow 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 DoubleA TripleA 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 secondfastest runner forestry if I accelerate the thirdfastest 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 nonzero 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
Minimalgrad
Mathematik
Konvexe Hülle
Minimierung
Dreiecksfreier Graph
Gruppenkeim
Mathematik
Computeranimation
Überlagerung <Mathematik>
00:54
sincFunktion
Mathematik
Inhalt <Mathematik>
Massestrom
Computeranimation
01:39
Mathematik
Gruppenkeim
Mathematik
Computeranimation
02:31
Weg <Topologie>
Kreisfläche
Mathematik
Computeranimation
03:17
Weg <Topologie>
Kreisfläche
Konvexe Hülle
Rechter Winkel
Mathematik
Computeranimation
04:00
Punkt
Kreisfläche
Flächeninhalt
Mathematik
Computeranimation
Inverser Limes
04:55
Mathematik
Computeranimation
05:47
Konvexe Hülle
Vorzeichen <Mathematik>
Mathematik
Computeranimation
06:34
Weg <Topologie>
Rationale Zahl
Rationale Zahl
Vorzeichen <Mathematik>
Mathematik
Computeranimation
07:18
Bruchrechnung
Parametersystem
Lineare Abhängigkeit
Ganze Zahl
Ortsoperator
Rationale Zahl
Größter gemeinsamer Teiler
Mathematik
Vorzeichen <Mathematik>
Computeranimation
Leistung <Physik>
08:06
Geschwindigkeit
Ganze Zahl
Rationale Zahl
Größter gemeinsamer Teiler
Mathematik
Vorzeichen <Mathematik>
Symmetrische Matrix
Computeranimation
09:00
Abstand
Betrag <Mathematik>
Rechter Winkel
Extrempunkt
Ganze Zahl
Mathematik
Vektorraum
Abstand
Extrempunkt
Gesetz <Physik>
Computeranimation
09:42
Abstand
Extrempunkt
Minimum
Zahlenbereich
Mathematik
Kartesische Koordinaten
Abstand
Extrempunkt
Teilbarkeit
Computeranimation
11:49
Mathematik
Teilbarkeit
Computeranimation
Unendlichkeit
12:33
Beweistheorie
Mathematik
Computeranimation
13:24
Mereologie
Zahlenbereich
Mathematik
Menge
Computeranimation
14:22
Diophantische Gleichung
Approximation
Kartesische Koordinaten
Mathematik
Vektorraum
Term
Ereignishorizont
Teilbarkeit
Menge
Computeranimation
Approximation
Menge
Reelle Zahl
Rationale Zahl
TVDVerfahren
Abstand
15:17
Diophantische Gleichung
Graph
Mathematik
Matroid
Ungerichteter Graph
Massestrom
Computeranimation
Approximation
Graph
Abstand
Knotenmenge
Elementare Zahlentheorie
Menge
Ganze Zahl
Sortierte Logik
Zahlenbereich
Physikalische Theorie
Endlicher Graph
TVDVerfahren
Abstand
Kantenfärbung
16:35
Abstand
Graph
Diophantische Gleichung
Zahlenbereich
Physikalische Theorie
Endlicher Graph
TVDVerfahren
Zahlenbereich
Mathematik
Matroid
Computeranimation
Approximation
17:21
Zufallszahlen
Kreisfläche
Menge
Beweistheorie
Mathematik
Beweistheorie
Computeranimation
18:08
Dicke
Erwartungswert
Zufallszahlen
Gewichtete Summe
Beweistheorie
Zahlenbereich
Mathematik
Beweistheorie
Stichprobenfehler
Computeranimation
20:08
Ortsoperator
Beweistheorie
Zahlenbereich
Mathematik
Beweistheorie
Computeranimation
20:52
Evolutionsstrategie
Subtraktion
Weg <Topologie>
Zahlenbereich
Mathematik
Abstand
Beweistheorie
Computeranimation
Richtung
22:26
Parametersystem
Kreisfläche
Punkt
Mathematik
Frequenz
Computeranimation
Richtung
Unendlichkeit
Quadratzahl
Einheit <Mathematik>
Beweistheorie
Quadratzahl
Geometrie
Beweistheorie
26:03
Quadratzahl
Konvexe Hülle
Mathematik
Quadratzahl
Computeranimation
Richtung
27:01
Ortsoperator
Extrempunkt
Tabelle
HausdorffDimension
Formale Potenzreihe
Zahlenbereich
Mathematik
Extrempunkt
Computeranimation
Quadratzahl
Würfel
Dimension 3
Würfel
Warteschlange
Quadratzahl
Aussage <Mathematik>
28:36
TVDVerfahren
Konvexe Hülle
Mathematik
Vektorraum
Extrempunkt
Computeranimation
Richtung
Flächeninhalt
Spieltheorie
TVDVerfahren
Würfel
Quadratzahl
Aussage <Mathematik>
29:33
Subtraktion
Punkt
Extrempunkt
Mathematik
Fastring
Extrempunkt
Computeranimation
Unendlichkeit
Weg <Topologie>
Flächeninhalt
TVDVerfahren
Würfel
Abstand
Quadratzahl
Normalvektor
Aussage <Mathematik>
31:31
Weg <Topologie>
Elementare Zahlentheorie
Gewichtete Summe
Kugel
Quadratzahl
Vorzeichen <Mathematik>
Extrempunkt
TVDVerfahren
Mathematik
Unrundheit
Extrempunkt
Gerichteter Graph
Computeranimation
32:40
Formale Potenzreihe
Zahlenbereich
Ruhmasse
Mathematik
Extrempunkt
Physikalische Theorie
Computeranimation
Existenzsatz
Mittelwert
Vorzeichen <Mathematik>
TVDVerfahren
Würfel
Quadratzahl
Koordinaten
Aussage <Mathematik>
33:36
Resultante
tTest
Zahlenbereich
Mathematik
Menge
Computeranimation
Eins
Differenzkern
Menge
Mathematikerin
Substitution
Optimierung
Gerade
Aggregatzustand
36:29
Punkt
Mathematik
Substitution
Optimierung
Menge
Gerade
Computeranimation
Eins
38:09
Vier
Menge
Zahlenbereich
Mathematik
Optimierung
Menge
Computeranimation
39:27
Elementare Zahlentheorie
Subtraktion
Menge
Beweistheorie
Mereologie
Zahlenbereich
Mathematik
Extrempunkt
Menge
Teilbarkeit
Computeranimation
Aggregatzustand
42:02
Resultante
Zahlenbereich
Konditionszahl
Theorem
Zahlenbereich
Mathematik
Menge
Computeranimation
Normalvektor
42:45
Randverteilung
Matrizenrechnung
Punkt
Mathematik
Kartesische Koordinaten
Element <Mathematik>
Ungerichteter Graph
Kardinalzahl
Inzidenzalgebra
Massestrom
Gesetz <Physik>
Determinante
RaumZeit
Computeranimation
Eins
Richtung
Übergang
Deskriptive Statistik
Sechs
Gruppendarstellung
Regulärer Graph
Theorem
Nominalskaliertes Merkmal
Nichtlinearer Operator
Kategorie <Mathematik>
Tabelle
Bimodul
Menge
Betrag <Mathematik>
Sortierte Logik
Ganze Zahl
Rechter Winkel
Zahlenbereich
Beweistheorie
Lineare Optimierung
Ordnung <Mathematik>
Beweistheorie
Nebenbedingung
Theorem
Total <Mathematik>
Matrizenrechnung
Vektorraum
Zahlenbereich
Auflösung <Mathematik>
Stichprobenfehler
Physikalische Theorie
Knotenmenge
Arithmetische Folge
Reelle Zahl
Modelltheorie
Grundraum
Aussage <Mathematik>
Beobachtungsstudie
Fundamentalsatz der Algebra
Matrizenring
Determinante
Graph
Operations Research
Schlussregel
Primideal
Vektorraum
Menge
Invertierbare Matrix
Energiedichte
Übergangswahrscheinlichkeit
Quadratzahl
Kantenfärbung
53:18
Weg <Topologie>
Punkt
Mathematik
Computeranimation
54:37
Einfach zusammenhängender Raum
tTest
Mathematik
Computeranimation
55:20
Arithmetische Folge
Trennschärfe <Statistik>
Mathematik
Computeranimation
56:13
Formale Potenzreihe
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 OpenAccessLizenz: 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. 