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 language | English (US) |
---|---|
Pages (from-to) | 91-97 |
Number of pages | 7 |
Journal | Combinatorica |
Volume | 2 |
Issue number | 1 |
DOIs | |
State | Published - Mar 1982 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics
Keywords
- AMS subject classification (1980): 05C65, 05C15