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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230201T163000
DTEND;TZID=Asia/Seoul:20230201T173000
DTSTAMP:20260419T131246
CREATED:20230115T151551Z
LAST-MODIFIED:20240705T170041Z
UID:6664-1675269000-1675272600@dimag.ibs.re.kr
SUMMARY:Benjamin Bergougnoux\, Tight Lower Bounds for Problems Parameterized by Rank-width
DESCRIPTION:We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$\, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)} n^{O(1)}$ time algorithm given by Bui-Xuan\, Telle\, and Vatshelle [Discret. Appl. Math.\, 2010] and it answers the open question of Bergougnoux and Kanté [SIAM J. Discret. Math.\, 2021]. We also show that the known $2^{O(k^2)} n^{O(1)}$ time algorithms for Weighted Dominating Set\, Maximum Induced Matching and Feedback Vertex Set parameterized by rank-width $k$ are optimal assuming ETH. Our results are the first tight ETH lower bounds parameterized by rank-width that do not follow directly from lower bounds for $n$-vertex graphs. \nThis is a joint work with Tuukka Korhonen and Jesper Nederlof.\nAccepted to STACS 2023 and available on arXiv https://arxiv.org/abs/2210.02117
URL:https://dimag.ibs.re.kr/event/2023-02-01/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230214T163000
DTEND;TZID=Asia/Seoul:20230214T173000
DTSTAMP:20260419T131246
CREATED:20221122T113208Z
LAST-MODIFIED:20240705T171025Z
UID:6504-1676392200-1676395800@dimag.ibs.re.kr
SUMMARY:Raphael Steiner\, Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
DESCRIPTION:Hadwiger’s famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd [Bull. London Math. Soc. 29\, (1997)\, pp. 139-144] conjectured the following strengthening of Hadwiger’s conjecture: If G is a t-chromatic graph and S⊆V(G) takes all colors in every t-coloring of G\, then G contains a $K_t$-minor rooted at S. We prove this conjecture in the first open case of t=4. Notably\, our result also directly implies a stronger version of Hadwiger’s conjecture for 5-chromatic graphs as follows: Every 5-chromatic graph contains a $K_5$-minor with a singleton branch-set. In fact\, in a 5-vertex-critical graph we may specify the singleton branch-set to be any vertex of the graph. Joint work with Anders Martinsson (ETH).
URL:https://dimag.ibs.re.kr/event/2023-02-14/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230215T163000
DTEND;TZID=Asia/Seoul:20230215T173000
DTSTAMP:20260419T131246
CREATED:20230103T235641Z
LAST-MODIFIED:20240705T170041Z
UID:6623-1676478600-1676482200@dimag.ibs.re.kr
SUMMARY:Robert Hickingbotham\, Treewidth\, Circle Graphs and Circular Drawings
DESCRIPTION:A circle graph is an intersection graph of a set of chords of a circle. In this talk\, I will describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects’. Our results imply that treewidth and Hadwiger number are linearly tied on the class of circle graphs\, and that the unavoidable induced subgraphs of a vertex-minor-closed class with large treewidth are the usual suspects if and only if the class has bounded rank-width. I will also discuss applications of our results to the treewidth of graphs $G$ that have a circular drawing whose crossing graph is well-behaved in some way. In this setting\, our results show that if the crossing graph is $K_t$-minor-free\, then $G$ has treewidth at most $12t-23$ and has no $K_{2\,4t}$-topological minor. On the other hand\, I’ll present a construction of graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are $2$-degenerate. This is joint work with Freddie Illingworth\, Bojan Mohar\, and David R. Wood
URL:https://dimag.ibs.re.kr/event/2023-02-15/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230221T163000
DTEND;TZID=Asia/Seoul:20230221T173000
DTSTAMP:20260419T131246
CREATED:20230110T061742Z
LAST-MODIFIED:20240705T170041Z
UID:6636-1676997000-1677000600@dimag.ibs.re.kr
SUMMARY:Meike Hatzel\, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation
DESCRIPTION:We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem\, given a directed graph $G$\, pairs of vertices (called terminals) $(s_1\,t_1)$\, $(s_2\,t_2)$\, and $(s_3\,t_3)$\, and an integer $k$\, asks to find a set of at most $k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths\, all $s_2t_2$-paths\, and all $s_3t_3$-paths. The parameterized complexity of this case has been open since Chitnis\, Cygan\, Hajiaghayi\, and Marx proved fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012\, and Pilipczuk and Wahlström proved the W[1]-hardness of the 4-terminal-pairs case at SODA 2016. \nOn the technical side\, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim\, Kratsch\, Pilipczuk\, Wahlström\, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain. We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width\, a recently introduced structural parameter [Bonnet\, Kim\, Thomassé\, Watrigant\, FOCS 2020]: By a recent characterization [Bonnet\, Giocanti\, Ossona de Mendez\, Simon\, Thomassé\, Toruńczyk\, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof\, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor\, a vertex corresponding to the “middle” box in the grid minor can be proclaimed irrelevant — not contained in the sought solution — and thus reduced.
URL:https://dimag.ibs.re.kr/event/2023-02-21/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230222T170000
DTEND;TZID=Asia/Seoul:20230222T180000
DTSTAMP:20260419T131246
CREATED:20221115T011207Z
LAST-MODIFIED:20240707T074027Z
UID:6483-1677085200-1677088800@dimag.ibs.re.kr
SUMMARY:Daniel Altman\, On an arithmetic Sidorenko conjecture\, and a question of Alon
DESCRIPTION:Let $G=\mathbb{F}_p^n$. Which systems of linear equations $\Psi$ have the property that amongst all subsets of $G$ of fixed density\, random subsets minimise the number of solutions to $\Psi$? This is an arithmetic analogue of a well-known conjecture of Sidorenko in graph theory\, which has remained open and of great interest since the 1980s. We will discuss some recent results along these lines\, with particular focus on some of the ideas behind a negative answer to a related question of Alon.
URL:https://dimag.ibs.re.kr/event/2023-02-22/
LOCATION:Zoom ID: 224 221 2686 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230228T163000
DTEND;TZID=Asia/Seoul:20230228T173000
DTSTAMP:20260419T131246
CREATED:20230213T001557Z
LAST-MODIFIED:20240707T074017Z
UID:6782-1677601800-1677605400@dimag.ibs.re.kr
SUMMARY:Maya Sankar\, The Turán Numbers of Homeomorphs
DESCRIPTION:Let $X$ be a 2-dimensional simplicial complex. Denote by $\text{ex}_{\hom}(n\,X)$ the maximum number of 2-simplices in an $n$-vertex simplicial complex that has no sub-simplicial complex homeomorphic to $X$. The asymptotics of $\text{ex}_{\hom}(n\,X)$ have recently been determined for all surfaces $X$. I will discuss these results\, as well as ongoing work bounding $\text{ex}_{\hom}(n\,X)$ for arbitrary 2-dimensional simplicial complexes $X$.
URL:https://dimag.ibs.re.kr/event/2023-02-28/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR