Article ID Journal Published Year Pages File Type
4653915 European Journal of Combinatorics 2012 11 Pages PDF
Abstract

We consider the maximal size of families of kk-element subsets of an nn element set [n][n] that satisfy the properties that every rr subsets of the family have non-empty intersection, and no ℓℓ subsets contain [n][n] in their union. We show that for large enough nn, 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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,