License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.48
URN: urn:nbn:de:0030-drops-64611
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6461/
Gusev, Vladimir V. ;
Pribavkina, Elena V.
On Synchronizing Colorings and the Eigenvectors of Digraphs
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.
BibTeX - Entry
@InProceedings{gusev_et_al:LIPIcs:2016:6461,
author = {Vladimir V. Gusev and Elena V. Pribavkina},
title = {{On Synchronizing Colorings and the Eigenvectors of Digraphs}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {48:1--48:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6461},
URN = {urn:nbn:de:0030-drops-64611},
doi = {10.4230/LIPIcs.MFCS.2016.48},
annote = {Keywords: the road coloring problem, synchronizing automata, edge-colorings of digraphs, Perron-Frobenius eigenvector, primitive digraphs}
}
|
Keywords: |
|
the road coloring problem, synchronizing automata, edge-colorings of digraphs, Perron-Frobenius eigenvector, primitive digraphs |
|
Collection: |
|
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.08.2016 |
