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:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190103T160000
DTEND;TZID=Asia/Seoul:20190103T170000
DTSTAMP:20260423T173405
CREATED:20181224T085518Z
LAST-MODIFIED:20240707T090650Z
UID:305-1546531200-1546534800@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, Sidorenko’s conjecture for blow-ups
DESCRIPTION:A celebrated conjecture of Sidorenko and Erdős–Simonovits states that\, for all bipartite graphs H\, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs\, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion. \nOur contribution here\, which goes beyond this paradigm\, is to show that the conjecture holds for any bipartite graph H with bipartition A∪B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary\, we have that for every bipartite graph H with bipartition A∪B\, there is a positive integer p such that the blow-up HAp formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Joint work with David Conlon.
URL:https://dimag.ibs.re.kr/event/2019-01-03/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190104T160000
DTEND;TZID=Asia/Seoul:20190104T170000
DTSTAMP:20260423T173405
CREATED:20181217T143613Z
LAST-MODIFIED:20240705T211439Z
UID:279-1546617600-1546621200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, New algorithm for multiway cut guided by strong min-max duality
DESCRIPTION:Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then\, LP-guided branching has been studied in depth and established as a powerful technique for parameterized algorithms design. \nIn this talk\, we make a brief overview of LP-guided branching technique and introduce the latest results whose parameterization is above even stronger lower bounds\, namely μ(I)=2LP(I)-IP(dual-I). Here\, LP(I) is the value of an optimal fractional solution and IP(dual-I) is the value of an optimal integral dual solution. Tutte-Berge formula for Maximum Matching (or equivalently Edmonds-Gallai decomposition) and its generalization Mader’s min-max formula are exploited to this end. As a result\, we obtain an algorithm running in time 4k-μ(I) for multiway cut and its generalizations\, where k is the budget for a solution. \nThis talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.
URL:https://dimag.ibs.re.kr/event/2019-01-04/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190128T160000
DTEND;TZID=Asia/Seoul:20190128T170000
DTSTAMP:20260423T173405
CREATED:20190102T015548Z
LAST-MODIFIED:20240705T211438Z
UID:348-1548691200-1548694800@dimag.ibs.re.kr
SUMMARY:Seog-Jin Kim (김석진)\, Signed colouring and list colouring of  k-chromatic graphs
DESCRIPTION:A signed graph is a pair (G\, σ)\, where G is a graph and σ: E(G) → {1\,-1} is a signature of G. A set S of integers is symmetric if I∈S implies that -i∈S. A k-colouring of (G\,σ) is a mapping f:V(G) → Nk such that for each edge e=uv\, f(x)≠σ(e) f(y)\, where Nk is a symmetric integer set of size k. We define the signed chromatic number of a graph G to be the minimum integer k such that for any signature σ of G\, (G\, σ) has a k-colouring. \nLet f(n\,k) be the maximum signed chromatic number of an n-vertex k-chromatic graph. This paper determines the value of f(n\,k) for all positive integers n ≥ k. Then we study list colouring of signed graphs. A list assignment L of G is called symmetric if L(v) is a symmetric integer set for each vertex v. The weak signed choice number ch±w(G) of a graph G is defined to be the minimum integer k such that for any symmetric k-list assignment L of G\, for any signature σ on G\, there is a proper L-colouring of (G\, σ). We prove that the difference ch±w(G)-χ±(G) can be arbitrarily large. On the other hand\, ch±w(G) is bounded from above by twice the list vertex arboricity of G. Using this result\, we prove that ch±w(K2⋆n)= χ±(K2⋆n) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.
URL:https://dimag.ibs.re.kr/event/2019-01-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR