The maximum number of disjoint pairs in a family of subsets | Zendy

Noga Alon | Zendy; Péter Frankl | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The maximum number of disjoint pairs in a family of subsets

Author(s) -

Noga Alon,

Péter Frankl

Publication year - 1985

Publication title -

graphs and combinatorics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.59

H-Index - 40

eISSN - 1435-5914

pISSN - 0911-0119

DOI - 10.1007/bf02582924

Subject(s) - disjoint sets , combinatorics , mathematics , conjecture , family of sets , bounded function , element (criminal law) , set (abstract data type) , discrete mathematics , computer science , mathematical analysis , political science , law , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research