2026-07-24T14:31:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6461 2024-03-06T10:38:20Z ddc:004 open_access

On Synchronizing Colorings and the Eigenvectors of Digraphs Gusev, Vladimir V. Pribavkina, Elena V. the road coloring problem synchronizing automata edge-colorings of digraphs Perron-Frobenius eigenvector primitive digraphs An automaton is synchronizing if there exists a word that sends all states of the automaton to a single state. A coloring of a digraph with a fixed out-degree k is a distribution of k labels over the edges resulting in a deterministic finite automaton. The famous road coloring theorem states that every primitive digraph has a synchronizing coloring. We study recent conjectures claiming that the number of synchronizing colorings is large in the worst and average cases. Our approach is based on the spectral properties of the adjacency matrix A(G) of a digraph G. Namely, we study the relation between the number of synchronizing colorings of G and the structure of the dominant eigenvector v of A(G). We show that a vector v has no partition of coordinates into blocks of equal sum if and only if all colorings of the digraphs associated with v are synchronizing. Furthermore, if for each b there exists at most one partition of the coordinates of v into blocks summing up to b, and the total number of partitions is equal to s, then the fraction of synchronizing colorings among all colorings of G is at least (k-s)/k. We also give a combinatorial interpretation of some known results concerning an upper bound on the minimal length of synchronizing words in terms of v. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladimir V. Gusev and Elena V. Pribavkina 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.48 urn:nbn:de:0030-drops-64611 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.48 eng https://creativecommons.org/licenses/by/3.0/legalcode