Universal Cycle Packings and Coverings for k-Subsets of an n-Set

Michał Dębski , Zbigniew Lonc

Abstract

Cykliczny ciąg elementów ze zbioru [n]=1,2,...,n jest (n,k)-uniwersalnym upakowaniem (odpowiednio: (n,k)-uniwersalnym pokryciem), jeżeli każdy k-podzbiór zbioru [n] występuje w tym ciągu co najwyżej raz (odpowiednio: przynajmniej raz) jako ciąg k kolejnych wyrazów. Niech p_n,k będzie długością najdłuższego (n,k)-uniwersalnego upakowania a c_n,k długością najkrótszego (n,k)-uniwersalnego pokrycia. Pokazujemy dokładniejsze niż dotąd znane asymptotyki, dla ustalonego k, dla liczb p_n,k oraz dla liczb p_n,k i c_n,k w przypadkach, gdy k zależy od n. Najciekawszy rezultat dotyczy przypadku, gdy k=o(n).
Author Michał Dębski ZAK
Michał Dębski,,
- Department of Algebra and Combinatorics
, Zbigniew Lonc ZAK
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
Journal seriesGraphs and Combinatorics, ISSN 0911-0119
Issue year2016
Vol32
No6
Pages2323-2337
Publication size in sheets0.7
Keywords in Englishuniversal cycle, ucycle packing, ucycle covering
DOIDOI:10.1007/s00373-016-1727-6
URL http://link.springer.com/article/10.1007/s00373-016-1727-6
Languageen angielski
Score (nominal)20
ScoreMinisterial score = 20.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 20.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.441 (2) - 2016=0.527 (5)
Citation count*0
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back