On a Covering Problem in the Hypercube

Creative Commons License

ÖZKAHYA L., Stanton B.

GRAPHS AND COMBINATORICS, cilt.31, sa.1, ss.235-242, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 31 Sayı: 1
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1007/s00373-013-1379-8
  • Dergi Adı: GRAPHS AND COMBINATORICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.235-242
  • Hacettepe Üniversitesi Adresli: Evet

Özet

In this paper, we address a particular variation of the Turan problem for the hypercube. Alon, Krech and Szab (SIAM J Discrete Math 21:66-72, 2007) asked "In an n-dimensional hypercube, Q (n) , and for a"" < d < n, what is the size of a smallest set, S, of Q (a"") 's so that every Q (d) contains at least one member of S?" Likewise, they asked a similar Ramsey type question: "What is the largest number of colors that we can use to color the copies of Q (a"") in Q (n) such that each Q (d) contains a Q (a"") of each color?" We give upper and lower bounds for each of these questions and provide constructions of the set S above for some specific cases.