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 outdegree 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 (ks)/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:148:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6461},
URN = {urn:nbn:de:0030drops64611},
doi = {10.4230/LIPIcs.MFCS.2016.48},
annote = {Keywords: the road coloring problem, synchronizing automata, edgecolorings of digraphs, PerronFrobenius eigenvector, primitive digraphs}
}
2016
Keywords: 

the road coloring problem, synchronizing automata, edgecolorings of digraphs, PerronFrobenius eigenvector, primitive digraphs 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

2016 