= Diagonal-intersection set-pair bound
{title2=$|I|\leq n-r-s+2$}
Suppose $|R_i|=r$, $|S_i|=s$ and $R_i\cap S_j$ is nonempty exactly when $i=j$. Choose $x_i\in R_i\cap S_i$. Each witness lies in neither set of any other pair, so the witnesses are distinct. For two distinct indices, $R_i\setminus\{x_i\}$ and $S_j\setminus\{x_j\}$ are disjoint subsets outside the witness set. Thus $n-|I|\geq r+s-2$. Equality is attained by disjoint fixed cores $P,Q$ of sizes $r-1,s-1$ and distinct remaining witnesses, with $R_i=P\cup\{x_i\}$ and $S_i=Q\cup\{x_i\}$.
Back to article page
