## Road Coloring Problem Solved 202

ArieKremen writes

*"Israeli Avraham Trakhtman, a Russian immigrant mathematician who had been employed as a night watchman, has solved the Road Coloring problem. First posed in 1970 by Benjamin Weiss and Roy Adler, the problem posits that given a finite number of roads, one should be able to draw a map, coded in various colors, that leads to a certain destination regardless of the point of origin. The 63-year-old Trakhtman jotted down the solution in pencil in 8 pages. The problem has real-world implementation in message and traffic routing."*
## Re:Night Watchman? (Score:0, Insightful)

He will stay a night watchman, because he does not have a USA degree and therefore shunned by the snooty upper educational society we have here.

It's pure bullshit how the USA punishes the educated that emigrate here that obviously are highly educated, but because they did not go to a "blessed" institution, you get to cook doughnuts instead of using that 12 year education in genetics. I know asian guys that have a background in education that makes most american educated PHD's I know look like 6th grade dropouts. but they cant get a job using their knowledge because "you were not educated in the USA".....

So they end up night watchmen, Grocery store clerks, or bank tellers. While back in their country they were educated as Doctors, Physicists, and scientists.

## Old news? (Score:5, Insightful)

2. Apparently his proof was published last September. It's "news" because it's just now hitting the semi-mainstream press. You people fail at nerddom.

## Re:Night Watchman? (Score:2, Insightful)

Also, to suggest that the quality of medical education is similar between 2nd and 3rd world countries is utterly ridiculous. Their degree is still good provided they can pass the boards and certifications. Not many do.

## Re:Yeah, yeah, First Post, but... (Score:4, Insightful)

## Sign of a true Genius. (Score:5, Insightful)

The man

isa True Genius. Insight to all of out out there, that is the proper way of thinking.## Re:Night Watchman? (Score:1, Insightful)

Fixed it for you.

## Re:Old news? (Score:2, Insightful)

## It's a theorem (Score:4, Insightful)

It's a theorem which states that if a graph is strongly connected and aperiodic, then there exists a road coloring. It was conjectured by Weiss and proven by Trahtman 30 years later, which is what the article is about. A graph that is periodic may still have a road coloring, but that's not the scope of the theorem.

Most roads are strongly connected but periodic (not aperiodic), in the sense that you can drive around a block in 4 segments, and drive around 2 blocks in 6. The period in this case is 2. You can't guarantee a computer network to be aperiodic either. These graphs may still have a road coloring, but the theorem doesn't apply. Therefore, this theorem has little application in practice.

I haven't read the paper, but there are generally two ways to prove the theorem: (1) show a coloring algorithm that makes only the assumptions of strong connectivity and aperiodicity, or (2) show the contraposition, that if there is no road coloring, then it implies either the graph is not strongly connected or there is period. Only (1) is useful in practice because you have a method to generate road coloring and instructions to reach all vertices, but it's harder to verify that (1) is correct. (2) is not very useful because although you have a proof, but you don't end up with an algorithm that generates road coloring.

In practice, algorithms get things done. Proofs are only certificates.

## Re:Night Watchman? (Score:1, Insightful)

Jewish Mathematics Professor Solves Road Coloring Problem.

-or-

Russian Immigrant Night Watchman Solves Road Coloring Problem.