### 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))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))(_{ 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 language | English (US) |
---|---|

Pages (from-to) | 13-21 |

Number of pages | 9 |

Journal | Graphs and Combinatorics |

Volume | 1 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1985 |

Externally published | Yes |

### 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

Alon, N., & Frankl, P. (1985). The maximum number of disjoint pairs in a family of subsets.

*Graphs and Combinatorics*,*1*(1), 13-21. https://doi.org/10.1007/BF02582924