BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.16.2//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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220801T163000
DTEND;TZID=Asia/Seoul:20220801T173000
DTSTAMP:20260525T125429
CREATED:20220801T073000Z
LAST-MODIFIED:20240707T075606Z
UID:5867-1659371400-1659375000@dimag.ibs.re.kr
SUMMARY:Seunghun Lee (이승훈)\, Inscribable order types
DESCRIPTION:We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk\, we investigate inscribability of order types. We first show that every simple order type with at most 2 interior points is inscribable\, and that the number of such order types is $\Theta(\frac{4^n}{n^{3/2}})$. We further construct an infinite family of minimally uninscribable order types. The proof of uninscribability mainly uses Möbius transformations. We also suggest open problems around inscribability. This is a joint work with Michael Gene Dobbins.
URL:https://dimag.ibs.re.kr/event/2022-08-01/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220809T163000
DTEND;TZID=Asia/Seoul:20220809T173000
DTSTAMP:20260525T125429
CREATED:20220808T073000Z
LAST-MODIFIED:20240707T075550Z
UID:5821-1660062600-1660066200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, Directed flow-augmentation
DESCRIPTION:We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that\, given a directed graph G\, two integers $s\,t\in V(G)$\, and an integer $k$\, adds (randomly) to $G$ a number of arcs such that for every minimal st-cut $Z$ in $G$ of size at most $k$\, with probability $2^{−\operatorname{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph.\nThe directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set\, whose parameterized complexity status was repeatedly posed as open problems:\n(1) Chain SAT\, defined by Chitnis\, Egri\, and Marx [ESA’13\, Algorithmica’17]\,\n(2) a number of weighted variants of classic directed cut problems\, such as Weighted st-Cut\, Weighted Directed Feedback Vertex Set\, or Weighted Almost 2-SAT.\nBy proving that Chain SAT is FPT\, we confirm a conjecture of Chitnis\, Egri\, and Marx that\, for any graph H\, if the List H-Coloring problem is polynomial-time solvable\, then the corresponding vertex-deletion problem is fixed-parameter tractable. \nJoint work with Stefan Kratsch\, Marcin Pilipczuk\, Magnus Wahlström.
URL:https://dimag.ibs.re.kr/event/2022-08-09/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220816T163000
DTEND;TZID=Asia/Seoul:20220816T173000
DTSTAMP:20260525T125429
CREATED:20220718T235006Z
LAST-MODIFIED:20240705T171145Z
UID:5967-1660667400-1660671000@dimag.ibs.re.kr
SUMMARY:Noleen Köhler\, Testing first-order definable properties on bounded degree graphs
DESCRIPTION:Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree model. We show that any FO property that is defined by a formula with quantifier prefix ∃*∀* is testable\, while there exists an FO property that is expressible by a formula with quantifier prefix ∀*∃* that is not testable. In the dense graph model\, a similar picture is long known (Alon\, Fischer\, Krivelevich\, Szegedy\, Combinatorica 2000)\, despite the very different nature of the two models. In particular\, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders\, based on zig-zag products of graphs. \nThis is joint work with Isolde Adler and Pan Peng.
URL:https://dimag.ibs.re.kr/event/2022-08-16/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220823T163000
DTEND;TZID=Asia/Seoul:20220823T173000
DTSTAMP:20260525T125429
CREATED:20220823T073000Z
LAST-MODIFIED:20240705T171142Z
UID:5971-1661272200-1661275800@dimag.ibs.re.kr
SUMMARY:Raul Lopes\, Temporal Menger and related problems
DESCRIPTION:A temporal graph is a graph whose edges are available only at specific times. In this scenario\, the only valid walks are the ones traversing adjacent edges respecting their availability\, i.e. sequence of adjacent edges whose appearing times are non-decreasing. \nGiven a graph G and vertices s and t of G\, Menger’s Theorem states that the maximum number of (internally) vertex disjoint s\,t-paths is equal to the minimum size of a subset X for which G-X contains no s\,t-path. This is a classical result in Graph Theory\, taught in most basic Graph Theory courses\, and it holds also when G is directed and when edge disjoint paths and edge cuts are considered instead. A direct translation of Menger’s Theorem to the temporal context has been known not to hold since an example was shown in the seminal paper by Kempe\, Kleinberg and Kumar (STOC’00). In this talk\, an overview of possible temporal versions of Menger’s Theorem will be discussed\, as well as the complexity of the related problems.
URL:https://dimag.ibs.re.kr/event/2022-08-23/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220830T163000
DTEND;TZID=Asia/Seoul:20220830T173000
DTSTAMP:20260525T125429
CREATED:20220830T073000Z
LAST-MODIFIED:20240707T075520Z
UID:6018-1661877000-1661880600@dimag.ibs.re.kr
SUMMARY:Jun Gao\, Number of (k-1)-cliques in k-critical graph
DESCRIPTION:We prove that for $n>k\geq 3$\, if $G$ is an $n$-vertex graph with chromatic number $k$ but any its proper subgraph has smaller chromatic number\, then $G$ contains at most $n-k+3$ copies of cliques of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai. \nThis is joint work with Jie Ma.
URL:https://dimag.ibs.re.kr/event/2022-08-30/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR