Solvin' it old school: Israeli mathematician unravels the decades-old 'Road Coloring Problem'... an eight page, hand-written proof. Some details here.

This is a great story - Russian mathematician immigrates to Israel, works as a laborer and night watchman, and perseveres and excels in his chosen vocation.  

JERUSALEM - A mathematical puzzle that baffled the top minds in the esoteric field of symbolic dynamics for nearly four decades has been cracked — by a 63-year-old immigrant who once had to work as a security guard.

Avraham Trahtman, a mathematician who also toiled as a laborer after moving to Israel from Russia, succeeded where dozens failed, solving the elusive "Road Coloring Problem."

The conjecture essentially assumed it's possible to create a "universal map" that can direct people to arrive at a certain destination, at the same time, regardless of starting point. Experts say the proposition could have real-life applications in mapping and computer science.

Now get this:

The "Road Coloring 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.

For eight years, Weiss tried to prove his theory. Over the next 30 years, some 100 other scientists attempted as well. All failed, until Trahtman came along and, in eight short pages, jotted the solution down in pencil last year.


I'm sure Wrymouth can explain to us Poli-Sci majors the intricacies and significance of this remarkable accomplishment.

And for Wrymouth and the math geeks, here is Mr. Trahtman's 8-page paper in its entirety.

I'm completely jazzed...

  • No trackbacks exist for this post.
Page: 1 of 1
  • 21 Mar 2008, 8:47 AM Wry M wrote:
    uh, oh, TWO interesting sets of math links in less than an hour... the other set's over in the comments section of AreWeLumberjacks?...

    Good thing it's a long weekend. Happy Easter (the modern, Christian kind, as opposed to the more ancient, pagany kind) to all.

    Cog will be happy to note I have picked up a "grad student" at my high school, who is helping me unravel a conjecture about WryMouth's tetrahedral matrix... he is gleefully crunching numbers because he has some free time I do not. I have dutifully named the conjecture after both of us in fair gratitude: the Boland-Wrymouth conjecture.

    And yes, we are using pens, pencils, and reams of graph paper.

    Additionally, another variation on Pascal's triangle is producing tantalizing results that remain just beyond my symbolic grasp... I can't get the free time to work out the functional description, although I can describe the procedure perfectly in English... the "shortcut" notation eludes me, and it is the "shortcut" notation that mathematicians and statisticians crave.

    This pursuit line is the one that resulted in the "hyperfactorial" number sequences and the "Star Wars" number sequences, posted about earlier. As I tell the students, with mock naivety, I am only trying to generalize the work of Pascal and Newton -- what could be so hard about that?

    Thanks for the tease.

    PS: I am not satisfied with the modern "proof" of Fermat's last theorem, as I believe it should be able to be done with techniques and materials available to Fermat -- i.e., no computers, or modern mathematics, etc. So that's on my list of things-to-do as well.
    Reply to this
  • 25 Mar 2008, 9:00 PM Wry M wrote:
    Cogit: I have downloaded the pdf... my idea of "bathtub" reading... thoughts will be posted in a little while, if post-worthy. Thanks again!
    Reply to this
    1. 26 Mar 2008, 7:21 PM WryMouth wrote:
      Ok; I'm back...

      FYI, the opening sentence of the abstract of the proof reads like Steve martin's old punch-line: "baby-no-face-banana-dog-boy."

      But, I was able to sift a few glimpses of reasoning through the dual smudged filters of thorough-going graph-theory slang and broken Russian-Israeli English.*
      You will be happy to know, Cogito, that the main engine of the proof rests on the ol' Proof By Contradiction maneuver you remember from your Hi Skule geometry and/or Debate Club days.

      Assume the contrary position is true, follow the logic trail to an absurdity, and then drop the "ergo, the theorem must be true."
      That's the bit, I am sure, he is speaking of when he says "hard, but not complicated."
      As a bonus, my fevered brain was able to solve a mapping problem I and my research student encountered in the Boland-Wrymouth conjecture -- how do you create a 2-d coordinate "street map" for a city, if there are three cardinal directions, instead of four?

      I have dubbed the three cardinal directions, varyingly, as Red/Blue/Green, Moe/Larry/Curly, or Groucho/Chico/Harpo.

      Hey; it's my map.

      Pictures to follow in a later post, we hope. We tried the map today, on levels n=4 and n=5, and it works a treat. I envision that it may even be extendable to maps of any number of directions.


      * Don't the editors of math papers even care about salesmanship? Why don't they at least clean up the dropped definite articles and stilted phrases?

      Reply to this

Page: 1 of 1
Leave a comment

Submitted comments are subject to moderation before being displayed.


 Email (will not be published)

Your comment is 0 characters limited to 3000 characters.