Periodic Partial Words and Random Bipartite Graphs

Issue title: Russian-Finnish Symposium in Discrete Mathematics

Article type: Research Article

Authors: Idiatulina, Lidia A. | Shur, Arseny M.

Affiliations: Ural Federal University, Ekaterinburg, Russia. lidiatulina@gmail.com; arseny.shur@usu.ru

Note: [] Address for correspondence: Ural Federal University, Ekaterinburg, Russia

Abstract: The interaction property (or the Fine–Wilf property) for periodic partial words is studied. Partial words with two periods are represented by bipartite graphs and the interaction property is related to the edge connectedness property of these graphs. Threshold functions for the edge connectedness of random bipartite graphs and multigraphs are found. As a corollary, the interaction property is described in probabilistic terms.

DOI: 10.3233/FI-2014-1030

Journal: Fundamenta Informaticae, vol. 132, no. 1, pp. 15-31, 2014