The maximum sum of sizes of cross-intersecting families of subsets of a set

preprint2021arXivOpen access

Abstract

A set of sets is called a family. Two families A\mathcal{A} and B\mathcal{B} of sets are said to be cross-intersecting if each member of A\mathcal{A} intersects each member of B\mathcal{B}. For any two integers nn and kk with 1≤k≤n1 \leq k \leq n, let ([n]≤k){[n] \choose \leq k} denote the family of subsets of [n]={1,…,n}[n] = \{1, \dots, n\} that have at most kk elements. We show that if A\mathcal{A} is a non-empty subfamily of ([n]≤r){[n] \choose \leq r}, B\mathcal{B} is a non-empty subfamily of ([n]≤s){[n] \choose \leq s}, r≤sr \leq s, and A\mathcal{A} and B\mathcal{B} are cross-intersecting, then ∣A∣+∣B∣≤1+∑i=1s((ni)−(n−ri)),|\mathcal{A}| + |\mathcal{B}| \leq 1 + \sum_{i=1}^s \left({n \choose i} - {n-r \choose i} \right), and equality holds if A={[r]}\mathcal{A} = \{[r]\} and B\mathcal{B} is the family of sets in ([n]≤s){[n] \choose \leq s} that intersect [r][r].

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.