= Finite intersection witness for cross-intersecting families
= Finite intersection witnesses for cross-intersecting families
{synonym}
For <cross-intersecting families> $\mathcal A,\mathcal B$ with member sizes at most $r,s$ respectively, there is a finite <set> $X$ with $|X|\leq r\sum_{j=0}^s r^j$ such that $A\cap B\cap X\ne\varnothing$ for every $A\in\mathcal A,B\in\mathcal B$. Take a <bounded-size transversal kernel> $\mathcal A_0$ preserving <hitting sets> of size at most $s$ and set $X=\bigcup_{A\in\mathcal A_0}A$. For each $B$, the <set> $B\cap X$ is a <hitting set> for $\mathcal A_0$, hence for all of $\mathcal A$. This proves the assertion even for infinite <set families>; if either family is empty, take $X=\varnothing$.
Back to article page
