Intersections ofk-element sets |
| |
Authors: | D. J. Kleitman J. Shearer D. Sturtevant |
| |
Affiliation: | (1) Massachusetts Institute of Technology, 02 139 Cambridge, MA, U.S.A. |
| |
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. 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. |
| |
Keywords: | 05 C 65 05 C 35 |
本文献已被 SpringerLink 等数据库收录! |