The maximum number of disjoint pairs in a family of subsets |
| |
| Authors: | N Alon P Frankl |
| |
| Institution: | (1) Department of Mathematics, Massachusetts Institute of Technology, 02139 Cambridge, MA, USA;(2) U.E.R. Mathématiques, Université de Paris, VII, 75005 Paris, France |
| |
| Abstract: | Let ? be a family of 2 n+1 subsets of a 2n-element set. Then the number of disjoint pairs in ? is bounded by (1+o(1))22n . This proves an old conjecture of Erdös. Let ? be a family of 21/(k+1)+δ)n subsets of ann-element set. Then the number of containments in ? is bounded by (1-1/k+o(1))( 2 |?| ). This verifies a conjecture of Daykin and Erdös. A similar Erdös-Stone type result is proved for the maximum number of disjoint pairs in a family of subsets. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
