A Proof of the Road Coloring Conjecture by Daniel Dadush

I will present a proof to a recently solved open problem known as the Road Coloring Conjecture 
(Adler, Goodwyn, Weiss 1971) due to A.N. Trakhtman. The formulation of this problem is as follows:

Given a directed graph G of constant out-degree k, can I color the edges of G such that:
- All the outgoing edges of a vertex are colored using distinct colors in the set {1,...,k}
- For every vertex w, there exists a sequence of colors (c_1,c_2,...,c_m) such that every
	path P in G of length m whose edges follow the color pattern (c_1,c_2,...,c_m) ends in w.

The Road Coloring Conjecture posits that such a coloring can be found if G is strongly connected and aperiodic.
Intuitively, if we think of the colors as "directions" (north,south,east,west,....), the problem is asking whether
for any vertex w in G can one give a set of directions leading to w that does not depend on the starting position.