A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911376348282880 |
|---|---|
| author | Gollin, J. Pascal Hendrey, Kevin Kawarabayashi, Ken-ichi Kwon, O-joung Oum, Sang-il |
| author_facet | Gollin, J. Pascal Hendrey, Kevin Kawarabayashi, Ken-ichi Kwon, O-joung Oum, Sang-il |
| contents | Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles.
A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $\ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_01986 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups Gollin, J. Pascal Hendrey, Kevin Kawarabayashi, Ken-ichi Kwon, O-joung Oum, Sang-il Combinatorics 05C38, 05C70, 05C78, 05C25 Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $\ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties. |
| title | A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups |
| topic | Combinatorics 05C38, 05C70, 05C78, 05C25 |
| url | https://arxiv.org/abs/2102.01986 |