Results 1 to 9 of 9

Math Help - Road Colouring Problem - Solved

  1. #1
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6

    Road Colouring Problem - Solved

    Ex-guard unlocks maths riddle


    Jerusalem - A mathematical mystery that has baffled the top minds in the esoteric field of symbolic dynamics for nearly four decades has recently been cracked - by a 63-year-old former security guard.

    Avraham Trakhtman, a mathematician who worked as a labourer after immigrating to Israel from Russia, has succeeded where dozens have failed, solving the elusive Road Colouring Problem.

    The conjecture essentially assumes that it is possible to create a "universal map" that would direct people to arrive at a certain destination, at the same time, regardless of their original location. Experts say this proposition, which seems to defy logic, could actually have real-life applications in the fields of mapping and computer science.

    "In math circles, we talk about beautiful results - this is beautiful and it is unexpected. Even in layman's terms it is completely counterintuitive, but somehow it works," said Stuart Margolis, a colleague who recruited Trakhtman to Bar Ilan University near Tel Aviv.

    He said the discovery was especially remarkable given Trakhtman's age and background. "The first time I met him he was wearing a night watchman's uniform," he said.

    The Road Colouring Problem was first posed in 1970 by Benjamin Weiss, an Israeli-American mathematician, and a colleague, Roy Adler, who worked at IBM at the time.

    The long road

    Weiss said he believed that given a finite number of roads, one should be able to draw up a map, coded in various colours, that would lead to a certain destination regardless of the point of origin.

    For eight years, he tried to prove his theory. Over the next 30 years, some 100 other scientists attempted to as well.

    All failed, until Trakhtman came along and, in eight short pages, jotted the solution down in pencil last year.

    Trakhtman said it took him a year to solve the problem. But that wasn't nearly as impressive as the journey he took to get to his current lofty position.

    Originally from Yekaterinburg, Russia, Trakhtman was already an accomplished mathematician before he came to Israel in 1992, at the age of 48. But like many immigrants in the wave that followed the break-up of the former Soviet Union, he too struggled to find work in the Jewish state and was forced into stints working maintenance and security before landing a teaching position at Bar Ilan in 1995.

    'A matter for mathematicians'

    The soft-spoken Trakhtman declined to discuss his arduous odyssey, saying those were the "old days". He said he was "lucky" to be recognised, but played down his recent achievement as a "matter for mathematicians" and said it hasn't changed him a bit.

    "The solution is not that complicated. It's hard, but it is not that complicated," he said in heavily accented Hebrew. "Some people think they need to be complicated. I think they need to be nice and simple."

    Trakhtman's solution is available for viewing on the internet and will soon be published in the Israel Journal of Mathematics.

    Weiss said it gave him great joy to see someone solve his problem, adding that Trakhtman's solution "is something that is understandable."

    Joel Friedman, a math professor at the University of British Columbia, said probably everyone in the field of symbolic dynamics has tried to solve the Roadmap Colouring Problem at some point, including himself. He said people in the related disciplines of graph theory, discrete math and theoretical computer science have also tried.

    "The solution to this problem has definitely generated excitement in the mathematical community," he said in an e-mail message.

    300-year-old problem

    Trakhtman's achievement is hardly the longest open problem to be solved recently. In 1994, British mathematician Andrew Wiles solved Fermat's last theorem, which had been open for more than 300 years.

    Margolis, Trakhtman's colleague at Bar Ilan, said the solution could have many applications.

    "Say you've lost an e-mail and you want to get it back - it would be guaranteed," he said. "Let's say you are lost in a town you have never been in before and you have to get to a friend's house and there are no street signs - the directions will work no matter what."

    But even more exciting, he said, was Trakhtman's personal history and advanced age, at least in the math world.

    "The heartwarming part of it is here is a guy who had a good reputation for his work in the Soviet Union and couldn't get work," he said.

    "Math is usually a younger person's game, like music and the arts," he said. "Usually you do your better work in your mid 20's and early 30's. He certainly came up with a good one at age 63," he said.

    ============================


    Reference: News24.co.za Article
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by janvdl View Post
    Ex-guard unlocks maths riddle


    Jerusalem - A mathematical mystery that has baffled the top minds in the esoteric field of symbolic dynamics for nearly four decades has recently been cracked - by a 63-year-old former security guard.

    Avraham Trakhtman, a mathematician who worked as a labourer after immigrating to Israel from Russia, has succeeded where dozens have failed, solving the elusive Road Colouring Problem.

    The conjecture essentially assumes that it is possible to create a "universal map" that would direct people to arrive at a certain destination, at the same time, regardless of their original location. Experts say this proposition, which seems to defy logic, could actually have real-life applications in the fields of mapping and computer science.

    "In math circles, we talk about beautiful results - this is beautiful and it is unexpected. Even in layman's terms it is completely counterintuitive, but somehow it works," said Stuart Margolis, a colleague who recruited Trakhtman to Bar Ilan University near Tel Aviv.

    He said the discovery was especially remarkable given Trakhtman's age and background. "The first time I met him he was wearing a night watchman's uniform," he said.

    The Road Colouring Problem was first posed in 1970 by Benjamin Weiss, an Israeli-American mathematician, and a colleague, Roy Adler, who worked at IBM at the time.

    The long road

    Weiss said he believed that given a finite number of roads, one should be able to draw up a map, coded in various colours, that would lead to a certain destination regardless of the point of origin.

    For eight years, he tried to prove his theory. Over the next 30 years, some 100 other scientists attempted to as well.

    All failed, until Trakhtman came along and, in eight short pages, jotted the solution down in pencil last year.

    Trakhtman said it took him a year to solve the problem. But that wasn't nearly as impressive as the journey he took to get to his current lofty position.

    Originally from Yekaterinburg, Russia, Trakhtman was already an accomplished mathematician before he came to Israel in 1992, at the age of 48. But like many immigrants in the wave that followed the break-up of the former Soviet Union, he too struggled to find work in the Jewish state and was forced into stints working maintenance and security before landing a teaching position at Bar Ilan in 1995.

    'A matter for mathematicians'

    The soft-spoken Trakhtman declined to discuss his arduous odyssey, saying those were the "old days". He said he was "lucky" to be recognised, but played down his recent achievement as a "matter for mathematicians" and said it hasn't changed him a bit.

    "The solution is not that complicated. It's hard, but it is not that complicated," he said in heavily accented Hebrew. "Some people think they need to be complicated. I think they need to be nice and simple."

    Trakhtman's solution is available for viewing on the internet and will soon be published in the Israel Journal of Mathematics.

    Weiss said it gave him great joy to see someone solve his problem, adding that Trakhtman's solution "is something that is understandable."

    Joel Friedman, a math professor at the University of British Columbia, said probably everyone in the field of symbolic dynamics has tried to solve the Roadmap Colouring Problem at some point, including himself. He said people in the related disciplines of graph theory, discrete math and theoretical computer science have also tried.

    "The solution to this problem has definitely generated excitement in the mathematical community," he said in an e-mail message.

    300-year-old problem

    Trakhtman's achievement is hardly the longest open problem to be solved recently. In 1994, British mathematician Andrew Wiles solved Fermat's last theorem, which had been open for more than 300 years.

    Margolis, Trakhtman's colleague at Bar Ilan, said the solution could have many applications.

    "Say you've lost an e-mail and you want to get it back - it would be guaranteed," he said. "Let's say you are lost in a town you have never been in before and you have to get to a friend's house and there are no street signs - the directions will work no matter what."

    But even more exciting, he said, was Trakhtman's personal history and advanced age, at least in the math world.

    "The heartwarming part of it is here is a guy who had a good reputation for his work in the Soviet Union and couldn't get work," he said.

    "Math is usually a younger person's game, like music and the arts," he said. "Usually you do your better work in your mid 20's and early 30's. He certainly came up with a good one at age 63," he said.

    ============================


    Reference: News24.co.za Article
    Good for him, I must say it all ways p**s me off when people talk about mathematicians being passed it at 35 or 30 or watever.

    I remember being told at a job interview for a space debris tracking job that at 35 I was too old for creative work in a mathematical field(not that that job was, but what did the interveiwer know). (this was over 20 years ago now)

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by CaptainBlack View Post
    Good for him, I must say it all ways p**s me off when people talk about mathematicians being passed it at 35 or 30 or watever.

    I remember being told at a job interview for a space debris tracking job that at 35 I was too old for creative work in a mathematical field(not that that job was, but what did the interveiwer know). (this was over 20 years ago now)

    RonL
    I thought older mathematicians would be in greater demand because of their experience.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by CaptainBlank View Post
    Good for him, I must say it all ways p**s me off when people talk about mathematicians being passed it at 35 or 30 or watever.

    I remember being told at a job interview for a space debris tracking job that at 35 I was too old for creative work in a mathematical field(not that that job was, but what did the interveiwer know). (this was over 20 years ago now)

    RonL
    Quote Originally Posted by janvdl View Post
    I thought older mathematicians would be in greater demand because of their experience.
    Sometimes yes sometimes it is not. In physics, almost all physics is a young men game. Mathematics is not necessarily always like that. There have been many who achieved a lot till the day they died. For example, Leonard Euler did his biggest contribution, when he was blind, last years of his life, solved 3 body problem, and stated quadradic reciprocity conjecture in 1783 (the year he died).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    ...For example, Leonard Euler did his biggest contribution, when he was blind, last years of his life, solved 3 body problem,...
    In what sense? I thought there was no exact solution to that??

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    Quote Originally Posted by Aryth View Post
    Ahhh! I was thinking of the situation where none of the bodies has a fixed center. Thank you.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member Singular's Avatar
    Joined
    Dec 2006
    From
    Solo, Java
    Posts
    57
    Quote Originally Posted by janvdl View Post
    Ex-guard unlocks maths riddle


    Jerusalem - A mathematical mystery that has baffled the top minds in the esoteric field of symbolic dynamics for nearly four decades has recently been cracked - by a 63-year-old former security guard.

    Avraham Trakhtman, a mathematician who worked as a labourer after immigrating to Israel from Russia, has succeeded where dozens have failed, solving the elusive Road Colouring Problem.

    The conjecture essentially assumes that it is possible to create a "universal map" that would direct people to arrive at a certain destination, at the same time, regardless of their original location. Experts say this proposition, which seems to defy logic,
    Anyone know on the web where I can find His Solution's ?

    Thank you
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by Singular View Post
    Anyone know on the web where I can find His Solution's ?

    Thank you

    I don't quite understand the mathematics, but...

    Is this it? (It says "solution", but it's Greek to me! )
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Edge colouring in K_n
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 28th 2010, 11:52 PM
  2. [SOLVED] graph vertex colouring
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 2nd 2010, 10:46 AM
  3. Graph theory - colouring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 17th 2010, 08:26 PM
  4. Word problem about a road closing time..
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: April 16th 2009, 02:35 PM
  5. Colouring-In
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: October 20th 2008, 05:29 AM

Search Tags


/mathhelpforum @mathhelpforum