Talk:Road coloring problem

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)

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)

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)

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)

What the theorem states, and what it does not state.

As seen from the section #Graph Incorrect? supra, it is possible to misread the article as claiming that every word would be synchronising; but this is not true, even when we only consider words of lengths longer than some large number. Another possible mistake would be, that for any edge colouring of an out-regular strongly connected aperiodic digraph, such that indeed each colour occurs exactly once in the set of outgoing edges from any vertex, there would be a syncronising word. This also is not true. The theorem just states that such a digraph has at least one edge colouring with at least one synchronising word.

I think that the article would be improved, if some simple counterexamples to the too general interpretation are added.

On the other hand, given a synchronising colouring, in fact any vertex is the unique end-point for one (actually, for infinitely many) syncronising words, for the simple reason that for any pairs of vertices, there is a path from the former vertex to the latter, and a corresponding word. In the example graph, e.g., the instruction "red-blue" 'leads' from the yellow to the green vertex. Thus, the eleven tokens instruction

red - red - blue - red - red - blue - red - red - blue - red - blue

necessarily is a syncronising word, with all paths so labelled ending at the green vertex, as a consequence of the first nine ones leading to the yellow one. This argument yields a dichotomy, which might be mentioned in the article: For any edge colouring (of such a graph), either there is no associated synchronising word at all, or there is one such word for each vertex in the graph. JoergenB (talk) 19:39, 14 June 2011 (UTC)

Erroneous statement

The statement: "For such a coloring to exist at all, it is necessary that G be both strongly connected and aperiodic." was incorrect. Consider a strongly connected, aperiodic graph and add a node with the correct out-degree and in-degree zero. The graph is no longer strongly connected but admits a synchronizing coloring. (Choose any coloring for the k new edges and add one letter to the beginning of the original synchronizing word.)

The assumption of strongly connectedness was moved to the beginning of the "Mathematical description" paragraph.

Andersskj (talk) 12:06, 28 May 2012 (UTC)