= Bounded-size transversal kernel
{title2=$M(r,s)=\sum_{j=0}^s r^j$}
If the members of a possibly infinite <set family> $\mathcal F$ have size at most $r$, there is a finite <subset> $\mathcal F_0\subseteq\mathcal F$ of size at most $M(r,s)$ with exactly the same <hitting sets> of size at most $s$. Use <mathematical induction> on $s$. For nonempty $\mathcal F$, choose $A_0\in\mathcal F$. When $s=0$ this one member suffices. Otherwise, for each $x\in A_0$, retain an inductive kernel for $\mathcal F_x=\{A\in\mathcal F:x\notin A\}$ at parameter $s-1$, and take their <set union> together with $A_0$. Its size is at most $1+rM(r,s-1)=M(r,s)$. A <hitting set> $H$ for this kernel meets $A_0$ at some $x$; $H\setminus\{x\}$ meets the kernel for $\mathcal F_x$, hence all of $\mathcal F_x$, while $x$ meets the other members of $\mathcal F$. If $A_0$ is empty no <hitting set> exists, and if $\mathcal F$ is empty its kernel is empty. Only finite branching is used, so no finiteness assumption on $\mathcal F$ is needed.
Back to article page
