BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv5.8.1//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
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:20210810T163000
DTEND;TZID=Asia/Seoul:20210810T173000
DTSTAMP:20210729T232118
CREATED:20210817T073000Z
LAST-MODIFIED:20210729T012338Z
UID:4408-1628613000-1628616600@dimag.ibs.re.kr
SUMMARY:Duksang Lee (이덕상)\, Intertwining connectivities for vertex-minors and pivot-minors
DESCRIPTION:We show that for pairs (Q\,R) and (S\,T) of disjoint subsets of vertices of a graph G\, if G is sufficiently large\, then there exists a vertex v in V(G)−(Q∪R∪S∪T) such that there are two ways to reduce G by a vertex-minor operation while preserving the connectivity between Q and R and the connectivity between S and T. Our theorem implies an analogous theorem of Chen and Whittle (2014) for matroids restricted to binary matroids. Joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-08-10/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210817T163000
DTEND;TZID=Asia/Seoul:20210817T173000
DTSTAMP:20210729T232118
CREATED:20210817T073000Z
LAST-MODIFIED:20210721T004402Z
UID:4242-1629217800-1629221400@dimag.ibs.re.kr
SUMMARY:Linda Cook\, Two results on graphs with holes of restricted lengths
DESCRIPTION:We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006\, Chudnovksy\, Seymour\, Robertson\, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc provided a structural description of the class of even-hole-free graphs. I will describe the structure of all graphs that contain only holes of length $\ell$ for every $\ell \geq 7$ (joint work with Jake Horsfield\, Myriam Preissmann\, Paul Seymour\, Ni Luh Dewi Sintiari\, Cléophée Robin\, Nicolas Trotignon\, and Kristina Vuškovíc. \nAnalysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities. In 1991\, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex $v \in V(G)$. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2003\, Chudnovsky\, Kawarabayashi\, and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019\, Chudnovsky\, Scott\, Seymour\, and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year\, Chudnovsky\, Scott\, and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least $\ell$ for any fixed integer $\ell \geq 5$. I will present a polynomial-time algorithm (joint work with Paul Seymour) to test whether a graph contains an even hole of length at least $\ell$ for any fixed integer $\ell \geq 4$.
URL:https://dimag.ibs.re.kr/event/2021-08-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210818T170000
DTEND;TZID=Asia/Seoul:20210818T180000
DTSTAMP:20210729T232118
CREATED:20210708T124002Z
LAST-MODIFIED:20210708T124002Z
UID:4353-1629306000-1629309600@dimag.ibs.re.kr
SUMMARY:Petr Hliněný\, Twin-width is linear in the poset width
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2021-08-18/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210824T163000
DTEND;TZID=Asia/Seoul:20210824T173000
DTSTAMP:20210729T232118
CREATED:20210810T073000Z
LAST-MODIFIED:20210729T012314Z
UID:4212-1629822600-1629826200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, A Constant-factor Approximation for Weighted Bond Cover
DESCRIPTION:The Weighted $\mathcal F$-Vertex Deletion for a class $\mathcal F$ of graphs asks\, given a weighted graph $G$\, for a minimum weight vertex set $S$ such that $G-S\in\mathcal F$. The case when $\mathcal F$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal F$-Vertex Deletion. Only three cases of minor-closed $\mathcal F$ are known to admit constant-factor approximations\, namely Vertex Cover\, Feedback Vertex Set and Diamond Hitting Set. \nWe study the problem for the class $\mathcal F$ of $\theta_c$-minor-free graphs\, under the equivalent setting of the Weighted c-Bond Cover\, and present a constant-factor approximation algorithm using the primal-dual method. For this\, we leverage a structure theorem implicit in [Joret et al.\, SIDMA’14] which states the following: any graph $G$ containing a $\theta_c$-minor-model either contains a large two-terminal protrusion\, or contains a constant-size $\theta_c$-minor-model\, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case\, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case\, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted $\mathcal F$-Vertex Deletion\, our result may be useful as a template for algorithms for other minor-closed families. \nThis is joint work with Euiwoong Lee and Dimitrios M. Thilikos.
URL:https://dimag.ibs.re.kr/event/2021-08-24/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210831T163000
DTEND;TZID=Asia/Seoul:20210831T173000
DTSTAMP:20210729T232118
CREATED:20210803T073000Z
LAST-MODIFIED:20210726T060457Z
UID:4198-1630427400-1630431000@dimag.ibs.re.kr
SUMMARY:Ilkyoo Choi (최일규)\, On independent domination of regular graphs
DESCRIPTION:Given a graph $G$\, a dominating set of $G$ is a set $S$ of vertices such that each vertex not in $S$ has a neighbor in $S$. The domination number of $G$\, denoted $\gamma(G)$\, is the minimum size of a dominating set of $G$. The independent domination number of $G$\, denoted $i(G)$\, is the minimum size of a dominating set of $G$ that is also independent. Note that every graph has an independent dominating set\, as a maximal independent set is equivalent to an independent dominating set. \nLet $G$ be a connected $k$-regular graph that is not $K_{k\, k}$ where $k\geq 4$. Generalizing a result by Lam\, Shiu\, and Sun\, we prove that $i(G)\le \frac{k-1}{2k-1}|V(G)|$\, which is tight for $k = 4$. This answers a question by Goddard et al. in the affirmative. We also show that $\frac{i(G)}{\gamma(G)} \le \frac{k^3-3k^2+2}{2k^2-6k+2}$\, strengthening upon a result of Knor\, Škrekovski\, and Tepeh. In addition\, we prove that a graph $G’$ with maximum degree at most $4$ satisfies $i(G’) \le \frac{5}{9}|V(G’)|$\, which is also tight.
URL:https://dimag.ibs.re.kr/event/2021-08-31/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210907T163000
DTEND;TZID=Asia/Seoul:20210907T173000
DTSTAMP:20210729T232118
CREATED:20210528T073901Z
LAST-MODIFIED:20210614T234103Z
UID:4140-1631032200-1631035800@dimag.ibs.re.kr
SUMMARY:Sang-hyun Kim (김상현)\, On rational 2x2 matrices without relations
DESCRIPTION:For a rational number $q= s/r$\, we consider the two 2×2 matrices $A=\begin{pmatrix}1&0\\1&1\end{pmatrix}$ and $B_q=\begin{pmatrix}1&q\\0&1\end{pmatrix}$. It is a long-standing conjecture (traced at least back to Rimhak Ree) that A and B(q) admit a nontrivial group relation if $|q|<4$; the converse is classical. For the special case $s≤27$ and $s\neq 24$\, we prove this conjecture. We give a lower bound estimate of the natural density for all the other values of s. (Joint with Thomas Koberda)
URL:https://dimag.ibs.re.kr/event/2021-09-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210914T163000
DTEND;TZID=Asia/Seoul:20210914T173000
DTSTAMP:20210729T232118
CREATED:20210705T020319Z
LAST-MODIFIED:20210707T232258Z
UID:4341-1631637000-1631640600@dimag.ibs.re.kr
SUMMARY:Cheolwon Heo (허철원)\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2021-09-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211012T043000
DTEND;TZID=Asia/Seoul:20211012T173000
DTSTAMP:20210729T232118
CREATED:20210714T230923Z
LAST-MODIFIED:20210716T014801Z
UID:4374-1634013000-1634059800@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2021-10-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR