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:20230103T163000
DTEND;TZID=Asia/Seoul:20230103T173000
DTSTAMP:20260419T150714
CREATED:20221010T054006Z
LAST-MODIFIED:20240707T074146Z
UID:6280-1672763400-1672767000@dimag.ibs.re.kr
SUMMARY:Youngho Yoo (유영호)\, Approximating TSP walks in subcubic graphs
DESCRIPTION:The Graphic Travelling Salesman Problem is the problem of finding a spanning closed walk (a TSP walk) of minimum length in a given connected graph. The special case of the Graphic TSP on subcubic graphs has been studied extensively due to their worst-case behaviour in the famous $\frac{4}{3}$-integrality-gap conjecture on the “subtour elimination” linear programming relaxation of the Metric TSP. \nWe prove that every simple 2-connected subcubic graph on $n$ vertices with $n_2$ vertices of degree 2 has a TSP walk of length at most $\frac{5n+n_2}{4}-1$\, confirming a conjecture of Dvořák\, Král’\, and Mohar. This bound is best possible and we characterize the extremal subcubic examples meeting this bound. We also give a quadratic time combinatorial algorithm to find such a TSP walk. In particular\, we obtain a $\frac{5}{4}$-approximation algorithm for the Graphic TSP on cubic graphs. Joint work with Michael Wigal and Xingxing Yu.
URL:https://dimag.ibs.re.kr/event/2023-01-03/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230110T163000
DTEND;TZID=Asia/Seoul:20230110T173000
DTSTAMP:20260419T150714
CREATED:20221123T222545Z
LAST-MODIFIED:20240705T171022Z
UID:6518-1673368200-1673371800@dimag.ibs.re.kr
SUMMARY:Mamadou Moustapha Kanté\, MSOL-Definable decompositions
DESCRIPTION:I will first introduce the notion of recognisability of languages of terms and then its extensions to sets of relational structures. In a second step\, I will discuss relations with decompositions of graphs/matroids and why their MSOL-definability is related to understanding recognisable sets. I will finally explain  how to define in MSOL branch-decompositions for finitely representable matroids of bounded path-width. This is joint work with Rutger Campbell\, Bruno Guillon\, Eun Jung Kim\, and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2023-01-10/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230117T163000
DTEND;TZID=Asia/Seoul:20230117T173000
DTSTAMP:20260419T150714
CREATED:20221213T152329Z
LAST-MODIFIED:20240707T074134Z
UID:6556-1673973000-1673976600@dimag.ibs.re.kr
SUMMARY:Noleen Köhler\, Twin-Width VIII: Delineation and Win-Wins
DESCRIPTION:We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated by twin-width (or simply\, delineated) if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$\, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadically dependent. An effective strengthening of delineation for a class $\mathcal C$ implies that tractable FO model checking on $\mathcal C$ is perfectly understood: On hereditary closures of subclasses $\mathcal D$ of $\mathcal C$\, FO model checking on $\mathcal D$ is fixed-parameter tractable (FPT) exactly when $\mathcal D$ has bounded twin-width. Ordered graphs [BGOdMSTT\, STOC ’22] and permutation graphs [BKTW\, JACM ’22] are effectively delineated\, while subcubic graphs are not. On the one hand\, we prove that interval graphs\, and even\, rooted directed path graphs are delineated. On the other hand\, we observe or show that segment graphs\, directed path graphs (with arbitrarily many roots)\, and visibility graphs of simple polygons are not delineated. \nIn an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not)\, we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW\, SODA ’21]. We show that $K_{t\,t}$-free segment graphs\, and axis-parallel $H_t$-free unit segment graphs have bounded twin-width\, where $H_t$ is the half-graph or ladder of height $t$. In contrast\, axis-parallel $H_4$-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated. \nMore broadly\, we explore which structures (large bicliques\, half-graphs\, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results\, combined with the FPT algorithm for first-order model checking on graphs given with $O(1)$-sequences [BKTW\, JACM ’22]\, give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If $p$ is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C\, then $p(G) \ge k$ can be decided in FPT time $f(k)\cdot |V (G)|O(1)$. For instance\, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains\, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width. \nJoint work with Édouard Bonnet\, Dibyayan Chakraborty\, Eun Jung Kim\, Raul Lopes and Stéphan Thomassé.
URL:https://dimag.ibs.re.kr/event/2023-01-17/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230119T100000
DTEND;TZID=Asia/Seoul:20230119T110000
DTSTAMP:20260419T150714
CREATED:20230103T142421Z
LAST-MODIFIED:20240705T170041Z
UID:6619-1674122400-1674126000@dimag.ibs.re.kr
SUMMARY:Pedro Montealegre\, A Meta-Theorem for Distributed Certification
DESCRIPTION:Distributed certification\, whether it be proof-labeling schemes\, locally checkable proofs\, etc.\, deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle\, and the processes are in charge of verifying these certificates\, so that two properties are satisfied: completeness\, i.e.\, for every legal instance\, there is a certificate assignment leading all processes to accept\, and soundness\, i.e.\, for every illegal instance\, and for every certificate assignment\, at least one process rejects. The verification of the certificates must be fast\, and the certificates themselves must be small. \nA large quantity of results have been produced in this framework\, each aiming at designing a distributed certification mechanism for specific boolean predicates. In this talk\, I will present a “meta-theorem”\, applying to many boolean predicates at once. Specifically\, I will show that\, for every boolean predicate on graphs definable in the monadic second-order (MSO) logic of graphs\, there exists a distributed certification mechanism using certificates on $O(log^2 n)$ bits in n-node graphs of bounded treewidth\, with a verification protocol involving a single round of communication between neighbors.
URL:https://dimag.ibs.re.kr/event/2023-01-19/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230125T163000
DTEND;TZID=Asia/Seoul:20230125T173000
DTSTAMP:20260419T150714
CREATED:20221109T131052Z
LAST-MODIFIED:20240705T171112Z
UID:6458-1674664200-1674667800@dimag.ibs.re.kr
SUMMARY:Jan Hladký\, Invitation to graphons
DESCRIPTION:The first course in graph theory usually covers concepts such as matchings\, independent sets\, colourings\, and forbidden subgraphs. Around 2004\, Borgs\, Chayes\, Lovász\, Sós\, Szegedy\, and Vestergombi introduced a very fruitful limit perspective on graphs. The central objects of this theory\, so-called graphons\, are suitable measurable counterparts to graphs. In the talk\, I will outline the syllabus of a hypothetical first course in graphon theory\, in particular introducing versions of all the aforementioned concepts in the graphon setting. Based on work with Doležal\, Hu\, Máthé\, Piguet\, Rocha.
URL:https://dimag.ibs.re.kr/event/2023-01-25/
LOCATION:Zoom ID: 224 221 2686 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230131T163000
DTEND;TZID=Asia/Seoul:20230131T173000
DTSTAMP:20260419T150714
CREATED:20230110T062223Z
LAST-MODIFIED:20240707T074122Z
UID:6639-1675182600-1675186200@dimag.ibs.re.kr
SUMMARY:Abhishek Methuku\, A proof of the Erdős–Faber–Lovász conjecture
DESCRIPTION:The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk\, I will sketch a proof of this conjecture for every large n. Joint work with D. Kang\, T. Kelly\, D. Kühn and D. Osthus.
URL:https://dimag.ibs.re.kr/event/2023-01-31/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR