Talk:Road coloring problem
From Wikipedia, the free encyclopedia
 |
|||||
| Mathematics rating: | Stub Class | Low Priority | Field: Discrete mathematics | ||
| Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article. | |||||
According to http://www-igm.univ-mlv.fr/~perrin/Recherche/Seminaires/FSATIE/Fsatie.pdf the conjecture was proven by Trahtman in 2007. —Preceding unsigned comment added by 194.100.215.1 (talk) 12:36, 27 January 2008 (UTC)
[edit] Introduction needed
I recognize that a theorem in graph theory necessarily requires some amount of technical terminology to express succinctly, but couldn't somebody rewrite the introduction to tone down the incomprehensibility just a little bit? I don't think that you need to explain all of graph theory from first principles here, but the current phrasing is just a little too abstract a level for something that ought to be a relatively conprehensible problem. Geoffrey.landis (talk) 01:47, 21 March 2008 (UTC)
[edit] Graph Incorrect?
Starting at the bottom most vertex, following the path blue-blue-red blue-blue-red, doesn't get you to the green dot. If you leave out the last "red" it does, but otherwise not. So either the graph is wrong or the description of how to use it is wrong. --66.224.246.146 (talk) 14:50, 21 March 2008 (UTC)
- I believe the graph illustrates a partial proof; also keep in mind that the graph is directed; you can't go against the flow. — • Kurt Guirnela • ‡ Feedback 14:53, 21 March 2008 (UTC)
- If you follow the "blue-blue-red" a third time (instead of the two that you did), it brings you to the green dot -- Shaun the Steadfast (talk) 15:37, 21 March 2008 (UTC)
If you follow "blue-blue-blue", or "red-red-red" for that matter, the solution is not a unique node. It appears that in general the word causes the graph traversal to traverse into a terminal loop for the word. But if the word and the terminal segment can synchronize in more than one way (BBB has three ways with BBB) then the solution is not a unique node. Is something missing in the problem definition or is the example defective in some way? [user: encycloconstructs] 17:32, 21 March 2008 (UTC)
- Avraham responded via private email: not any word must be synchronizing. Essential is that there EXISTS a synchronizing word. At least one. 27 March 2008 —Preceding unsigned comment added by Encycloconstructs (talk • contribs) 05:25, 27 March 2008 (UTC)
[edit] Solution
A positive solution for this has now been put forward; http://arxiv.org/abs/0709.0099. I don't know enough about the mathematics side to put this into the article, but bring this up for someone more qualified to bring in. Aawood (talk) 15:19, 21 March 2008 (UTC)
- Yes, that information has already been introduced into the article since then. There is a reference to Avraham Trahtman in the Mathematical Description section of the article. Such a landmark event has not been overlooked. — • Kurt Guirnela • ‡ Feedback 17:16, 21 March 2008 (UTC)
- A matter of unfortunate timing; I looked at the article and the information wasn't there, got the information together and came to the talk page to add it, and at the same time someone was editing the main page to add the information. In the end, there were only 7 minutes in it. It appears this was "overlooked" since late 2007, so I'm sure you'll grant me those minutes. Aawood (talk) 20:28, 21 March 2008 (UTC)
- Lol! no problem, mate. =) Happy editing! — • Kurt Guirnela • ‡ Feedback 04:05, 22 March 2008 (UTC)
- A matter of unfortunate timing; I looked at the article and the information wasn't there, got the information together and came to the talk page to add it, and at the same time someone was editing the main page to add the information. In the end, there were only 7 minutes in it. It appears this was "overlooked" since late 2007, so I'm sure you'll grant me those minutes. Aawood (talk) 20:28, 21 March 2008 (UTC)
