2023/07/22 by Bursics, Balázs, Csonka, Bence, Szepessy, Luca · 1 citation
#05C15 (Primary) #05C65 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2307.12154
In this paper we study the minimal size of edges in hypergraph families that guarantees the existence of a polychromatic coloring, that is, a k-coloring of a vertex set such that every hyperedge contains a vertex of all k color classes. We also investigate the connection of this problem with c-shallow hitting sets: sets of vertices that intersect each hyperedge in at least one and at most c vertices. We determine for some hypergraph families the minimal c for which a c-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 prove relations between the set of differences and polychromatic colorability.