Colorful Helly via induced matchings

Abstract

We establish a theorem regarding the maximum size of an {\it{induced}} matching in the bipartite complement of the incidence graph of a set system $(X,\mathcal{F})$. We show that this quantity plus one provides an upper bound on the colorful Helly number of this set system, i.e. the minimum positive integer $N$ for which the following statement holds: if finite subfamilies ${\mathcal{F}}_1,\dots ,{\mathcal{F}}_N\subset \mathcal{F}$ are such that ${\cap }_{F\in {\mathcal{F}}_i}F=0$ for every $i=1,\dots ,N$, then there exists $F_i\in {\mathcal{F}}_i$ such that $F_1\cap \dots \cap F_N=\varnothing$. We will also discuss some natural refinements of this result and applications.

12 pages, 2 figures. Fix issue with a figure not displaying, and correct some typos