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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20200508
DTEND;VALUE=DATE:20200510
DTSTAMP:20260424T113850
CREATED:20200221T012551Z
LAST-MODIFIED:20240705T201209Z
UID:2142-1588896000-1589068799@dimag.ibs.re.kr
SUMMARY:KSIAM 2020 Spring Conference (cancelled)
DESCRIPTION:KSIAM 2020 Spring Conference will be held at IBS from May 8\, 2020 to May 9\, 2020. \nOrganized by Korean Society for Industrial and Applied Mathematics. \nOrganizing Committee\n\nMyungjoo Kang (Seoul National University) (chair)\nAhn\, Jaemyung (KAIST)\nKwon\, Hee-Dae (Inha University)\nLee\, Eun Jung (Yonsei University)\nJang\, Bongsoo (UNIST)\nJung\, Miyoun (Hankuk University of Foreign Studies)\nKim\, Junseok (Korea University)\nOum\, Sang-il (IBS\, KAIST)
URL:https://dimag.ibs.re.kr/event/ksiam-2020-spring-conference/
LOCATION:IBS Science Culture Center
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200512T163000
DTEND;TZID=Asia/Seoul:20200512T173000
DTSTAMP:20260424T113850
CREATED:20200417T054420Z
LAST-MODIFIED:20240707T084008Z
UID:2354-1589301000-1589304600@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, Twin-width: tractable FO model checking
DESCRIPTION:Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA ’14]\, we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes\, bounded rank-width graphs\, map graphs\, $K_t$-free unit $d$-dimensional ball graphs\, posets with antichains of bounded size\, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of $d$-contractions\, witness that the twin-width is at most $d$. We show that FO model checking\, that is deciding if a given first-order formula $\phi$ evaluates to true for a given binary structure $G$ on a domain $D$\, is FPT in $|\phi|$ on classes of bounded twin-width\, provided the witness is given. More precisely\, being given a $d$-contraction sequence for $G$\, our algorithm runs in time $f(d\,|\phi|) \cdot |D|$ where $f$ is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes\, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS ’15]. \nIn order to explore the limits of twin-width\, we generalize to bounded twin-width classes a result by Norine et al. [JCTB ’06] stating that proper minor-free classes are small (i.e.\, they contain at most $n! c^n$ graphs on $n$ vertices\, for some constant $c$). This implies by a counting argument that bounded-degree graphs\, interval graphs\, and unit disk graphs have unbounded twin-width. \nJoint work with Stéphan Thomassé\, Édouard Bonnet\, and Rémi Watrigant.
URL:https://dimag.ibs.re.kr/event/2020-05-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200519T163000
DTEND;TZID=Asia/Seoul:20200519T173000
DTSTAMP:20260424T113850
CREATED:20200422T003736Z
LAST-MODIFIED:20240705T201022Z
UID:2383-1589905800-1589909400@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\,  Mim-width: a width parameter beyond rank-width
DESCRIPTION:Vatshelle (2012) introduced a width parameter called mim-width. It is based on the following cut function : for a vertex partition (A\,B) of a graph\, the complexity of this partition is computed by the size of a maximum induced matching of the bipartite subgraph induced by edges between A and B. This parameter naturally extends the expressibility power of the graph parameters clique-width and rank-width\, which have been well-developed in recent years. In a series of papers\, we explored the computational complexity of several problems\, parameterized by mim-width. We summarize known structural properties and algorithmic applications of mim-width\, and give some open problems at the end. This is joint work with Lars Jaffke\, Torstein Strømme\, and Jan Arne Telle.
URL:https://dimag.ibs.re.kr/event/2020-05-19/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200526T163000
DTEND;TZID=Asia/Seoul:20200526T173000
DTSTAMP:20260424T113850
CREATED:20200507T062724Z
LAST-MODIFIED:20240705T201016Z
UID:2430-1590510600-1590514200@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Asymptotic Structure for the Clique Density Theorem
DESCRIPTION:The famous Erdős-Rademacher problem asks for the smallest number of r-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts\, the asymptotic value of this extremal function for all r was determined only recently\, by Reiher [Annals of Mathematics\, 184 (2016) 683-707]. Here we describe the asymptotic structure of all almost extremal graphs. This task for r=3 was previously accomplished by Pikhurko and Razborov [Combinatorics\, Probability and Computing\, 26 (2017) 138–160].
URL:https://dimag.ibs.re.kr/event/2020-05-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR