The maximum number of disjoint pairs in a family of subsets

N. Alon, P. Frankl

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)13-21
Number of pages9
JournalGraphs and Combinatorics
Volume1
Issue number1
DOIs
StatePublished - Dec 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'The maximum number of disjoint pairs in a family of subsets'. Together they form a unique fingerprint.

  • Cite this