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;TZID=Asia/Seoul:20250701T163000
DTEND;TZID=Asia/Seoul:20250701T173000
DTSTAMP:20260416T162153
CREATED:20250324T010911Z
LAST-MODIFIED:20250610T150051Z
UID:10713-1751387400-1751391000@dimag.ibs.re.kr
SUMMARY:Sergey Norin\, Asymptotic dimension of intersection graphs
DESCRIPTION:The notion of asymptotic dimension of metric spaces\, introduced by Gromov\, describes their large-scale behaviour. Asymptotic dimension of graph families has been recently studied\, in particular\, by Bonamy et al. who proved that the asymptotic dimension of proper minor-closed graph families is at most two. \nWe will discuss nerve-type theorems for asymptotic dimension. In particular\, we show that the asymptotic dimension of intersection graphs of balls and spheres in $\mathbb{R}^d$ is at most $d+1$. \nBased on joint work with Zdeněk Dvořák and with Chun-Hung Liu.
URL:https://dimag.ibs.re.kr/event/2025-07-01/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250708T163000
DTEND;TZID=Asia/Seoul:20250708T173000
DTSTAMP:20260416T162153
CREATED:20250117T144850Z
LAST-MODIFIED:20250625T140926Z
UID:10409-1751992200-1751995800@dimag.ibs.re.kr
SUMMARY:Mihyun Kang (강미현)\, Phase transitions in a random subgraph of the hypercube
DESCRIPTION:We will discuss classical and recent results about phase transitions in random subgraphs of the hypercube and beyond. The focus will be on the giant component\, long cycles\, large matchings\, and isoperimetric properties.
URL:https://dimag.ibs.re.kr/event/2025-07-08/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250714T140000
DTEND;TZID=Asia/Seoul:20250718T170000
DTSTAMP:20260416T162153
CREATED:20250421T055000Z
LAST-MODIFIED:20250706T061119Z
UID:10816-1752501600-1752858000@dimag.ibs.re.kr
SUMMARY:2025 Summer School on Combinatorics and Algorithms (2025 조합론 및 알고리즘 여름학교)
DESCRIPTION:The 2025 Summer School on Combinatorics and Algorithms is a venue for students and early-career researchers to learn selected topics in theoretical computer science and discrete mathematics. It will be a great opportunity for young and aspiring researchers to study topics which are important but not covered during the lectures in the university classes. \nWebsite: https://combialgo.dimag.kr/ \nLecturers and Topics\n\nÉdouard Bonnet\, LIP\, CNRS.\n\nInduced Subgraphs and Induced Minors of Graphs\n\n\nMichał Pilipczuk\, University of Warsaw.\n\nStructural Theory of Sparse Graphs\n\n\n\nSchedule\n\nStart on 14 July 2025 Monday\, 2 PM\nEnd on 18 July 2025 Friday\, 5 PM
URL:https://dimag.ibs.re.kr/event/2025-07-14/
LOCATION:POSTECH\, Pohang\, Korea
CATEGORIES:Workshops and Conferences
ORGANIZER;CN="Eunjung Kim (%EA%B9%80%EC%9D%80%EC%A0%95)":MAILTO:eunjungkim78@gmail.com
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250722T163000
DTEND;TZID=Asia/Seoul:20250722T173000
DTSTAMP:20260416T162153
CREATED:20250610T134044Z
LAST-MODIFIED:20250611T222217Z
UID:10983-1753201800-1753205400@dimag.ibs.re.kr
SUMMARY:Linda Cook\, A tight algorithmic meta-theorem for distributed certification within bounded treewidth graphs
DESCRIPTION:A local certification of a graph property is a protocol in which nodes are given  “certificates of a graph property” that allow the nodes to check whether their network has this property while only communicating with their local network. The key property of a local certification is that if certificates are corrupted\, some node in the network will be able to recognize this. Inspired by practical concerns\, the aim in LOCAL certification is to minimize the maximum size of a certificate. \nIn this talk we introduce local certification and open problems in the area and  present some recent joint work with Eunjung Kim and Tomáš Masařík\, A Tight Meta-theorem for LOCAL Certification of MSO2 Properties within Bounded Treewidth Graphs. \nIn this work\, instead of considering a specific graph property and developing a local certification protocol tailor-made for this property\, we aim for generic protocols that can certify any property expressible in a certain logical framework. We consider Monadic Second Order Logic (MSO$_2$)\, a powerful framework that can express properties such as non-$k$-colorability\, Hamiltonicity\, and $H$-minor-freeness. Unfortunately\, in general\, there are MSO$_2$-expressible properties that cannot be certified without huge certificates. For instance\, non-3-colorability requires certificates of size $\Omega(n^2/\log n)$ on general $n$-vertex graphs (Göös\, Suomela 2016). Hence\, we impose additional structural restrictions on the graph. Inspired by their importance in centralized computing and Robertson-Seymour Graph Minor theory\, we consider graphs of bounded treewidth. We provide a local certification protocol for certifying any MSO$_2$-expressible property on graphs of bounded treewidth and\, consequently\, a local certification protocol for certifying bounded treewidth. That is\, for each integer $k$ and each MSO$_2$-expressible property $\Pi$\, we give a local certification protocol to certify that a graph satisfies $\Pi$ and has treewidth at most $k$ using certificates of size $\mathcal{O}(\log n)$ (which is asymptotically optimal). Our result improves upon the works of Fraigniaud\, Montealegre\, Rapaport\, and Todinca (Algorithmica 2024)\,  Bousquet\, Feuilloley\, Pierron (PODC 2022)\, and the very recent work of Baterisna and Chang (PODC 2025).
URL:https://dimag.ibs.re.kr/event/2025-07-22/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250729T163000
DTEND;TZID=Asia/Seoul:20250729T173000
DTSTAMP:20260416T162153
CREATED:20250706T060914Z
LAST-MODIFIED:20250707T012610Z
UID:11110-1753806600-1753810200@dimag.ibs.re.kr
SUMMARY:Colin Geniet\, Merge-width
DESCRIPTION:This talk is an introduction to the recent notion of merge-width\, proposed by Jan Dreier and Szymon Torúnczyk. I will give an overview of the context and motivations for merge-width\, namely the first-order model checking problem\, and present the definition\, some examples\, and some basic proof techniques with the example of χ-boundedness.\nThis is based on joint work with Marthe Bonamy.
URL:https://dimag.ibs.re.kr/event/2025-07-29/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR