DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2016.48

On Synchronizing Colorings and the Eigenvectors of Digraphs

Authors: Vladimir V. Gusev and Elena V. Pribavkina

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

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.

Cite as

Vladimir V. Gusev and Elena V. Pribavkina. On Synchronizing Colorings and the Eigenvectors of Digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gusev_et_al:LIPIcs.MFCS.2016.48,
  author =	{Gusev, Vladimir V. and Pribavkina, Elena V.},
  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 =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.48},
  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}
}

Search Results

Documents authored by Pribavkina, Elena V.

On Synchronizing Colorings and the Eigenvectors of Digraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message