NDA
Bejelentkezés
Kapcsolat
An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes |
Tartalom: | http://real.mtak.hu/26417/ |
---|---|
Archívum: | MTA Könyvtár |
Gyűjtemény: |
Status = In Press
Type = Conference or Workshop Item |
Cím: |
An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes
|
Létrehozó: |
Keszegh, Balázs
Pálvölgyi, Dömötör
|
Dátum: |
2015
|
Téma: |
QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
|
Tartalmi leírás: |
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 $(Scap Fmid Fin FF)$ is a Sperner family, we can select an $Rsubset S$ such that $1le |Fcap R|le 2$ holds for every $Fin FF$? |
Típus: |
Conference or Workshop Item
PeerReviewed
|
Formátum: |
text
|
Azonosító: |
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)
|
Kapcsolat: |