On Synchronizing Colorings and the Eigenvectors of Digraphs
(2016) MFCS 2016 - 41st International Symposium on Mathematical Foundations of Computer Science
Files
LIPIcs-MFCS-2016-48.pdf
Open Access - Adobe PDF
- 549.47 KB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Gusev, V., & Pribavkina, E. V. (2016). On Synchronizing Colorings and the Eigenvectors of Digraphs. Leibniz International Proceedings in Informatics (LIPIcs), p. 48:1-48:14. https://doi.org/10.4230/LIPIcs.MFCS.2016.48