부산대학교 도서관

Summary: ``A polychromatic $k$-coloring of a hypergraph assigns to each vertex one of $k$ colors in such a way that every hyperedge contains all the colors. A range capturing hypergraph is an $m$-uniform hypergraph whose vertices are points in the plane and whose hyperedges are those $m$-subsets of points that can be separated by some geometric object of a particular type, such as axis-aligned rectangles, from the remaining points. Polychromatic $k$-colorings of $m$-uniform range capturing 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 determined by a bottomless rectangle or by a horizontal strip in general do not allow for polychromatic colorings. This strengthens the corresponding result of Chen, Pach, Szegedy, and Tardos [Random Struct. Algorithms, 34:11--23, 2009] [MR2478536] for axis-aligned rectangles, and gives the first explicit (not randomized) construction of non-2-colorable hypergraphs defined by axis-aligned rectangles of arbitrarily large uniformity. \par ``In general we consider unions of range capturing hypergraphs, each defined by a type of unbounded axis-aligned rectangles. For each combination of types, we show that the unions of such hypergraphs either 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-colorings for any $m$.''