Packing nearly-disjoint sets |
| |
Authors: | P. D. Seymour |
| |
Affiliation: | (1) Department of Mathematics, The Ohio State University, 43210 Columbus, Ohio, USA |
| |
Abstract: | De Bruijn and Erdős proved that ifA 1, ...,A k are distinct subsets of a set of cardinalityn, and |A i ∩A j |≦1 for 1≦i<j ≦k, andk>n, then some two ofA 1, ...,A k have empty intersection. We prove a strengthening, that at leastk /n ofA 1, ...,A k are pairwise disjoint. This is motivated by a well-known conjecture of Erdőds, Faber and Lovász of which it is a corollary. Partially supported by N. S. F. grant No. MCS—8103440 |
| |
Keywords: | 05 C 65 05 C 15 |
本文献已被 SpringerLink 等数据库收录! |
|