Hitting sets and colorings of hypergraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914579637862400 |
|---|---|
| author | Bursics, Balázs Csonka, Bence Szepessy, Luca |
| author_facet | Bursics, Balázs Csonka, Bence Szepessy, Luca |
| contents | In this paper we study the minimal size of edges in hypergraph families that guarantees the existence of a polychromatic coloring, that is, a $k$-coloring of a vertex set such that every hyperedge contains a vertex of all $k$ color classes. We also investigate the connection of this problem with $c$-shallow hitting sets: sets of vertices that intersect each hyperedge in at least one and at most $c$ vertices.
We determine for some hypergraph families the minimal $c$ for which a $c$-shallow hitting set exists.
We also study this problem for a special hypergraph family, which is induced by arithmetic progressions with a difference from a given set. We show connections between some geometric hypergraph families and the latter, and prove relations between the set of differences and polychromatic colorability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_12154 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hitting sets and colorings of hypergraphs Bursics, Balázs Csonka, Bence Szepessy, Luca Combinatorics 05C15 (Primary), 05C65 (Secondary) In this paper we study the minimal size of edges in hypergraph families that guarantees the existence of a polychromatic coloring, that is, a $k$-coloring of a vertex set such that every hyperedge contains a vertex of all $k$ color classes. We also investigate the connection of this problem with $c$-shallow hitting sets: sets of vertices that intersect each hyperedge in at least one and at most $c$ vertices. We determine for some hypergraph families the minimal $c$ for which a $c$-shallow hitting set exists. We also study this problem for a special hypergraph family, which is induced by arithmetic progressions with a difference from a given set. We show connections between some geometric hypergraph families and the latter, and prove relations between the set of differences and polychromatic colorability. |
| title | Hitting sets and colorings of hypergraphs |
| topic | Combinatorics 05C15 (Primary), 05C65 (Secondary) |
| url | https://arxiv.org/abs/2307.12154 |