Packing nearly-disjoint sets

P. D. Seymour

doi:10.1007/BF02579285

Packing nearly-disjoint sets

P. D. Seymour

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

14 Scopus citations

Abstract

De Bruijn and Erdo{combining double acute accent}s proved that if A₁, ..., 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₁, ..., A_k have empty intersection. We prove a strengthening, that at least k /n of A₁, ..., 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	https://doi.org/10.1007/BF02579285
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

Access to Document

10.1007/BF02579285

Cite this

@article{ed89c0d7760d493db85850223b886402,

title = "Packing nearly-disjoint sets",

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≦in, 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{\'a}sz of which it is a corollary.",

keywords = "AMS subject classification (1980): 05C65, 05C15",

author = "Seymour, \{P. D.\}",

year = "1982",

month = mar,

doi = "10.1007/BF02579285",

language = "English (US)",

volume = "2",

pages = "91--97",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - Packing nearly-disjoint sets

AU - Seymour, P. D.

PY - 1982/3

Y1 - 1982/3

N2 - 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≦in, 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.

AB - 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≦in, 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.

KW - AMS subject classification (1980): 05C65, 05C15

UR - https://www.scopus.com/pages/publications/51249183574

UR - https://www.scopus.com/pages/publications/51249183574#tab=citedBy

U2 - 10.1007/BF02579285

DO - 10.1007/BF02579285

M3 - Article

AN - SCOPUS:51249183574

SN - 0209-9683

VL - 2

SP - 91

EP - 97

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

Packing nearly-disjoint sets

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this