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;TZID=Asia/Seoul:20200303T163000
DTEND;TZID=Asia/Seoul:20200303T173000
DTSTAMP:20260420T081800
CREATED:20200207T093644Z
LAST-MODIFIED:20240707T091837Z
UID:2099-1583253000-1583256600@dimag.ibs.re.kr
SUMMARY:Eun-Kyung Cho (조은경)\, Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$
DESCRIPTION:Given a graph $G$\, a decomposition of $G$ is a collection of spanning subgraphs $H_1\, \ldots\, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ for exactly one $i \in \{1\, \ldots\, t\}$. Given a positive integer $d$\, a graph is said to be $d$-degenerate if every subgraph of it has a vertex of degree at most $d$. Given a non-negative integer $h$\, we say that a graph $G$ is $(d\,h)$-decomposable if there is a decomposition of $G$ into two spanning subgraphs\, where one is a $d$-degenerate graph\, and the other is a graph with maximum degree at most $h$. \nIt is known that a planar graph is $5$-degenerate\, but not always $4$-degenerate. This implies that a planar graph is $(5\,0)$-decomposable\, but not always $(4\,0)$-decomposable. Moreover\, by related previous results\, it is known that a planar graph is $(3\,4)$- and $(2\,8)$-decomposable. \nIn this talk\, we improve these results by showing that every planar graph is $(4\,1)$-\, $(3\,2)$-\, and $(2\,6)$-decomposable. The $(4\,1)$- and $(3\,2)$-decomposabilities are sharp in the sense that the maximum degree condition cannot be reduced more. \nThis is joint work with Ilkyoo Choi\, Ringi Kim\, Boram Park\, Tingting Shan\, and Xuding Zhu.
URL:https://dimag.ibs.re.kr/event/2020-03-03/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200317T163000
DTEND;TZID=Asia/Seoul:20200317T173000
DTSTAMP:20260420T081800
CREATED:20200307T133007Z
LAST-MODIFIED:20240705T201209Z
UID:2180-1584462600-1584466200@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, On a generalization of the Chvátal-Gomory closure
DESCRIPTION:Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called “cutting-plane” algorithm in combination with branch-and-bound enumeration. Cutting-planes for an integer linear program are linear inequalities that are valid for all integer feasible solutions but cut off intermediate fractional solutions. \nThe Chvátal-Gomory cuts\, introduced by Gomory in 1958 and further studied by Chvátal in 1973 in relation to their applications in combinatorial optimization\, are the first class of general-purpose cutting-planes in the literature. The split cuts\, whose name was coined by Cook\, Kannan\, and Schrijver in 1980\, are another class of important cutting-planes in modern integer programming. Although there are infinitely many cuts in each class\, it is known that only finitely many of them are nonredundant\, which is related to designing a finite-convergent cutting-plane algorithm. In this talk\, we introduce a new class of cutting-planes that generalizes the Chvátal-Gomory cuts and generalizes a special case of the split cuts. As the two classic classes of cutting-planes\, we show that only a finite number of cuts can be redundant. \nThis talk is based on a joint work with Sanjeeb Dash and Oktay Günlük.
URL:https://dimag.ibs.re.kr/event/2020-03-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200324T163000
DTEND;TZID=Asia/Seoul:20200324T173000
DTSTAMP:20260420T081800
CREATED:20200311T074415Z
LAST-MODIFIED:20240707T084154Z
UID:2186-1585067400-1585071000@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, Covering radius in the Hamming permutation space
DESCRIPTION:Our problem can be described in terms of a two player game\, played with the set $\mathcal{S}_n$ of permutations on $\{1\,2\,\dots\,n\}$. First\, Player 1 selects a subset $S$ of $\mathcal{S}_n$ and shows it to Player 2. Next\, Player 2 selects a permutation $p$ from $\mathcal{S}_n$ as different as possible from the permutations in $S$\, and shows it to Player 1. Finally\, Player 1 selects a permutation $q$ from $S$\, and they compare $p$ and $q$. The aim of Player 1 is to ensure that $p$ and $q$ differ in few positions\, while keeping the size of $S$ small. The function $f(n\,s)$ can be defined as the minimum size of a set $S\subseteq \mathcal{S}_n$ that Player 1 can select in order to gaurantee that $p$ and $q$ will differ in at most $s$ positions. \nI will present some recent results on the function $f(n\,s)$. We are particularly interested in determining the value $f(n\,2)$\, which would resolve a conjecture of Kézdy and Snevily that implies several famous conjectures for Latin squares. Here we improve the best known lower bound\, showing that $f(n\,2)\geqslant 3n/4$. This talk is based on joint work with Ian M. Wanless.
URL:https://dimag.ibs.re.kr/event/2020-03-24/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200331T163000
DTEND;TZID=Asia/Seoul:20200331T173000
DTSTAMP:20260420T081800
CREATED:20200324T132402Z
LAST-MODIFIED:20240707T084146Z
UID:2222-1585672200-1585675800@dimag.ibs.re.kr
SUMMARY:Ringi Kim (김린기)\, The strong clique number of graphs with forbidden cycles
DESCRIPTION:The strong clique number of a graph $G$ is the maximum size of a set of edges of which every pair has distance at most two. \nIn this talk\, we prove that every  $\{C_5\,C_{2k}\}$-free graph has strong clique number at most $k\Delta(G)-(k-1)$\, which resolves a conjecture by  Cames van Batenburg et al. We also prove that every $C_{2k}$-free graph has strong clique number at most $(2k−1)\Delta(G) + (2k−1)^2$\, improving the previous known upper bound $10k^2 (\Delta(G)-1)$ due to  Cames van Batenburg et al. This is joint work with Eun-Kyung Cho\, Ilkyoo Choi\, and Boram Park.
URL:https://dimag.ibs.re.kr/event/2020-03-31/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR