Sequence needing more terms, related to "Property B" ===================================================== The following is a sequence that at the present time is too short to include in the OEIS: m(1) = 1, m(2) = 3, m(3) = 7, m(4) = 21, 22 or 23? m(n) is the smallest number of sets of size n that do not have Property B. It would nice if the resources of the math-fun list, the seq-fan list and the Web could be harnessed to determine m(4)! -------------------------------------------------------- Here are more details (though I'm not an expert on the problem, so some of what follows may be incorrect or out-of-date). Definition: We work inside a finite set X of unspecified size. A collection C of subsets of X, all of size n, has Property B if we can partition X into two disjoint subsets X = Y union Z such that every set in C meets both Y and Z. Illustrations for n = 1, 2, 3: n=1: take X = {1}. Then the collection C = { {1} } does not have Property B. n=2, X={1,2,3}, C = { {1,2}, {1,3}, {2,3} } does not have Property B. C={ {1,2}, {1,3} } does, because we can take Y = {1}, Z={2,3}. n=3: take X={1..7}, C={ the 7 Steiner triples } = cyclic shifts of {1, 2, 4} does not have Property B. If any subset is omitted from C then that subset can be taken as Y and the 6 subsets do have Prop. B. References: The problem of finding m(4) was mentioned by E C Milner in his address at the 1974 Internat. Congress of Mathematicians in Vancouver. Donovan Hare tells me that the upper bound of 23 was found by Seymour (A Note on a Combinatorial Problem of Erdos and Hajnal. Bull. London Math. Soc. 2:8 (174), 681-682) and independently Toft (On Colour-critical Hypergraphs, in Infinite and Finite Sets, ed. A. Hajnal et al, North Holland Publishing Co., 1975, 1445-1457). According to Harvey Abbott (I am indebted to Donovan Hare for passing on this information), the lower bound of 21 is due to G.M. Manning: "Some results on the m(4) problem of Erdos and Hajnal", Electron. Research Announcements of the American Mathematical Society, 1(1995) 112-113. --------------------------------------------------------------- Other references for background:
From MathSciNet:
MR1849460 (2002f:05156) Abbott, H. L.; Hare, D. R. Families of 4-sets without property B. Ars Combin. 60 (2001), 239--245. 05D05 MR1088279 (91j:05075) Exoo, Geoffrey On constructing hypergraphs without Property B. Ars Combin. 30 (1990), 3--12. 05C65 MR1045053 (91i:54020) Jiang, Ji Guang Paracompactness and the property $b\sb 1$. (Chinese) Acta Math. Sinica 32 (1989), no. 4, 551--555. 54D20 MR0982108 (90c:05001) Abbott, H. L.; Liu, A. On property $B(4)$ of families of sets. Ars Combin. 26 (1988), 59--68. (Reviewer: E. C. Milner) 05A05 MR0944353 (89e:51009) Boros, Endre ${\rm PG}(2,p\sp s),\;p>2,$ has property $B(p+2)$. Ars Combin. 25 (1988), 111--113. (Reviewer: Anne Delandtsheer) 51E20 (05B25) MR0918392 (89a:05006) Abbott, H. L.; Liu, A. On a problem of Erdös concerning property $B$. Combinatorica 7 (1987), no. 3, 215--219. (Reviewer: G. F. Clements) 05A05 MR0429593 (55 #2604) de Vries, Hans Ludwig On property B and on Steiner systems. Math. Z. 153 (1977), no. 2, 155--159. (Reviewer: N. S. Mendelsohn) 05B05 (05A05) MR0392583 (52 #13400) Johnson, David S. On property $B\sb{r}$. J. Combinatorial Theory Ser. B 20 (1976), no. 1, 64--66. 05A05 MR0340086 (49 #4842) Woodall, D. R. Property $B$ and the four-colour problem. Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 322--340. Inst. Math. Appl., Southend-on-Sea, 1972. (Reviewer: F. Bernhart) 05C15 Google gave many hits, one of which is a related paper by Peter Erdos: www.renyi.hu/~elp/prop-b.pdf Neil Sloane (njas@research.att.com), Aug 17 2004