Property B

From Wikipedia, the free encyclopedia

In mathematics, Property B is a certain set theoretic property. Formally, given a finite set X, a collection C of subsets of X, all of size n, has Property B iff we can partition X into two disjoint subsets Y and Z such that every set in C meets both Y and Z. The smallest number of sets of size n that do not have Property B is denoted by m(n).

[edit] Values of m(n)

It is known that m(1) = 1, m(2) = 3, and m(3) = 7 (as can by seen by the following examples); the value of m(4) is not known, although an upper bound of 23 (Seymour, Toft) and a lower bound of 21 (Manning) have been proven. At the time of this writing (August 2004), there is no OEIS entry for the sequence m(n) yet, due to the lack of terms known.

m(1)

For n = 1, set X = {1}, and C = {{1}}. Then C does not have Property B.

m(2)

For n = 2, set X = {1, 2, 3} and C = {{1, 2}, {1, 3}, {2, 3}}. Then C does not have Property B, so m(2) <= 3. However, C' = {{1, 2}, {1, 3}} does (set Y = {1} and Z = {2, 3}), so m(2) >= 3.

m(3)

For n = 3, set X = {1, 2, 3, 4, 5, 6, 7}, and C = {{1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {4, 5, 7}, {5, 6, 1}, {6, 7, 2}, {7, 1, 3}} (the Steiner triple system S₇); C does not have Property B (so m(3) <= 7), but if any element of C is omitted, then that element can be taken as Y, and the set of remaining elements C' will have Property B (so for this particular case, m(3) >= 7). One may check all other collections of 6 3-sets to see that all have Property B.

[edit] References

• Seymour, A note on a combinatorial problem of Erdős and Hajnal, Bull. London Math. Soc. 2:8 (174), 681-682
• Toft, On colour-critical hypergraphs, in Infinite and Finite Sets, ed. A. Hajnal et al, North Holland Publishing Co., 1975, 1445-1457
• G. M. Manning, Some results on the m(4) problem of Erdős and Hajnal, Electron. Research Announcements of the American Mathematical Society, 1(1995) 112-113