Abstract
LetF be a collection ofk-element sets with the property that the intersection of no two should be included in a third. We show that such a collection of maximum size satisfies .2715k+o(k)≦≦log2 |F|≦.7549k+o(k) settling a question raised by Erdős. The lower bound is probabilistic, the upper bound is deduced via an entropy argument. Some open questions are posed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Erdős, private communication.
R. McEliece,The Theory of Information and Coding, Encyclopedia of Mathematics, Vol. 3, Addison-Wesley, Reading, Massachusetts, 1977.
Author information
Authors and Affiliations
Additional information
This research has been supported in part by the Office of Naval Research under Contract N00014-76-C-0366.
Supported in part by a NSF postdoctoral Fellowship.