Add to Watchlist
The Lonely Runner Conjecture
96 views
Citation of segmentFormal Metadata
Title  The Lonely Runner Conjecture 
Title of Series  Kolloquium der Fakultät für Mathematik und Informatik der FernUniversität in Hagen 
Author 
Goddyn, Luis

License 
No Open Access License: German copyright law applies. This film may be used for your own use but it may not be distributed via the internet or passed on to external parties. 
DOI  10.5446/18565 
Publisher  FernUniversität in Hagen 
Release Date  2012 
Language  English 
Producer 
FernUniversität in Hagen

Content Metadata
Subject Area  Mathematics 
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. 
Series
Annotations
Transcript
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 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
Covering space
Mathematics
Field extension
Mathematics
Computer animation
Cycle (graph theory)
Likelihoodratio test
Mathematical optimization
Local Group
00:54
Summation
Mathematics
Computer animation
Mass flow rate
Content (media)
Sinc function
01:39
Summation
Mathematics
Mathematics
Computer animation
Local Group
02:31
Mathematics
Trail
Computer animation
Multiplication sign
Circle
03:17
Mathematics
Trail
Computer animation
Multiplication sign
Circle
Right angle
04:00
Point (geometry)
Area
Summation
Mathematics
Computer animation
Convex hull
Circle
04:55
Mathematics
Summation
Computer animation
Multiplication sign
Units of measurement
Maxima and minima
05:47
Mathematics
Computer animation
Multiplication sign
Maxima and minima
06:34
Mathematics
Trail
Rational number
Computer animation
07:18
Fraction (mathematics)
Mathematics
Linear independence
Computer animation
Greatest common divisor
Parameter (computer programming)
Integer
Position operator
Power (physics)
08:06
Mathematics
Computer animation
Velocity
Greatest common divisor
Integer
Symmetric matrix
09:00
Chemical equation
Multiplication sign
Physical law
Distance
Distance
Mathematics
Maxima and minima
Moment of inertia
Computer animation
Vector space
Integer
Right angle
Absolute value
Supremum
09:42
Greatest element
Mass flow rate
Divisor
Chemical equation
Multiplication sign
Cartesian coordinate system
Distance
Distance
Variance
Number
Maxima and minima
Mathematics
Maxima and minima
Computer animation
Supremum
11:49
Mathematics
Computer animation
Divisor
Multiplication sign
Infinity
Convex hull
8 (number)
12:33
Mathematics
Proof theory
Computer animation
Multiplication sign
Maxima and minima
13:24
Computer animation
Set (mathematics)
Mereology
Number
14:22
Rational number
Divisor
Set (mathematics)
Real number
Set (mathematics)
Cartesian coordinate system
Distance
Law of large numbers
Approximation
Event horizon
Approximation
Mathematics
Computer animation
Vector space
Term (mathematics)
Bounded variation
Diophantische Gleichung
15:17
Graph (mathematics)
Mass flow rate
Graph (mathematics)
Theory
Set (mathematics)
Distance
Graph (mathematics)
Approximation
Distance
Mathematics
Number
Number theory
Computer animation
Graph coloring
Manysorted logic
Vertex (graph theory)
Matroid
Integer
Graph (mathematics)
Bounded variation
Diophantische Gleichung
16:35
Number
Computer animation
Graph (mathematics)
Matroid
Theory
Graph (mathematics)
Bounded variation
Approximation
Diophantische Gleichung
Distance
Number
Maxima and minima
17:21
Mathematics
Proof theory
Random number
Computer animation
Multiplication sign
Circle
Set (mathematics)
Newton's law of universal gravitation
Proof theory
18:08
Expected value
Standard error
Proof theory
Random number
Summation
Computer animation
Multiplication sign
Length
Number
Proof theory
20:08
Mathematics
Proof theory
Computer animation
Multiplication sign
Position operator
Number
Proof theory
20:52
Multiplication sign
Trail
Multiplication sign
Direction (geometry)
Distance
Distance
Number
Maxima and minima
Mathematics
Computer animation
Subtraction
Proof theory
Newton's law of universal gravitation
22:26
Point (geometry)
Geometry
Multiplication sign
Direction (geometry)
Infinity
Parameter (computer programming)
Frequency
Proof theory
Computer animation
Square number
Circle
Square number
Units of measurement
Proof theory
26:03
Mathematics
Computer animation
Lie group
Direction (geometry)
Square number
Square number
Length
27:01
Threedimensional space
Multiplication sign
Propositional formula
Number
Maxima and minima
Mathematics
Maxima and minima
Computer animation
Cube
Hausdorff dimension
Cube
Square number
Queue (abstract data type)
Table (information)
Square number
Position operator
Length
28:36
Area
Direction (geometry)
Propositional formula
Maxima and minima
Mathematics
Computer animation
Vector space
Cube
Game theory
Bounded variation
Bounded variation
Square number
Length
29:33
Point (geometry)
Area
Trail
Multiplication sign
Propositional formula
Infinity
Distance
Maxima and minima
Mathematics
Maxima and minima
Computer animation
Cube
Normal (geometry)
Bounded variation
Subtraction
Square number
Nearring
Length
31:31
Trail
Sphere
Mathematics
Summation
Maxima and minima
Summation
Sign (mathematics)
Number theory
Roundness (object)
Computer animation
Square number
Bounded variation
Directed graph
32:40
Multiplication sign
Propositional formula
Coordinate system
Mass
Theory
Number
Maxima and minima
Mathematics
Sign (mathematics)
Computer animation
Cube
Average
Bounded variation
Square number
Length
Newton's law of universal gravitation
33:36
Computer programming
State of matter
Set (mathematics)
Multiplication sign
Equaliser (mathematics)
1 (number)
Student's ttest
Set (mathematics)
Line (geometry)
Law of large numbers
Substitute good
Number
Maxima and minima
Mathematics
Computer animation
Mathematician
Resultant
37:03
Point (geometry)
Computer animation
Set (mathematics)
1 (number)
Line (geometry)
Substitute good
Number
Newton's law of universal gravitation
38:38
Mathematics
Computer programming
4 (number)
Proof theory
Computer animation
Set (mathematics)
Set (mathematics)
Number
40:00
Mathematics
Proof theory
Number theory
Computer animation
Divisor
State of matter
Set (mathematics)
Set (mathematics)
Mereology
Subtraction
Number
42:07
Set (mathematics)
Ring (mathematics)
Ext functor
Likelihoodratio test
Open set
Number
Mathematics
Number
Computer animation
Theorem
Right angle
Units of measurement
Resultant
Condition number
42:55
Operations research
Invertierbare Matrix
Direction (geometry)
1 (number)
Food energy
6 (number)
Group representation
Matrix (mathematics)
Manysorted logic
Vector space
Square number
Determinant
Descriptive statistics
Proof theory
Spacetime
Constraint (mathematics)
Mass flow rate
Real number
Nominal number
Maxima and minima
Category of being
Proof theory
Numeral (linguistics)
Vector space
Graph coloring
Order (biology)
Theorem
Right angle
Arithmetic progression
Fundamental theorem of algebra
Point (geometry)
Standard error
Observational study
Set (mathematics)
Real number
Image resolution
Regular graph
Graph (mathematics)
Rule of inference
Theory
Number
Prime ideal
Operator (mathematics)
Linear programming
Energy level
Integer
Theorem
Stochastic kernel estimation
Absolute value
Newton's law of universal gravitation
Module (mathematics)
Graph (mathematics)
Element (mathematics)
Physical law
Total S.A.
Set (mathematics)
Incidence algebra
Mathematical model
Cartesian coordinate system
Mathematics
Computer animation
Universe (mathematics)
Vertex (graph theory)
Table (information)
Marginal distribution
Matrix (mathematics)
53:18
Point (geometry)
Mathematics
Trail
Trail
Computer animation
54:37
Mathematics
Trail
Computer animation
Dot product
Moving average
Student's ttest
Connected space
55:20
Summation
Mathematics
Trail
Computer animation
Multiplication sign
Theorem
Selectivity (electronic)
Arithmetic progression
56:13
Mathematics
Summation
Trail
Computer animation
Theorem