BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220208T163000
DTEND;TZID=Asia/Seoul:20220208T173000
DTSTAMP:20260423T190722
CREATED:20220208T073000Z
LAST-MODIFIED:20240707T080447Z
UID:5159-1644337800-1644341400@dimag.ibs.re.kr
SUMMARY:Pascal Gollin\, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
DESCRIPTION: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. \nWe 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. \nA 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. \nThis is joint work with Kevin Hendrey\, Ken-ichi Kawarabayashi\, O-joung Kwon\, Sang-il Oum\, and Youngho Yoo.
URL:https://dimag.ibs.re.kr/event/2022-02-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR