The maximum size of intersecting and union families of sets

Mark Siggers, Norihide Tokushige

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We consider the maximal size of families of k-element subsets of an n element set [. n] that satisfy the properties that every r subsets of the family have non-empty intersection, and no ℓ subsets contain [. n] in their union. We show that for large enough n, the largest such family is the trivial one of all (n-2k-1) subsets that contain a given element and do not contain another given element. Moreover we show that unless such a family is such that all subsets contain a given element, or all subsets miss a given element, then it has size at most 9(n-2k-1).We also obtain versions of these statements for weighted non-uniform families.

Original languageEnglish
Pages (from-to)128-138
Number of pages11
JournalEuropean Journal of Combinatorics
Volume33
Issue number2
DOIs
StatePublished - Feb 2012

Fingerprint

Dive into the research topics of 'The maximum size of intersecting and union families of sets'. Together they form a unique fingerprint.

Cite this