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:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20250210
DTEND;VALUE=DATE:20250213
DTSTAMP:20260417T083559
CREATED:20250121T050854Z
LAST-MODIFIED:20250121T050854Z
UID:10460-1739145600-1739404799@dimag.ibs.re.kr
SUMMARY:IBS-DIMAG Winter School on Graph Minors\, Week 2
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/graph-minors-week-2/
LOCATION:Room B109\, IBS (기초과학연구원)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250211T163000
DTEND;TZID=Asia/Seoul:20250211T173000
DTSTAMP:20260417T083559
CREATED:20241226T073216Z
LAST-MODIFIED:20250119T115501Z
UID:10327-1739291400-1739295000@dimag.ibs.re.kr
SUMMARY:Jungho Ahn (안정호)\, A coarse Erdős-Pósa theorem for constrained cycles
DESCRIPTION:An induced packing of cycles in a graph is a set of vertex-disjoint cycles such that the graph has no edge between distinct cycles of the set. The classic Erdős-Pósa theorem shows that for every positive integer $k$\, every graph contains $k$ vertex-disjoint cycles or a set of $O(k\log k)$ vertices which intersects every cycle of $G$. \nWe generalise this classic Erdős-Pósa theorem to induced packings of cycles of length at least $\ell$ for any integer $\ell$. We show that there exists a function $f(k\,\ell)=O(\ell k\log k)$ such that for all positive integers $k$ and $\ell$ with $\ell\geq3$\, every graph $G$ contains an induced packing of $k$ cycles of length at least $\ell$ or a set $X$ of at most $f(k\,\ell)$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$. \nFurthermore\, we extend the result to long cycles containing prescribed vertices. For a graph $G$ and a set $S\subseteq V(G)$\, an $S$-cycle in $G$ is a cycle containing a vertex in $S$. We show that for all positive integers $k$ and $\ell$ with $\ell\geq3$\, every graph $G$\, and every set $S\subseteq V(G)$\, $G$ contains an induced packing of $k$ $S$-cycles of length at least $\ell$ or a set $X$ of at most $\ell k^{O(1)}$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$. \nOur proofs are constructive and yield polynomial-time algorithms\, for fixed $\ell$\, finding either the induced packing of the constrained cycles or the set $X$. \nThis is based on joint works with Pascal Gollin\, Tony Huynh\, and O-joung Kwon.
URL:https://dimag.ibs.re.kr/event/2025-02-11/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR