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.

We investigate the effect of the well-known Mycielski construction on the Shannon capacity of graphs and on one of its most prominent upper bounds, the (complementary) Lovász theta number. We prove that if the Shannon capacity of a graph, the distinguishability graph of a noisy channel, is attained by some finite power, then its Mycielskian has strictly larger Shannon capacity than the graph itself. For the complementary Lovász theta function we show that its value on the Mycielskian of a graph is completely determined by its value on the original graph, a phenomenon similar to the one discovered for the fractional chromatic number by Larsen, Propp and Ullman. We also consider the possibility of generalizing our results on the Sperner capacity of directed graphs and on the generalized Mycielsky construction. Possible connections with what Zuiddam calls the asymptotic spectrum of graphs are discussed as well.