Chapter 6: Q34SE (page 440)
Let\({\rm{S}}\)be a set. We say that a collection of subsets\({{\rm{A}}_{\rm{1}}}{\rm{,}}{{\rm{A}}_{\rm{2}}}{\rm{, \ldots ,}}{{\rm{A}}_{\rm{n}}}\)each containing\({\rm{d}}\)elements, where\({\rm{d}} \ge {\rm{2}}\), is\({\rm{2 - }}\)colorable if it is possible to assign to each element of\({\rm{S}}\)one of two different colors so that in every subset\({{\rm{A}}_{\rm{i}}}\)there are elements that have been assigned each color. Let\({\rm{m(d)}}\)be the largest integer such that every collection of fewer than\({\rm{m(d)}}\)sets each containing\({\rm{d}}\)elements is\({\rm{2 - }}\)colorable.
a) Show that the collection of all subsets with\({\rm{d}}\)elements of a set\({\rm{S}}\)with\({\rm{2d - 1}}\)elements is not\({\rm{2 - }}\)colorable.
b) Show that\({\rm{m(2) = 3}}\).
c) Show that\({\rm{m(3) = 7}}\). (Hint: Show that the collection\({\rm{\{ 1,3,5\} ,\{ 1,2,6\} ,\{ 1,4,7\} ,\{ 2,3,4\} ,\{ 2,5,7\} ,\{ 3,6,7\} ,\{ 4,5,6\} }}\)is not\({\rm{2 - }}\)colorable. Then show that all collections of six sets with three elements each are\({\rm{2 - }}\)colorable.)
Short Answer
(a) The total of all \({\rm{S}}\) subsets are not \({\rm{2 - }}\)colorable.
(b) Every pair of two-subsets can be colored twice.
(c) \({\rm{\{ 1,3,5\} ,\{ 1,2,6\} ,\{ 1,4,7\} ,\{ 2,3,4\} ,\{ 2,5,7\} ,\{ 4,5,6\} ,\{ 3,6,7\} }}\) We try to use red and blue to color the subgroups. Assume that 1 is red without losing generality. At least one of the numbers 2 and \({\rm{6}}\) must be blue. If 2 is red, then \({\rm{6}}\) must be blue, implying that one of the numbers \({\rm{4,5}}\)must be red, and hence 3 must be blue. This also implies that \({\rm{7}}\) must be red, meaning that 4 must be blue and that \({\rm{5}}\) must be red. As a result, \({\rm{2,5,7}}\)is all red, which is a contradiction.