Let ℱ be a family of 2 n+1 subsets of a 2 n-element set. Then the number of disjoint pairs in ℱ is bounded by (1+o(1))22 n . This proves an old conjecture of Erdös. Let ℱ be a family of 21/(k+1)+δ)n subsets of an n-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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics