REAL

An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes

Keszegh, Balázs and Pálvölgyi, Dömötör (2015) An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes. In: 21st International Workshop on Graph-Theoretic Concepts in Computer Science, 2015. June 17-19., Munich, Germany. (In Press)

[img]
Preview
Text
specchainWG.pdf

Download (398kB) | Preview

Abstract

The goal of this paper is to give a new, abstract approach to cover-decomposition and polychromatic colorings using hypergraphs on ordered vertex sets. We introduce an abstract version of a framework by Smorodinsky and Yuditsky, used for polychromatic coloring halfplanes, and apply it to so-called {\em ABA-free hypergraphs}, which are a special case of {\em shift-chains}. Using our methods, we prove that $(2k-1)$-uniform ABA-free hypergraphs have a polychromatic $k$-coloring, a problem posed by the second author. We also prove the same for hypergraphs defined on a point set by pseudohalfplanes. These results are best possible. We also introduce several new notions that seem to be important for investigating polychromatic colorings and $\epsilon$-nets, such as {\em shallow hitting sets} and {\em balanced polychromatic colorings}. We pose several open problems related to them. For example, is it true that given a finite point set $S$ on a sphere and a set of halfspheres $\FF$, such that $\{S\cap F\mid F\in \FF\}$ is a Sperner family, we can select an $R\subset S$ such that $1\le |F\cap R|\le 2$ holds for every $F\in \FF$?

Item Type: Conference or Workshop Item (Paper)
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Balázs Keszegh
Date Deposited: 11 Sep 2015 13:09
Last Modified: 11 Sep 2015 13:09
URI: http://real.mtak.hu/id/eprint/26417

Actions (login required)

Edit Item Edit Item