The maximum number of disjoint pairs in a family of subsets

N. Alon; P. Frankl

doi:10.1007/BF02582924

The maximum number of disjoint pairs in a family of subsets

N. Alon, P. Frankl

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

Let ℱ be a family of 2ⁿ⁺¹ subsets of a 2 n-element set. Then the number of disjoint pairs in ℱ is bounded by (1+o(1))2^{2 n} . This proves an old conjecture of Erdös. Let ℱ be a family of 2^1/(k+1)+δ)n subsets of an n-element set. Then the number of containments in ℱ is bounded by (1-1/k+o(1))(₂ ^|ℱ| ). 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 language	English (US)
Pages (from-to)	13-21
Number of pages	9
Journal	Graphs and Combinatorics
Volume	1
Issue number	1
DOIs	https://doi.org/10.1007/BF02582924
State	Published - Dec 1985
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/BF02582924

Cite this

@article{14f5abeff7a245629d9c29f7d469d836,

title = "The maximum number of disjoint pairs in a family of subsets",

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{\"o}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{\"o}s. A similar Erd{\"o}s-Stone type result is proved for the maximum number of disjoint pairs in a family of subsets.",

author = "N. Alon and P. Frankl",

year = "1985",

month = dec,

doi = "10.1007/BF02582924",

language = "English (US)",

volume = "1",

pages = "13--21",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - The maximum number of disjoint pairs in a family of subsets

AU - Alon, N.

AU - Frankl, P.

PY - 1985/12

Y1 - 1985/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=51249179132&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51249179132&partnerID=8YFLogxK

U2 - 10.1007/BF02582924

DO - 10.1007/BF02582924

M3 - Article

AN - SCOPUS:51249179132

SN - 0911-0119

VL - 1

SP - 13

EP - 21

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

The maximum number of disjoint pairs in a family of subsets

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this