부산대학교 도서관

Summary: ``A polychromatic $k$-coloring of a hypergraph assigns to eachvertex one of $k$ colors in such a way that every hyperedge containsall the colors. A range capturing hypergraph is an $m$-uniformhypergraph whose vertices are points in the plane and whose hyperedgesare those $m$-subsets of points that can be separated by some geometricobject of a particular type, such as axis-aligned rectangles, from theremaining points. Polychromatic $k$-colorings of $m$-uniform rangecapturing hypergraphs are motivated by the study of weak$\varepsilon$-nets and cover decomposability problems.\par ``We show that the hypergraphs in which each hyperedge is determinedby a bottomless rectangle or by a horizontal strip in general do notallow for polychromatic colorings. This strengthens the correspondingresult of Chen, Pach, Szegedy, and Tardos [Random Struct. Algorithms,34:11--23, 2009] [MR2478536] for axis-alignedrectangles, and gives the first explicit (not randomized) constructionof non-2-colorable hypergraphs defined by axis-aligned rectangles ofarbitrarily large uniformity.\par ``In general we consider unions of range capturing hypergraphs, eachdefined by a type of unbounded axis-aligned rectangles. For eachcombination of types, we show that the unions of such hypergraphseither admit polychromatic $k$-colorings for $m=O(k)$, $m=O(k \log k)$,$m=O(k^{8.75})$, or do not admit in general polychromatic 2-coloringsfor any $m$.''