A better bound for locally thin set families (Q5947361): Difference between revisions

A family \({\mathcal F}\) of subsets of a ``ground set'' \(A\) of \(n\) elements is 4-locally thin if, for any 4 distinct members of \({\mathcal F}\), at least one member of \(A\) is contained in exactly one of the 4; \(M(n)\) denotes the maximum cardinality of such a family \({\mathcal F}\). All logarithms are to base 2; \(h\) denotes the ``binary entropy function'', defined by \(h(t)=-t\log t-(1-t)\log t\). It is shown in Theorem 2.1 that \[ \limsup_{n\to\infty}\frac{\log M(n)}n\leq\frac 12\max\limits_{p\in[0,1]}\left[(1-p^2)h\left(\frac{1-p}{1+p}\right)\right]. \] Through computer calculations the authors deduce that the cardinality of a 4-locally thin family cannot exceed \(2^{0.4561n}\). This improves on results contained in [\textit{N. Alon, E. Fachini}, and \textit{J. Körner}, Comb. Probab. Comput. 9, No. 6, 481-488 (2000; Zbl 0972.05050)] and [\textit{N. Alon, J. Körner}, and \textit{A. Monti}, Comb. Probab. Comput. 9, No. 5, 381-390 (2000; Zbl 0978.05070)].