A road is a road is a road
March 21, 2008 6:48 AM Subscribe
Did you know that you can create a simple set of directions to your house that works no matter where the recipient starts from? After 38 years this remarkable conjecture has now been proved by a 63-year old former security guard.
A friend of mine used to give directions to his house as "Second house down Lookout Mountain from Rock City." Anyone in North America could find it.
posted by paulsc at 6:53 AM on March 21, 2008
posted by paulsc at 6:53 AM on March 21, 2008
If Richard Feynman had a paper route at age 11, would that mean that the Nobel Prize was won by a "former paperboy"?
The man is a mathematician.
Also, this is a pretty crazy theorem. It's the same set of directions from any starting point. What the...
posted by DU at 6:55 AM on March 21, 2008 [2 favorites]
The man is a mathematician.
Also, this is a pretty crazy theorem. It's the same set of directions from any starting point. What the...
posted by DU at 6:55 AM on March 21, 2008 [2 favorites]
I don't get this at all. I just know it's awesome.
Okay, I also know that I hope any of my future accomplishments in aren't mentioned with the phrase "former line cook" or anything like that.
posted by Navelgazer at 6:58 AM on March 21, 2008
Okay, I also know that I hope any of my future accomplishments in aren't mentioned with the phrase "former line cook" or anything like that.
posted by Navelgazer at 6:58 AM on March 21, 2008
I've always hoped that any news reports about me would be preceded by the words, "millionaire playboy."
posted by Pollomacho at 7:03 AM on March 21, 2008 [1 favorite]
posted by Pollomacho at 7:03 AM on March 21, 2008 [1 favorite]
"Millionaire playboy wannabe Pollomacho was found dead in his skidrow cardboard box today. He had a plastic bag over his head and his pants down."
posted by DU at 7:07 AM on March 21, 2008 [19 favorites]
posted by DU at 7:07 AM on March 21, 2008 [19 favorites]
I built many of the buildings of this town. Eight of these homes were built by my hands, but do they call me Allen the constructor? No.
And I farmed five thousand acres of land with no aid from anybody, with cattle, sheep, and a great deal of produce, but do they call me Allen the farmer? No.
But youfuck one lousy sheep.... guard one lousy building...
posted by allen.spaulding at 7:07 AM on March 21, 2008 [8 favorites]
And I farmed five thousand acres of land with no aid from anybody, with cattle, sheep, and a great deal of produce, but do they call me Allen the farmer? No.
But you
posted by allen.spaulding at 7:07 AM on March 21, 2008 [8 favorites]
It's possible that I'm missing something obvious, but I don't really understand how applications of this would work. I know this is interesting from a graph theory perspective, but the article makes it sound like this proof will actually have real-world uses.
The point of this method is that you can navigate without knowing where you are, but you do need to know at least the color of road you're on, so it seems like in the real-world you would just label all of the roads with a unique ID instead of one of two colors. Also, I would think that the fact that all nodes need to have the same out-degree means that it won't work in real-world maps and whatnot. The article also mentioned that this could be used to find lost emails, and I have absolutely no clue how that would work using this method.
posted by burnmp3s at 7:07 AM on March 21, 2008
The point of this method is that you can navigate without knowing where you are, but you do need to know at least the color of road you're on, so it seems like in the real-world you would just label all of the roads with a unique ID instead of one of two colors. Also, I would think that the fact that all nodes need to have the same out-degree means that it won't work in real-world maps and whatnot. The article also mentioned that this could be used to find lost emails, and I have absolutely no clue how that would work using this method.
posted by burnmp3s at 7:07 AM on March 21, 2008
but the article makes it sound like this proof will actually have real-world uses.
If you actually wanted to give your friends driving directions like this, you'd need friends with full tanks of gas and a lot of time on their hands. The directions are guaranteed to get you where you're going, but they don't give you the shortest route there.
(The linked Wikipedia article gives a small demonstration — you can see that even on the fairly simple graph they give, the directions take nine moves even if you start out just one or two vertices away from your goal.)
posted by nebulawindphone at 7:16 AM on March 21, 2008
If you actually wanted to give your friends driving directions like this, you'd need friends with full tanks of gas and a lot of time on their hands. The directions are guaranteed to get you where you're going, but they don't give you the shortest route there.
(The linked Wikipedia article gives a small demonstration — you can see that even on the fairly simple graph they give, the directions take nine moves even if you start out just one or two vertices away from your goal.)
posted by nebulawindphone at 7:16 AM on March 21, 2008
Completely wild guess here, but I think the email case means that currently, emails do not always take a predictable route from source to destination, and that this result allows for emails that were correctly addressed but got stuck at some point (at a misconfigured machine, perhaps) to be found because there would be a predictable routing that one could retrace to poll each machine along the route and find out if they had the email.
posted by zippy at 7:18 AM on March 21, 2008
posted by zippy at 7:18 AM on March 21, 2008
I think the "real-world" example of maps is more an intuitive thing than a utility thing. Graph theory has many applications that are non-obvious but extremely useful.
posted by DU at 7:25 AM on March 21, 2008
posted by DU at 7:25 AM on March 21, 2008
Graph theory is pretty damn close to the single most important facet in computer science. I suspect that there's the equivalent of a swiss patent clerk or two fiddling with problems just like this as we speak.
posted by Skorgu at 7:36 AM on March 21, 2008 [1 favorite]
posted by Skorgu at 7:36 AM on March 21, 2008 [1 favorite]
I think the "real world" example is for a crappy four house village with a town square in the middle, connected by one way streets since the city planner was in a rush. The Petersons, Browns, Hardisons and Old lady Kaminski will be pleased.
posted by cashman at 7:37 AM on March 21, 2008 [2 favorites]
posted by cashman at 7:37 AM on March 21, 2008 [2 favorites]
Start walking east, when you reach the same place you starteed from, move 2 meters sideways to the right and repeat. When you reach the South pole, move 2 meters to the left (to the north? up?) and repeat. You will reach your destination.
posted by Space Coyote at 7:37 AM on March 21, 2008 [1 favorite]
posted by Space Coyote at 7:37 AM on March 21, 2008 [1 favorite]
Keep turning right (which means reversing at a dead end) until you hit New York City.
posted by StickyCarpet at 7:38 AM on March 21, 2008
posted by StickyCarpet at 7:38 AM on March 21, 2008
I hope my future work in physics is described as done by "a former Baskin Robbins ice cream scooper" since I did that in high school. (and this is cool math)
posted by Shutter at 7:46 AM on March 21, 2008
posted by Shutter at 7:46 AM on March 21, 2008
The road thing is just a way of visualizing the problem. The real world applications are likely to be much more abstract. (Although I'm DEFINITELY going to do this with my trail system in the backwoods!).
An interesting property of the directions is that, although they don't give the shortest route, every route that they describe to the destination contains the same number of hops. So in a tick-based system (one edge traversal per tick), you can guarantee that all agents following the directions who start at the same time will arrive at the destination simultaneously.
To apply it to a real roadmap, all you have to do is color SOME of the roads. A road can have more than one color going in more than one direction.
I just love the idea that you could carry a card in your pocket that had a series of colors on it, and no matter where you were, if you followed the colours in the correct order, you get to your destination. If at any point you get lost, you just start again.
When you start visualising it like that, you can see that there are obvious applications in routing. The series of colours that describes the route to a particular destination from anywhere is the equivalent of its address. A packet traversing from node to node just follows the directions until it reaches the destination. It doesn't care where it starts from, just as it doesn't matter where you post a letter from. The difference is that the packet doesn't need any more information to get there -- it gets there automagically.
The rub is that it only works for an invariant subsection of a network topology.
posted by unSane at 7:48 AM on March 21, 2008 [2 favorites]
An interesting property of the directions is that, although they don't give the shortest route, every route that they describe to the destination contains the same number of hops. So in a tick-based system (one edge traversal per tick), you can guarantee that all agents following the directions who start at the same time will arrive at the destination simultaneously.
To apply it to a real roadmap, all you have to do is color SOME of the roads. A road can have more than one color going in more than one direction.
I just love the idea that you could carry a card in your pocket that had a series of colors on it, and no matter where you were, if you followed the colours in the correct order, you get to your destination. If at any point you get lost, you just start again.
When you start visualising it like that, you can see that there are obvious applications in routing. The series of colours that describes the route to a particular destination from anywhere is the equivalent of its address. A packet traversing from node to node just follows the directions until it reaches the destination. It doesn't care where it starts from, just as it doesn't matter where you post a letter from. The difference is that the packet doesn't need any more information to get there -- it gets there automagically.
The rub is that it only works for an invariant subsection of a network topology.
posted by unSane at 7:48 AM on March 21, 2008 [2 favorites]
"63-year old former security guard" - the bit about being 63 is what has surprised his colleagues, seeing as mathematicians tend to peak by the time they hit 30.
posted by linux at 8:03 AM on March 21, 2008
posted by linux at 8:03 AM on March 21, 2008
Matt Damon and Ben Affleck finally have a topic for their big follow-up to Good Will Hunting.
posted by goatdog at 8:06 AM on March 21, 2008
posted by goatdog at 8:06 AM on March 21, 2008
The rub is that it only works for an invariant subsection of a network topology.
Exactly. I know that the "road" thing was mainly used as a metaphor, and that in reality this would be used in other systems, but I'm having a hard time coming up with any specific case where something like this would be useful.
It only works on very specific graphs, the structure of the graph has to be known when the coloring is done, the structure of the graph can't change after the coloring is done, and the coloring of the map has to be stored somehow so that it can be used to traverse the map.
I can't think of any real-life situation where you'd always have all of those conditions met and not have any better path-finding method than this available.
posted by burnmp3s at 8:14 AM on March 21, 2008
Exactly. I know that the "road" thing was mainly used as a metaphor, and that in reality this would be used in other systems, but I'm having a hard time coming up with any specific case where something like this would be useful.
It only works on very specific graphs, the structure of the graph has to be known when the coloring is done, the structure of the graph can't change after the coloring is done, and the coloring of the map has to be stored somehow so that it can be used to traverse the map.
I can't think of any real-life situation where you'd always have all of those conditions met and not have any better path-finding method than this available.
posted by burnmp3s at 8:14 AM on March 21, 2008
Pratically, it is similar to solving a maze: keep your hand on the wall, start walking without llifting your hand away until you are out.
The exciting and awesome part is proving it mathematically. I read about it in today's paper, but it lacked details. Thanks for the links!
posted by francesca too at 8:22 AM on March 21, 2008
The exciting and awesome part is proving it mathematically. I read about it in today's paper, but it lacked details. Thanks for the links!
posted by francesca too at 8:22 AM on March 21, 2008
Did you know that you can create a simple set of directions to your house that works no matter where the recipient starts from?
No, I didn't. Actually, I still don't, because I can't seem to do that.
Former taxi driver.
posted by Kirth Gerson at 8:24 AM on March 21, 2008
No, I didn't. Actually, I still don't, because I can't seem to do that.
Former taxi driver.
posted by Kirth Gerson at 8:24 AM on March 21, 2008
I don't care how future newspaper articles describe me, as long a my name appears nowhere near the phrase "covered in his own filth".
posted by blue_beetle at 8:29 AM on March 21, 2008
posted by blue_beetle at 8:29 AM on March 21, 2008
The specific application he talks about in the paper is finite-state automaton theory.
Imagine that you have an automaton with states represented by the vertices on the graph and inputs represented by the edges.
So if you're in state S and you receive input I, you traverse along the edge labelled I to state S' and so on. The result proves that there is always a single input 'word' which will reset all automata to a known state, no matter what state it's in already. It's known as the 'synchronizing word' because by issuing it to all the automata in a system, it resets them all to a known state.
It's like having a bunch of kids all lost in London, but with a walkie talkie. You can broadcast the same 'word' to all of them, and if they follow it, they all end up in Leicester Square at exactly the same time. Spooky.
posted by unSane at 8:29 AM on March 21, 2008 [1 favorite]
Imagine that you have an automaton with states represented by the vertices on the graph and inputs represented by the edges.
So if you're in state S and you receive input I, you traverse along the edge labelled I to state S' and so on. The result proves that there is always a single input 'word' which will reset all automata to a known state, no matter what state it's in already. It's known as the 'synchronizing word' because by issuing it to all the automata in a system, it resets them all to a known state.
It's like having a bunch of kids all lost in London, but with a walkie talkie. You can broadcast the same 'word' to all of them, and if they follow it, they all end up in Leicester Square at exactly the same time. Spooky.
posted by unSane at 8:29 AM on March 21, 2008 [1 favorite]
No matter where in the graph you start, if you trace out the path "blue-red-red, blue-red-red, blue-red-red", you will end up at the yellow vertex.
This just isn't true. Unless you they mean that you can't go over lines that you've already crossed, I can consistently go b-r-r, b-r-r, b-r-r and not end up anywhere near the yellow vertex.
Either I'm really, really bad at math, or some kind of super-genius navigator, where my only skill is to get lost.
posted by quin at 8:36 AM on March 21, 2008 [1 favorite]
This just isn't true. Unless you they mean that you can't go over lines that you've already crossed, I can consistently go b-r-r, b-r-r, b-r-r and not end up anywhere near the yellow vertex.
Either I'm really, really bad at math, or some kind of super-genius navigator, where my only skill is to get lost.
posted by quin at 8:36 AM on March 21, 2008 [1 favorite]
You're following the lines in the direction of the arrows, right?
posted by unSane at 8:40 AM on March 21, 2008
posted by unSane at 8:40 AM on March 21, 2008
quin -- did you notice that the lines/"roads" are one-way?
posted by Perplexity at 8:43 AM on March 21, 2008
posted by Perplexity at 8:43 AM on March 21, 2008
I see that since the original solution he's come up with an algorithm for coloring the graph. Time is order of N^3 in the worst case and quadratic in most cases.
posted by unSane at 8:46 AM on March 21, 2008
posted by unSane at 8:46 AM on March 21, 2008
Ah see, 'bad navigator' would be the answer here. No I wasn't noticing that the roads were one-way.
Seriously, don't let me out on the streets today. If I missed something that obvious, something is clearly wrong with my brain.
posted by quin at 8:46 AM on March 21, 2008
Seriously, don't let me out on the streets today. If I missed something that obvious, something is clearly wrong with my brain.
posted by quin at 8:46 AM on March 21, 2008
My indoor slides into the wall, my outdoor locks on whim, forcing me out the back door. I'm sure quantum mechanics covers this variation.
posted by Mblue at 8:50 AM on March 21, 2008
posted by Mblue at 8:50 AM on March 21, 2008
Keep turning right (which means reversing at a dead end) until you hit New York City.
Are you sure this works? I've driven around the block 16 times so far, and don't seem to be getting any closer to NYC.
posted by sfenders at 8:56 AM on March 21, 2008
Are you sure this works? I've driven around the block 16 times so far, and don't seem to be getting any closer to NYC.
posted by sfenders at 8:56 AM on March 21, 2008
neat! I can't get lost!
posted by cowbellemoo at 9:06 AM on March 21, 2008
posted by cowbellemoo at 9:06 AM on March 21, 2008
It's like having a bunch of kids all lost in London, but with a walkie talkie. You can broadcast the same 'word' to all of them, and if they follow it, they all end up in Leicester Square at exactly the same time. Spooky.
Mornington Crescent!
posted by nonmyopicdave at 9:20 AM on March 21, 2008
Mornington Crescent!
posted by nonmyopicdave at 9:20 AM on March 21, 2008
I think he means "Keep turning right, unless you've already been down that road, until you hit NYC..."
There are lots and lots of graph traversal algorithms which will take you to all nodes of a graph. See also maze solutions.
However we are talking about something quite different.
posted by unSane at 9:27 AM on March 21, 2008
There are lots and lots of graph traversal algorithms which will take you to all nodes of a graph. See also maze solutions.
However we are talking about something quite different.
posted by unSane at 9:27 AM on March 21, 2008
Christ, I've sent people custom google maps outlining where my home is, directions, and where to park, and people STILL get lost trying to get here. I do not hold out hope that this impressive-yet-difficult algorithm is going to fix this before my birthday party.
posted by Uther Bentrazor at 10:06 AM on March 21, 2008
posted by Uther Bentrazor at 10:06 AM on March 21, 2008
the bit about being 63 is what has surprised his colleagues, seeing as mathematicians tend to peak by the time they hit 30.
posted by linux
linux, that misconception is based on G. H. Hardy's A MAthematician's Apology in which he said "I do not know an instance of a major mathematical advance initiated by a man past fifty". He also said that he had never known a former mathematician that could make it in any other field. It is very easy to finder counterexamples.
For important work at the age of 63 I can think of:
Lenart Carleson recently got an Abel's prize at the age of 78, partly for work he did at 63 on the Hénon map.
There is still some truth to the matter, mathematicians tend to make their best contributions before hitting 40.
posted by Dr. Curare at 10:28 AM on March 21, 2008
posted by linux
linux, that misconception is based on G. H. Hardy's A MAthematician's Apology in which he said "I do not know an instance of a major mathematical advance initiated by a man past fifty". He also said that he had never known a former mathematician that could make it in any other field. It is very easy to finder counterexamples.
For important work at the age of 63 I can think of:
Lenart Carleson recently got an Abel's prize at the age of 78, partly for work he did at 63 on the Hénon map.
There is still some truth to the matter, mathematicians tend to make their best contributions before hitting 40.
posted by Dr. Curare at 10:28 AM on March 21, 2008
I don't care how future newspaper articles describe me, as long a my name appears nowhere near the phrase "covered in his own filth".
In other news, most of the body of mefite blue_beetle was found today covered in filth in a 1972 AMC Pacer behind a Taco Bell in Corpus Christi, Texas, along with some legal paperwork. The documents found with his body, and the filth, transferred ownership of the filth to mathowie, so blue_beetle was technically covered in mathowie's filth, though it should be noted that forensics confirmed that all of the several liters of filth covering blue_beetle seems to have emanated from his various orifices.
posted by ROU_Xenophobe at 10:50 AM on March 21, 2008 [2 favorites]
In other news, most of the body of mefite blue_beetle was found today covered in filth in a 1972 AMC Pacer behind a Taco Bell in Corpus Christi, Texas, along with some legal paperwork. The documents found with his body, and the filth, transferred ownership of the filth to mathowie, so blue_beetle was technically covered in mathowie's filth, though it should be noted that forensics confirmed that all of the several liters of filth covering blue_beetle seems to have emanated from his various orifices.
posted by ROU_Xenophobe at 10:50 AM on March 21, 2008 [2 favorites]
A couple of comments here say that not only do the "set of directions" work no matter what vertex you start from, but they also get you to the destination in the same amount of time. Except I'm staring at the very simple Wikipedia example and this is clearly false—to get to the green vertex, for example, sometimes you have to use two or three cycles of "blue-blue-red" while other times you require only one. Even taking into account the lengths of the connections (which I assume don't actually matter and are simply an artifact of the specific visual representation of the problem), it seems pretty obvious that the amount of time it takes to reach the green vertex changes depending on your starting vertex. Is there a specific subset of graphs where the "same amount of time" property holds true as well?
posted by chrominance at 10:54 AM on March 21, 2008
posted by chrominance at 10:54 AM on March 21, 2008
They get you to the destination in the same amount of time in the sense that, if the instructions are T characters long, after T ticks of time, everyone is at the destination. This is important in the finite-state automaton example because it means that if you are issuing instructions and make a mistake, you can issue the 'synchronize word' and know that T ticks later, all of your automata are in the same (accepting) state. In this case it doesn't matter if some of the automata have already cycled through that state a few times.
In other words, the instructions do get you to the destination in the same amount of time, but you may go *through* the destination several times on the way there. It's not necessarily the first time you've been there. (It's like getting to a meeting early and driving around the block until everyone else arrives).
posted by unSane at 11:07 AM on March 21, 2008 [1 favorite]
In other words, the instructions do get you to the destination in the same amount of time, but you may go *through* the destination several times on the way there. It's not necessarily the first time you've been there. (It's like getting to a meeting early and driving around the block until everyone else arrives).
posted by unSane at 11:07 AM on March 21, 2008 [1 favorite]
I can not wait for the this google-maps mashup.
posted by TimeTravelSpeed at 11:38 AM on March 21, 2008
posted by TimeTravelSpeed at 11:38 AM on March 21, 2008
It seems like FedEx and UPS could make something out of this, considering they're basically in the business of routing packets through a network. There'd probably be all kinds of special conditions and short-circuits, but it would be useful for determining maximum transit times and applying reset conditions when things get FUBAR.
Airlines too, come to think of it. Remember last year when there was a big storm and 80% of all airline planes got stuck in NYC? Bet they wish they had a big logistical "RESET" button then too.
posted by rusty at 12:23 PM on March 21, 2008
Airlines too, come to think of it. Remember last year when there was a big storm and 80% of all airline planes got stuck in NYC? Bet they wish they had a big logistical "RESET" button then too.
posted by rusty at 12:23 PM on March 21, 2008
“Smed, I’m at the gas station, where’s your house, man?”
“Look, just imagine you’re in a state represented by vertices on a graph...”
“Ok, so, left at the light or what?”
“No, no, each input is represented by the edges, so - are you in state ‘S’?”
“Uh, what?”
“You’ve got to go blue-red-red, man.”
“So...right at the light then?”
posted by Smedleyman at 1:11 PM on March 21, 2008 [4 favorites]
“Look, just imagine you’re in a state represented by vertices on a graph...”
“Ok, so, left at the light or what?”
“No, no, each input is represented by the edges, so - are you in state ‘S’?”
“Uh, what?”
“You’ve got to go blue-red-red, man.”
“So...right at the light then?”
posted by Smedleyman at 1:11 PM on March 21, 2008 [4 favorites]
Go South until you reach the South Pole, then...
posted by Rafaelloello at 1:50 PM on March 21, 2008
posted by Rafaelloello at 1:50 PM on March 21, 2008
Even though this should guarantee otherwise, twenty years from now, I fully expect the path finding algorithms of AI characters in video games to still be screwed up.
posted by BrotherCaine at 4:40 PM on March 21, 2008
posted by BrotherCaine at 4:40 PM on March 21, 2008
« Older Stranger Photos Have Happened | No Intelligence Admitted Without Proper... Newer »
This thread has been archived and is closed to new comments
posted by XMLicious at 6:53 AM on March 21, 2008 [6 favorites]