On universal partial words for word-patterns and set partitions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 5

Universal words are words containing exactly once each element from a given set of combinatorial structures admitting encoding by words. Universal partial words (u-p-words) contain, in addition to the letters from the alphabet in question, any number of occurrences of a special “joker” symbol. We initiate the study of u-p-words for word-patterns (essentially, surjective functions) and (2-)set partitions by proving a number of existence/non-existence results and thus extending the results in the literature on u-p-words and u-p-cycles for words and permutations. We apply methods of graph theory and combinatorics on words to obtain our results.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2020004
Classification : 68R15
Keywords: universal word, partial word, set partition, word-pattern, De Bruijn graph, Eulerian path, Hamiltonian path 
@article{ITA_2020__54_1_A5_0,
     author = {Chen, Herman Z. Q. and Kitaev, Sergey},
     title = {On universal partial words for word-patterns and set partitions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     year = {2020},
     publisher = {EDP Sciences},
     volume = {54},
     doi = {10.1051/ita/2020004},
     mrnumber = {4107501},
     zbl = {1460.68079},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2020004/}
}
TY  - JOUR
AU  - Chen, Herman Z. Q.
AU  - Kitaev, Sergey
TI  - On universal partial words for word-patterns and set partitions
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2020
VL  - 54
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2020004/
DO  - 10.1051/ita/2020004
LA  - en
ID  - ITA_2020__54_1_A5_0
ER  - 
%0 Journal Article
%A Chen, Herman Z. Q.
%A Kitaev, Sergey
%T On universal partial words for word-patterns and set partitions
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2020
%V 54
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ita/2020004/
%R 10.1051/ita/2020004
%G en
%F ITA_2020__54_1_A5_0
Chen, Herman Z. Q.; Kitaev, Sergey. On universal partial words for word-patterns and set partitions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 5. doi: 10.1051/ita/2020004

[1] A. Burstein and S. Kitaev, On Unavoidable Sets of Word Patterns. SIAM J. Discr. Math. 19 (2005) 371–381. | MR | Zbl | DOI

[2] H. Z. Q. Chen, S. Kitaev, T. Mütze and B. Y. Sun, On universal partial words. Discr. Math. Theor. Comp. Sci. 19 (2017) 16. | MR | Zbl

[3] F. R. K. Chung, P. Diaconis and R. Graham, Universal cycles for combinatorial structures. Discr. Math. 110 (1992) 43–59. | MR | Zbl | DOI

[4] B. Goeckner, C. Groothuis, C. Hettle, B. Kell, P. Kirkpatrick, R. Kirsch and R. Solava, Universal Partial Words over Non-Binary Alphabets. Theor. Comp. Sci. 713 (2018) 56–65. | MR | Zbl | DOI

[5] Z. Higgins, E. Kelley, B. Sieben, A. Godbole. Universal and near-universal cycles of set partitions. Electron. J. Combin. 22 (2015) 4, Paper 4.48, 15pp. | MR | Zbl | DOI

[6] S. Kitaev, V. N. Potapov and V. Vajnovszki, On shortening u-cycles and u-words for permutations. Discr. Appl. Math. 260 (2019) 203–213. | MR | Zbl | DOI

Cité par Sources :