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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200910T171000
DTEND;TZID=Asia/Seoul:20200910T181000
DTSTAMP:20260423T042220
CREATED:20200708T123031Z
LAST-MODIFIED:20240705T200015Z
UID:2619-1599757800-1599761400@dimag.ibs.re.kr
SUMMARY:Sebastian Siebertz\, Rank-width meets stability
DESCRIPTION:Forbidden graph characterizations provide a convenient way of specifying graph classes\, which often exhibit a rich combinatorial and algorithmic theory. A prime example in graph theory are classes of bounded tree-width\, which are characterized as those classes that exclude some planar graph as a minor. Similarly\, in model theory\, classes of structures are characterized by configurations that are forbidden as logical interpretations or transductions. Two notions from classical model theory are (monadic) stability and (monadic) dependence\, which correspond to the impossibility of interpreting with first-order logic (after a vertex coloring step) arbitrary long linear orders and all graphs\, respectively.  Examples of monadically stable classes of graphs are nowhere dense graph classes\, and examples of monadically dependent classes are classes of bounded rank-width (or equivalently\, bounded clique-width)\, which can be seen as a dense analog of classes of bounded tree-width. \nI will give an overview over recent approaches to combine model theoretic and graph theoretic tools to derive structural and algorithmic results for classes of (finite) graphs. I assume no background from logic.
URL:https://dimag.ibs.re.kr/event/2020-09-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200917T100000
DTEND;TZID=Asia/Seoul:20200917T110000
DTSTAMP:20260423T042220
CREATED:20200811T231948Z
LAST-MODIFIED:20240707T082734Z
UID:2789-1600336800-1600340400@dimag.ibs.re.kr
SUMMARY:Luke Postle\, Further progress towards Hadwiger's conjecture
DESCRIPTION:In 1943\, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s\, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable.  Recently\, Norin\, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$\, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^{\beta})$-colorable for every $\beta > 0$; more specifically\, they are $O(t (\log \log t)^{6})$-colorable.
URL:https://dimag.ibs.re.kr/event/2020-09-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200924T100000
DTEND;TZID=Asia/Seoul:20200924T110000
DTSTAMP:20260423T042220
CREATED:20200811T231744Z
LAST-MODIFIED:20240707T082720Z
UID:2781-1600941600-1600945200@dimag.ibs.re.kr
SUMMARY:Zihan Tan\, Towards Tight(er) Bounds for the Excluded Grid Theorem
DESCRIPTION:We study the Excluded Grid Theorem\, a fundamental structural result in graph theory\, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function $f$\, such that for every integer $g > 0$\, every graph of treewidth at least $f(g)$ contains the g×g-grid as a minor. For every integer $g > 0$\, let $f(g)$ be the smallest value for which the theorem holds. Establishing tight bounds on $f(g)$ is an important graph-theoretic question. Robertson and Seymour showed that f(g) is at least of order $g^2 \log g$. For a long time\, the best known upper bounds on $f(g)$ were super-exponential in $g$. The first polynomial upper bound of $f(g) = O(g^{98} \operatorname{poly log} g)$ was proved by Chekuri and Chuzhoy. It was later improved to $f(g) = O(g^{36} \operatorname{poly log} g)$\, and then to $f(g) = O(g^{19} \operatorname{poly log} g)$. In this talk\, we present our recent work that further improves this bound to $f(g) = O(g^9 \operatorname{poly log} g)$ via a simpler proof. Moreover\, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem\, it seems conceivable that the techniques proposed in this talk can lead to even tighter bounds on $f(g)$. \nThis talk is based on joint work with Julia Chuzhoy.
URL:https://dimag.ibs.re.kr/event/2020-09-24/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR