2201.12942
The road problem and homomorphisms of directed graphs
Sophie MacDonald
correcthigh confidence
- Category
- Not specified
- Journal tier
- Strong Field
- Processed
- Sep 28, 2025, 12:56 AM
- arXiv Links
- Abstract ↗PDF ↗
Audit review
The paper proves Theorem 4.3 (that OM(G),q ≤S G when M(G) is a cycle of bunches) via Trahtman’s lemma, minimal images, and an induction that produces a nontrivial stability relation and a bunchy synchronizing factor, which must be OM(G),q . The candidate solution gives a direct construction of a right-resolving, synchronizing homomorphism Φ: G → OM(G),q by refining ΣG with a q-phase index defined by the wrap number mod q, and proves synchronization using the primitivity of the d-step derived graph on each fiber (a Perron–Frobenius periodic decomposition argument). Both arguments establish the same result; the paper’s proof is combinatorial/inductive, and the model’s proof is constructive/linear-algebraic.
Referee report (LaTeX)
\textbf{Recommendation:} minor revisions
\textbf{Journal Tier:} strong field
\textbf{Justification:}
The paper gives a clear generalization of the road coloring theorem to the case where M(G) is a cycle of bunches and establishes Theorem 4.3. The structure theory around right-resolvers, stability, bunchiness, and the O(G) conjecture is carefully developed. The proof of Theorem 4.3 follows Trahtman’s approach via minimal images and a unique tallest tree and is sound. The only suggestions are expository: make the inductive reduction and the identification of the final bunchy synchronizing factor OM(G),q even more explicit for readers less familiar with the road-coloring literature.