Road coloring theorem

In graph theory the road coloring theorem, known until recently as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network (which might be a representation of city streets or a maze).[1] In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics.

The theorem was first conjectured by Roy Adler and Benjamin Weiss (1970). It was proved by Avraham Trahtman (2009).

Example and intuition

A directed graph with a synchronizing coloring

The image to the right shows a directed graph on eight vertices in which each vertex has out-degree 2. (Each vertex in this case also has in-degree 2, but that is not necessary for a synchronizing coloring to exist.) The edges of this graph have been colored red and blue to create a synchronizing coloring.

For example, consider the vertex marked in yellow. No matter where in the graph you start, if you traverse all nine edges in the walk "blue-red-red—blue-red-red—blue-red-red", you will end up at the yellow vertex. Similarly, if you traverse all nine edges in the walk "blue-blue-red—blue-blue-red—blue-blue-red", you will always end up at the vertex marked in green, no matter where you started.

The road coloring theorem states that for a certain category of directed graphs, it is always possible to create such a coloring.

Mathematical description

Let G be a finite, strongly connected, directed graph where all the vertices have the same out-degree k. Let A be the alphabet containing the letters 1, ..., k. A synchronizing coloring (also known as a collapsible coloring) in G is a labeling of the edges in G with letters from A such that (1) each vertex has exactly one outgoing edge with a given label and (2) for every vertex v in the graph, there exists a word w over A such that all paths in G corresponding to w terminate at v.

The terminology synchronizing coloring is due to the relation between this notion and that of a synchronizing word in finite automata theory.

For such a coloring to exist at all, it is necessary that G be aperiodic.[2] The road coloring theorem states that aperiodicity is also sufficient for such a coloring to exist. Therefore, the road coloring problem can be stated briefly as:

Every finite strongly connected aperiodic directed graph of uniform out-degree has a synchronizing coloring.

Previous partial results

Previous partial or special-case results include the following:

See also

Notes

  1. ↑ Seigel-Itzkovich, Judy (2008-02-08). "Russian immigrant solves math puzzle". The Jerusalem Post. Retrieved 2010-09-13.
  2. ↑ Hegde & Jain (2005).

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.