BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.18.0//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:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261013T163000
DTEND;TZID=Asia/Seoul:20261013T173000
DTSTAMP:20260819T090026Z
CREATED:20260811T214705Z
LAST-MODIFIED:20260819T090026Z
UID:13078-1791909000-1791912600@dimag.ibs.re.kr
SUMMARY:Julien Codsi\, Recent progress in the tree-⍺ world
DESCRIPTION:Treewidth is a graph parameter commonly used to quantify how “close” a graph is to a tree. Although it is a cornerstone of structural graph theory and algorithm design\, it is nearly useless for algorithmic purposes in many dense graph classes. In this talk\, we discuss the tree-independence number\, a more versatile graph parameter that replaces the standard width measure with the stability number. We will present recent results aimed at characterizing the graph classes in which this parameter enables sub-exponential time algorithms for problems that are\, in general\, NP-hard.
URL:https://dimag.ibs.re.kr/event/2026-10-13/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261027T163000
DTEND;TZID=Asia/Seoul:20261027T173000
DTSTAMP:20261001T042132Z
CREATED:20260917T075544Z
LAST-MODIFIED:20261001T042132Z
UID:13361-1793118600-1793122200@dimag.ibs.re.kr
SUMMARY:Xiying Du\, Characterizing (2\,3)-linked graphs
DESCRIPTION:We say a graph $G$ is $(2\,m)$-linked if\, for every choice of $m+2$ distinct vertices $a_1\,\ldots\,a_m\,b_1\,b_2$ in $G$\, there exist two vertex-disjoint connected subgraphs $A$ and $B$ of $G$ such that $\{a_1\,\ldots\,a_m\}\subseteq V(A)$ and $\{b_1\,b_2\}\subseteq V(B)$. A related notion is $k$-linkedness: a graph is $k$-linked if\, for any distinct vertices $s_1\,\ldots\,s_k\,t_1\,\ldots\,t_k$\, it contains $k$ pairwise vertex-disjoint paths joining $s_i$ to $t_i$ for $i=1\,\ldots\,k$. \nA fundamental result in graph theory is the characterization of $2$-linked graphs\, obtained independently by Robertson and Chakravarti\, Seymour\, and Thomassen: $G$ does not contain disjoint paths joining $s_1$ to $t_1$ and $s_2$ to $t_2$ if and only if $G$ admits a certain “essentially planar” structure with $s_1\,s_2\,t_1\,t_2$ appearing on the outer boundary in this cyclic order. For $k$-linkedness and $(2\,m)$-linkedness with $k\,m\geq 3$\, comparable complete structural characterizations seem much more difficult. \nIn this talk\, I will present a full structural characterization of $(2\,3)$-linked graphs. This is joint work with Robin Thomas\, Shijie Xie\, and Xingxing Yu.
URL:https://dimag.ibs.re.kr/event/2026-10-27/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261117T163000
DTEND;TZID=Asia/Seoul:20261117T173000
DTSTAMP:20261012T112738Z
CREATED:20261012T112738Z
LAST-MODIFIED:20261012T112738Z
UID:13607-1794933000-1794936600@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, TBA
DESCRIPTION:TBA
URL:https://dimag.ibs.re.kr/event/2026-11-17/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261201T163000
DTEND;TZID=Asia/Seoul:20261201T173000
DTSTAMP:20261012T113621Z
CREATED:20261012T113621Z
LAST-MODIFIED:20261012T113621Z
UID:13611-1796142600-1796146200@dimag.ibs.re.kr
SUMMARY:William J. Wesley\, An elementary solution to the 2-color Pythagorean triples problem
DESCRIPTION:In the 1980s\, Ron Graham asked whether every red/blue coloring of the positive integers contains a monochromatic Pythagorean triple and offered a $100 prize for the answer. The bounty was claimed in 2016 by Heule\, Kullmann\, and Marek\, who showed that every such coloring of [1\,7825] has a monochromatic triple. Their proof used SAT solvers and took over 50\,000 CPU hours to produce and verify. In this talk we will present an elementary solution to Graham’s problem that requires neither deep analytic arguments nor extensive computation.
URL:https://dimag.ibs.re.kr/event/2026-12-01/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR