On a Covering Problem in the Hypercube


Creative Commons License

ÖZKAHYA L., Stanton B.

GRAPHS AND COMBINATORICS, vol.31, no.1, pp.235-242, 2015 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 31 Issue: 1
  • Publication Date: 2015
  • Doi Number: 10.1007/s00373-013-1379-8
  • Journal Name: GRAPHS AND COMBINATORICS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.235-242
  • Hacettepe University Affiliated: Yes

Abstract

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.