Abstract. In this paper, we study the minimal size of edges in hypergraph families that guarantees the existence of a polychromatic coloring, that is, a Formula: see text-coloring of a vertex set such that every hyperedge contains a vertex of all Formula: see text color classes. We also investigate the connection of this problem with Formula: see text-shallow hitting sets: sets of vertices that intersect each hyperedge in at least one and at most Formula: see text vertices. We determine for some hypergraph families the minimal Formula: see text for which a Formula: see text-shallow hitting set exists. We also study this problem for a special hypergraph family, which is induced by arithmetic progressions with a difference from a given set. We show connections between some geometric hypergraph families and the latter, and we prove relations between the set of differences and polychromatic colorability.
Bursics et al. (Tue,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: