A uniform set covering lemma

Abstract:

The bounded set system $H = (V,\mathfrak {F})$ is composed of a nonvoid set $V$ and a set, $\mathfrak {F}$, of nonvoid subsets of $V$, a finite number of which cover $V$. $C \subset V$ is a critical subset of $H$ if every proper subset of $C$ requires fewer members of $\mathfrak {F}$ to cover it than are needed to cover $C$. For $|\mathfrak {F}|$ finite, it is shown that every $A \subset V$ contains a critical $C \subset A$ requiring the same number of members of $\mathfrak {F}$ in a minimum cover. For $v \in V,l(v)$ is the largest number of members of $\mathfrak {F}$ in any minimum cover of any critical set containing $v$. For $|\mathfrak {F}|$ finite, it is shown that there exists a covering ${A_1},{A_2}, \cdots ,{A_k},{A_i} \in \mathfrak {F}$ for $1 \leq i \leq k$, such that $v \in \bigcup \nolimits _{i = 1}^{l(v)} {{A_i}}$ for all $v \in V$. An application to graph coloring is described.