BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
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:20250203
DTEND;VALUE=DATE:20250206
DTSTAMP:20260417T070506
CREATED:20250121T050727Z
LAST-MODIFIED:20250121T050727Z
UID:10456-1738540800-1738799999@dimag.ibs.re.kr
SUMMARY:IBS-DIMAG Winter School on Graph Minors\, Week 1
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/graph-minors-week-1/
LOCATION:Room B109\, IBS (기초과학연구원)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250204T163000
DTEND;TZID=Asia/Seoul:20250204T173000
DTSTAMP:20260417T070506
CREATED:20241226T073135Z
LAST-MODIFIED:20241230T024913Z
UID:10324-1738686600-1738690200@dimag.ibs.re.kr
SUMMARY:Jang Soo Kim (김장수)\, Longest elements in a semigroup of functions and Slater indices
DESCRIPTION:The group \( S_n \) of permutations on \([n]=\{1\,2\,\dots\,n\} \) is generated by simple transpositions \( s_i = (i\,i+1) \). The length \( \ell(\pi) \) of a permutation \( \pi \) is defined to be the minimum number of generators whose product is \( \pi \). It is well-known that the longest element in \( S_n \) has length \( n(n-1)/2 \). Let \( F_n \) be the semigroup of functions \( f:[n]\to[n] \)\, which are generated by the simple transpositions \( s_i \) and the function \( t:[n]\to[n] \) given by \( t(1) =t(2) = 1 \) and \( t(i) = i \) for \( i\ge3 \). The length \( \ell(f) \) of a function \( f\in F_n \) is defined to be the minimum number of these generators whose product is \( f \). In this talk\, we study the length of longest elements in \( F_n \). We also find a connection with the Slater index of a tournament of the\ncomplete graph \( K_n \). This is joint work with Yasuhide Numata.
URL:https://dimag.ibs.re.kr/event/2025-02-04/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20250210
DTEND;VALUE=DATE:20250213
DTSTAMP:20260417T070506
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:20260417T070506
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
BEGIN:VEVENT
DTSTART;VALUE=DATE:20250217
DTEND;VALUE=DATE:20250220
DTSTAMP:20260417T070506
CREATED:20250121T051001Z
LAST-MODIFIED:20250121T051001Z
UID:10462-1739750400-1740009599@dimag.ibs.re.kr
SUMMARY:IBS-DIMAG Winter School on Graph Minors\, Week 3
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/graph-minors-week-3/
LOCATION:Room B109\, IBS (기초과학연구원)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250218T163000
DTEND;TZID=Asia/Seoul:20250218T173000
DTSTAMP:20260417T070506
CREATED:20250123T111843Z
LAST-MODIFIED:20250123T111843Z
UID:10488-1739896200-1739899800@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Erdős-Pósa property of A-paths in unoriented group-labelled graphs
DESCRIPTION:A family $\mathcal{F}$ of graphs is said to satisfy the Erdős-Pósa property if there exists a function $f$ such that for every positive integer $k$\, every graph $G$ contains either $k$ (vertex-)disjoint subgraphs in $\mathcal{F}$ or a set of at most $f(k)$ vertices intersecting every subgraph of $G$ in $\mathcal{F}$. We characterize the obstructions to the Erdős-Pósa property of $A$-paths in unoriented group-labelled graphs. As a result\, we prove that for every finite abelian group $\Gamma$ and for every subset $\Lambda$ of $\Gamma$\, the family of $\Gamma$-labelled $A$-paths whose lengths are in $\Lambda$ satisfies the half-integral relaxation of the Erdős-Pósa property. Moreover\, we give a characterization of such $\Gamma$ and $\Lambda\subseteq\Gamma$ for which the same family of $A$-paths satisfies the full Erdős-Pósa property. This is joint work with Youngho Yoo.
URL:https://dimag.ibs.re.kr/event/2025-02-18/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250225T163000
DTEND;TZID=Asia/Seoul:20250225T173000
DTSTAMP:20260417T070506
CREATED:20250104T011404Z
LAST-MODIFIED:20250214T002236Z
UID:10354-1740501000-1740504600@dimag.ibs.re.kr
SUMMARY:Sepehr Hajebi\, The pathwidth theorem for induced subgraphs
DESCRIPTION:We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H\, every graph of sufficiently large pathwidth contains either a large complete subgraph\, a large complete bipartite induced minor\, or an induced minor isomorphic to H. The second result describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor. \nWe will also try to discuss the proof of the first result with as much detail as time permits. \nBased on joint work with Maria Chudnovsky and Sophie Spirkl.
URL:https://dimag.ibs.re.kr/event/2025-02-25/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR