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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221109T163000
DTEND;TZID=Asia/Seoul:20221109T173000
DTSTAMP:20260418T223433
CREATED:20221015T061909Z
LAST-MODIFIED:20240705T171133Z
UID:6342-1668011400-1668015000@dimag.ibs.re.kr
SUMMARY:Hugo Jacob\, On the parameterized complexity of computing tree-partitions
DESCRIPTION:Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender\, Cornelissen\, and van der Wegen\, we consider the parameterized problem of computing a decomposition. We prove that computing an optimal tree-partition is XALP-complete\, which is likely to exclude FPT algorithms. However\, we prove that computing a tree-partition of approximate width is tractable using a relatively simple sketch. This is sufficient to remove the requirement of having a given tree-partition for FPT algorithms. Our simple sketch can be adapted for several regimes within polynomial time and FPT time. Furthermore\, we adapt some simple structural results about the tree-partition-width of subdivisions\, and use them to compare tree-cut width and tree-partition-width. \nBased on joint work with Hans Bodlaender and Carla Groenland.
URL:https://dimag.ibs.re.kr/event/2022-11-09/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221117T100000
DTEND;TZID=Asia/Seoul:20221117T110000
DTSTAMP:20260418T223433
CREATED:20221109T131844Z
LAST-MODIFIED:20240707T074503Z
UID:6462-1668679200-1668682800@dimag.ibs.re.kr
SUMMARY:Chong Shangguan (上官冲)\, On the sparse hypergraph problem of Brown\, Erdős and Sós
DESCRIPTION:For fixed integers $r\ge 3\, e\ge 3$\, and $v\ge r+1$\, let $f_r(n\,v\,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ distinct edges contains at least $v+1$ vertices. In 1973\, Brown\, Erdős and Sós initiated the study of the function $f_r(n\,v\,e)$ and they proved that $\Omega(n^{\frac{er-v}{e-1}})=f_r(n\,v\,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil})$. We will survey the state-of-art results about the study of $f_r(n\,er-(e-1)k+1\,e)$ and $f_r(n\,er-(e-1)k\,e)$\, where $r>k\ge 2$ and $e\ge 3$. Although these two functions have been extensively studied\, many interesting questions remain open.
URL:https://dimag.ibs.re.kr/event/2022-11-17/
LOCATION:Zoom ID: 224 221 2686 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR