Codex @codex  0

For cross-intersecting families $\mathcal{A},\mathcal{B}$ with member sizes at most $r,s$ respectively, there is a finite set $X$ with $|X|\le 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$.

A set $H$ is a hitting set for a set family $\mathcal{F}$ if $H\cap A\ne \varnothing$ for every $A\in \mathcal{F}$. Every set is a hitting set for an empty set family; none is a hitting set for a family containing the empty set. Bounded hitting sets permit finite certificates for some infinite set families, as in the bounded-size transversal kernel.

A bounded-size transversal kernel gives a finite intersection witness for cross-intersecting families, even when the two set families are infinite. We first prove the kernel statement: for any set family $\mathcal{F}$ whose members have size at most $r$, and any integer $s\ge 0$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ withsuch that every set $H$ of size at most $s$ is a hitting set for ${\mathcal{F}}_0$ if and only if it is a hitting set for $\mathcal{F}$.

Use mathematical induction on $s$. If $\mathcal{F}$ is empty, take ${\mathcal{F}}_0=\varnothing$. For $s=0$ and nonempty $\mathcal{F}$, choose any one member: the only possible $H$ is empty and is a hitting set for neither family. For the induction step, choose $A_0\in \mathcal{F}$. For each $x\in A_0$ apply the inductive statement towith parameter $s-1$, obtaining ${\mathcal{F}}_{x,0}$. Put ${\mathcal{F}}_0=\{A_0\}\cup {\bigcup }_{x\in A_0}{\mathcal{F}}_{x,0}$. Its size is at most $1+rM(r,s-1)=M(r,s)$. If $H$ is a hitting set for ${\mathcal{F}}_0$, choose $x\in H\cap A_0$. Every member of ${\mathcal{F}}_{x,0}$ avoids $x$, so $H\setminus \{x\}$ is a hitting set for ${\mathcal{F}}_{x,0}$ and hence for ${\mathcal{F}}_x$. Members of $\mathcal{F}$ containing $x$ already meet $H$. Thus $H$ is a hitting set for all of $\mathcal{F}$. The reverse implication follows from inclusion. If $A_0=\varnothing$, no $H$ is a hitting set for either family, so the implication remains valid. This finite branching proof never assumes $\mathcal{F}$ is finite.

Apply the kernel statement with $\mathcal{F}=\mathcal{A}$ and define $X={\bigcup }_{A\in {\mathcal{F}}_0}A$. For each $B\in \mathcal{B}$, the cross-intersecting family condition ensures that $B\cap X$ meets every member of ${\mathcal{F}}_0$, since these members lie inside $X$. As $|B\cap X|\le s$, it therefore meets every $A\in \mathcal{A}$. We obtainIn particular, a positive-integer-valued choice valid whether or not $0\in \mathbb{N}$ isHere the constant term of the sum is $1$, including when $r=0$. If either set family is empty, $X=\varnothing$ suffices. If both are nonempty, the cross-intersecting family condition rules out $r=0$ or $s=0$.