Packing nearly-disjoint sets

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

De Bruijn and Erdo{combining double acute accent}s proved that if A 1, ..., A k are distinct subsets of a set of cardinality n, and |A i ∩A j |≦1 for 1≦i<j ≦k, and k>n, then some two of A 1, ..., A k have empty intersection. We prove a strengthening, that at least k /n of A 1, ..., A k are pairwise disjoint. This is motivated by a well-known conjecture of Erdo{combining double acute accent}ds, Faber and Lovász of which it is a corollary.

Original languageEnglish (US)
Pages (from-to)91-97
Number of pages7
JournalCombinatorica
Volume2
Issue number1
DOIs
StatePublished - Mar 1982
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification (1980): 05C65, 05C15

Fingerprint

Dive into the research topics of 'Packing nearly-disjoint sets'. Together they form a unique fingerprint.

Cite this