A Note on a Combinatorial Problem of ErdŐS and Hajnal

A family of sets F is said by Miller [1] to have property B if there exists a set intersecting each member of F but containing no member of F. Erdos and Hajnal [2] define m(s) to be the least k for which there exists a family F such that \F\ = k, \X\ = s for each XeF, and F does not have property B. It has been shown that w(l) = 1, m(2) = 3, m(3) = 7, but m(4) is not known. Abbott and Hanson [3] give a construction showing that m(4) ^ 24. Using a variation on their method we show that m(4) ^ 23. Let £ be a subset of D with the following properties: (i) If Y, Ze D and Y u Z = {1,..., 8} then at least one of Y, Z is a member of E. (ii) If |Z| = 3 and Z is a subset of a member of D, then Z is a subset of a member of£. Put F = C u E. Suppose that F has property B and let Z be some set intersecting all members of F but containing none. Then S—Z has the same property, so we may assume that |Zn{9, 10, 11}| < 1. But then Z does not intersect some member of A; and since Z intersects every member of C, Z must intersect every member of B. It follows that F does not have property B. Abbott and Hanson take D — E = {ZeD:2eZ and \Z n {4, 6, 8}| is even},and sohave|E| = 12. |£| = 11 and E has properties (i) and (ii) above; so F does not have property B, and m(4) ^ 23.