= Diagonal-intersection set-pair bound
{title2=$|I|\leq n-r-s+2$}
Let $I$ index \b[at least two] pairs of <subsets> of an $n$-element ground <set>, with $|R_i|=r$, $|S_i|=s$, and $R_i\cap S_j\ne\varnothing$ exactly when $i=j$. Then
$$
|I|\leq n-r-s+2.
$$
Choose a witness $x_i\in R_i\cap S_i$ for each pair. The <intersection> conditions make these witnesses distinct and exclude $x_i$ from both <sets> belonging to every other index. For distinct $i,j$, the <sets> $R_i\setminus\{x_i\}$ and $S_j\setminus\{x_j\}$ are disjoint and both lie outside the entire witness <set>. Consequently $n-|I|\geq(r-1)+(s-1)$.
For sharpness, choose disjoint fixed <sets> $P,Q$ of sizes $r-1,s-1$ and let the remaining <points> be witnesses. Put $R_i=P\cup\{x_i\}$ and $S_i=Q\cup\{x_i\}$. This construction attains equality whenever there are at least two witnesses. The two-pair hypothesis cannot be dropped: a single pair $R_1=S_1=[n]$ satisfies the <intersection> condition, but for $n\geq2$ the proposed unrestricted bound would read $1\leq2-n$.
Back to article page
