On a problem of Erdős concerning property B (Q1102961): Difference between revisions

Let \({\mathcal A}=(A_ i\), \(i\in I)\) be a family of sets. Then \({\mathcal A}\) has property B (property B(s)) if there is a set S such that \(S\cap A_ i\neq \emptyset\) and \(S\not\supset A\) \((0<| A_ i\cap S| <s)\) for all \(i\in I\). Let m(n) (m(n,s)) be the size of a smallest family \({\mathcal A}=(A_ i,\quad i\in I)\) with \(| A_ i| =n\), \(i\in I\) not possessing property B (property B(s)). It has been proved by \textit{J. Beck} [Discrete Math. 24, 127-137 (1978; Zbl 0429.05055)] that for every \(\epsilon >0\) and \(s\geq s_ 0(\epsilon)\) it holds \(m(s)>s^{1/3-\epsilon}2\quad s.\) The authors show that for \(s\geq 1\), \(m(2^{s-1},s)\leq 2\quad s-1\) and \(m(n,s)\leq 2^{s+2}-2s-4,\) provided \(n\geq 5.2^{2s-3}\) which together with the result of Beck answers in the negative the question of P. Erdős whether m(n,s)\(\geq m(s)\) for all \(n\geq s\).