Cover-Decomposition and polychromatic numbers
A colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each colour; the polychromatic number is the maximum number of colours in such a colouring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2011
|
| _version_ | 1797104932186226688 |
|---|---|
| author | Bollobás, B Pritchard, D Rothvo, T Scott, A |
| author_facet | Bollobás, B Pritchard, D Rothvo, T Scott, A |
| author_sort | Bollobás, B |
| collection | OXFORD |
| description | A colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each colour; the polychromatic number is the maximum number of colours in such a colouring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric settings, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size and degree). Our goal is to get good lower bounds in natural hypergraph families not arising from geometry. We obtain algorithms yielding near-tight bounds for three hypergraph families: those with bounded hyperedge size, those representing paths in trees, and those with bounded VC-dimension. To do this, we link cover-decomposition to iterated relaxation of linear programs via discrepancy theory. © 2011 Springer-Verlag Berlin Heidelberg. |
| first_indexed | 2024-03-07T06:40:22Z |
| format | Journal article |
| id | oxford-uuid:f913f209-ab1d-41b8-8e3a-0e8372941b2e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:40:22Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:f913f209-ab1d-41b8-8e3a-0e8372941b2e2022-03-27T12:55:09ZCover-Decomposition and polychromatic numbersJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f913f209-ab1d-41b8-8e3a-0e8372941b2eEnglishSymplectic Elements at Oxford2011Bollobás, BPritchard, DRothvo, TScott, AA colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each colour; the polychromatic number is the maximum number of colours in such a colouring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric settings, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size and degree). Our goal is to get good lower bounds in natural hypergraph families not arising from geometry. We obtain algorithms yielding near-tight bounds for three hypergraph families: those with bounded hyperedge size, those representing paths in trees, and those with bounded VC-dimension. To do this, we link cover-decomposition to iterated relaxation of linear programs via discrepancy theory. © 2011 Springer-Verlag Berlin Heidelberg. |
| spellingShingle | Bollobás, B Pritchard, D Rothvo, T Scott, A Cover-Decomposition and polychromatic numbers |
| title | Cover-Decomposition and polychromatic numbers |
| title_full | Cover-Decomposition and polychromatic numbers |
| title_fullStr | Cover-Decomposition and polychromatic numbers |
| title_full_unstemmed | Cover-Decomposition and polychromatic numbers |
| title_short | Cover-Decomposition and polychromatic numbers |
| title_sort | cover decomposition and polychromatic numbers |
| work_keys_str_mv | AT bollobasb coverdecompositionandpolychromaticnumbers AT pritchardd coverdecompositionandpolychromaticnumbers AT rothvot coverdecompositionandpolychromaticnumbers AT scotta coverdecompositionandpolychromaticnumbers |