• This event has passed.

# Pascal Gollin, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

## February 8 Tuesday @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

### Speaker

Pascal Gollin
IBS Discrete Mathematics Group
https://dimag.ibs.re.kr/home/gollin/

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. We therefore say that cycles satisfy the Erdős-Pósa property. However, while odd cycles do not satisfy the Erdős-Pósa property, Reed proved in 1999 an analogue by relaxing packing to half-integral packing, where each vertex is allowed to be contained in at most two such cycles. Moreover, he gave a structural characterisation for when the Erdős-Pósa property for odd cycles fails.

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 the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property, and we similarly give a structural characterisation for the failure of the Erdős-Pósa property.

A multitude of natural properties of cycles can be encoded in this setting. For example, we show that the cycles of length $\ell$ modulo $m$ satisfy the half-integral Erdős-Pósa property, and we characterise for which values of $\ell$ and $m$ these cycles satisfy the Erdős-Pósa property.

This is joint work with Kevin Hendrey, Ken-ichi Kawarabayashi, O-joung Kwon, Sang-il Oum, and Youngho Yoo.

## Details

Date:
February 8 Tuesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Room B232
IBS (기초과학연구원)

## Organizer

Sang-il Oum (엄상일)
View Organizer Website
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.