Hitting Sets and Colorings of Hypergraphs

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.