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:20200707T163000
DTEND;TZID=Asia/Seoul:20200707T173000
DTSTAMP:20260420T012910
CREATED:20200526T020628Z
LAST-MODIFIED:20240707T083806Z
UID:2481-1594139400-1594143000@dimag.ibs.re.kr
SUMMARY:Seog-Jin Kim (김석진)\, Online DP-coloring of graphs
DESCRIPTION:Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number\, $\chi_P(G)$\, (the minimum number of colors needed for an online coloring of $G$) and the DP-chromatic number\, $\chi_{DP}(G)$\, (the minimum number of colors needed for a DP-coloring of $G$) is at least the list chromatic number\, $\chi_\ell(G)$\, of $G$ and can be much larger. On the other hand\, each of them has a number of useful properties.\nWe introduce a common generalization\, online DP-coloring\, of online list coloring and DP-coloring and to study its properties. This is joint work with Alexandr Kostochka\, Xuer Li\, and Xuding Zhu.
URL:https://dimag.ibs.re.kr/event/2020-07-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200714T163000
DTEND;TZID=Asia/Seoul:20200714T173000
DTSTAMP:20260420T012910
CREATED:20200708T123817Z
LAST-MODIFIED:20240707T083801Z
UID:2622-1594744200-1594747800@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Inverse Turán Problems
DESCRIPTION:For given graphs $G$ and $F$\, the Turán number $ex(G\,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Briggs and Cox introduced a dual version of this problem wherein for a given number $k$\, one maximizes the number of edges in a host graph $G$ for which $ex(G\,H) < k$.  We resolve a problem of Briggs and Cox in the negative by showing that the inverse Turán number of $C_4$ is $\Theta(k^{3/2})$. More generally\, we determine the order of magnitude of the inverse Turán number of $K_{s\,t}$ for all $s$ and $t$.  Addressing another problem of Briggs and Cox\, we determine the asymptotic value of the inverse Turán number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length.  We also obtain improved bounds on the inverse Turán number of even cycles \nJoint work with Ervin Győri\, Nika Salia and Oscar Zamora.
URL:https://dimag.ibs.re.kr/event/2020-07-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200721T163000
DTEND;TZID=Asia/Seoul:20200721T173000
DTSTAMP:20260420T012910
CREATED:20200519T123058Z
LAST-MODIFIED:20240707T083754Z
UID:2456-1595349000-1595352600@dimag.ibs.re.kr
SUMMARY:Ilkyoo Choi (최일규)\, Flexibility of Planar Graphs
DESCRIPTION:Oftentimes in chromatic graph theory\, precoloring techniques are utilized in order to obtain the desired coloring result. For example\, Thomassen’s proof for 5-choosability of planar graphs actually shows that two adjacent vertices on the same face can be precolored. In this vein\, we investigate a precoloring extension problem formalized by Dvorak\, Norin\, and Postle named flexibility. Given a list assignment $L$ on a graph $G$\, an $L$-request is a function on a subset $S$ of the vertices that indicates a preferred color in $L(v)$ for each vertex $v\in S$. A graph $G$ is $\varepsilon$-flexible for list size $k$ if given a $k$-list assignment $L$ and an $L$-request\, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. We survey known results regarding this new concept\, and prove some new results regarding flexibility of planar graphs.
URL:https://dimag.ibs.re.kr/event/2020-07-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200728T163000
DTEND;TZID=Asia/Seoul:20200728T173000
DTSTAMP:20260420T012910
CREATED:20200708T123952Z
LAST-MODIFIED:20240707T083742Z
UID:2624-1595953800-1595957400@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, Solving hard cut problems via flow-augmentation
DESCRIPTION:We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs\, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s\, t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals s and t. \nMore precisely\, we consider problems where an (unknown) solution is a set $Z \subseteq E(G)$ of size at most $k$ such that \n\nin $G−Z$\, $s$ and $t$ are indistinct connected components\,\nevery edge of $Z$ connects two distinct connected components of $G − Z$\, and\nif we define the set $Z_{s\,t}\subseteq Z$ as these edges $e \in Z$ for which there exists an (s\, t)-path P_e with $E(P_e) ∩ Z = \{e\}$\, then $Z_{s\,t}$ separates s from t.\n\nWe prove that in the above scenario one can in randomized time $k^O(1)(|V (G)| + |E(G)|)$ add a number of edges to the graph so that with $2^{O(k \log k)}$ probability no added edge connects two components of $G − Z$ and $Z_{s\,t}$ becomes a minimum cut between $s$ and $t$. \nThis additional property becomes a handy lever in applications. For example\, consider the question of an $(s\, t)$-cut of cardinality at most k and of minimum possible weight (assuming edge weights in $G$). While the problem is NP-hard in general\, it easily reduces to the maximum flow / minimum cut problem if we additionally assume that k is the minimum possible cardinality an $(s\, t)$-cut in G. Hence\, we immediately obtain that the aforementioned problem admits an $2^{O(k \log k)}n^O(1)$-time randomized fixed-parameter algorithm. \nWe apply our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems (see below)\, and was unamenable to other techniques for parameterized algorithms in graph cut problems\, such as Randomized Contractions\, Treewidth Reduction or Shadow Removal. \nIn fact\, we go one step further. To demonstrate the power of the approach\, we consider more generally the Boolean Min CSP(Γ)-problems\, a.k.a. Min SAT(Γ)\, parameterized by the solution cost. This is a framework of optimization problems that includes problems such as Almost 2-SAT and the notorious l-Chain SAT problem. We are able to show that every problem Min SAT(Γ) is either (1) FPT\, (2) W[1]-hard\, or (3) able to express the soft constraint (u → v)\, and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate\, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut. In other words\, flow-augmentation is powerful enough to let us solve every fixed-parameter tractable problem in the class\, except those that explicitly encompass directed graph cuts. \nThis is a joint work with Stefan Kratsch\, Marcin Pilipczuk and Magnus Wahlström.
URL:https://dimag.ibs.re.kr/event/2020-07-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR