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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220801T163000
DTEND;TZID=Asia/Seoul:20220801T173000
DTSTAMP:20260420T034127
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:20220803T163000
DTEND;TZID=Asia/Seoul:20220803T173000
DTSTAMP:20260420T034127
CREATED:20220720T073000Z
LAST-MODIFIED:20240707T075557Z
UID:5637-1659544200-1659547800@dimag.ibs.re.kr
SUMMARY:Lars Jaffke\, Taming graphs with no large creatures and skinny ladders
DESCRIPTION:We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladder as an induced minor\, then there exists a polynomial $p$ such that every $G \in \mathcal{G}$ contains at most $p(|V(G)|)$ minimal separators. By a result of Fomin\, Todinca\, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set\, Feedback Vertex Set and many other problems\, when restricted to an input graph from $\mathcal{G}$. Furthermore\, as shown by Gartland and Lokshtanov\, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators). \nJoint work with Jakub Gajarský\, Paloma T. Lima\, Jana Novotná\, Marcin Pilipczuk\, Paweł Rzążewski\, and Uéverton S. Souza.
URL:https://dimag.ibs.re.kr/event/2022-08-03/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220809T163000
DTEND;TZID=Asia/Seoul:20220809T173000
DTSTAMP:20260420T034127
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:20220810T163000
DTEND;TZID=Asia/Seoul:20220810T173000
DTSTAMP:20260420T034127
CREATED:20220713T073000Z
LAST-MODIFIED:20240705T171145Z
UID:5849-1660149000-1660152600@dimag.ibs.re.kr
SUMMARY:Akash Kumar\, Random walks and Forbidden Minors
DESCRIPTION:Random walks and spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In this talk\, I will present how random walks helped make progress on algorithmic problems on planar graphs.\nIn particular\, I show how random walk based (i.e.\, spectral) approaches led to progress on finding forbidden minors [K.-Seshadhri-Stolman\, FOCS 2018] as well as on deciding planarity [K.-Seshadhri-Stolman\, STOC 2019] in bounded degree graphs within the property testing framework. I will also cover how these approaches eventually led to progress on the so-called “efficient partition oracle” problem [K.-Seshadhri-Stolman\, FOCS 2021].\nThe talk will assume minimal background by presenting a stand-alone story that should be of interest to students/researchers in computer science.
URL:https://dimag.ibs.re.kr/event/2022-08-10/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220816T163000
DTEND;TZID=Asia/Seoul:20220816T173000
DTSTAMP:20260420T034127
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:20260420T034127
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:20220825T100000
DTEND;TZID=Asia/Seoul:20220825T110000
DTSTAMP:20260420T034127
CREATED:20220825T010000Z
LAST-MODIFIED:20240707T075527Z
UID:6007-1661421600-1661425200@dimag.ibs.re.kr
SUMMARY:Brett Leroux\, Expansion of random 0/1 polytopes
DESCRIPTION:A conjecture of Milena Mihail and Umesh Vazirani states that the edge expansion of the graph of every $0/1$ polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a $0/1$ polytope in $\mathbb{R}^d$ is greater than 1 over some polynomial function of $d$. This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of a random $0/1$ polytope in $\mathbb{R}^d$ is at least $\frac{1}{12d}$ with high probability. \nAfter discussing this result and the proof\, we will mention some possible extensions. To conclude\, we will discuss some related questions about the combinatorics of random polytopes\, including the diameter problem. \nThis is joint work with Luis Rademacher.
URL:https://dimag.ibs.re.kr/event/2022-08-25/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220830T163000
DTEND;TZID=Asia/Seoul:20220830T173000
DTSTAMP:20260420T034127
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
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220831T163000
DTEND;TZID=Asia/Seoul:20220831T173000
DTSTAMP:20260420T034127
CREATED:20220816T233139Z
LAST-MODIFIED:20240707T075512Z
UID:6033-1661963400-1661967000@dimag.ibs.re.kr
SUMMARY:Raphael Steiner\, Congruence-constrained subdivisions in digraphs
DESCRIPTION:I will present the short proof from [1] that for every digraph F and every assignment of pairs of integers $(r_e\,q_e)_{e\in A(F)}$ to its arcs\, there exists an integer $N$ such that every digraph D with dichromatic number at least $N$ contains a subdivision of $F$ in which $e$ is subdivided into a directed path of length congruent to $r_e$ modulo $q_e$ for every $e \in  A(F)$. This generalizes to the directed setting the analogous result by Thomassen for undirected graphs and at the same time yields a novel proof of his result. I will also talk about how a hypergraph coloring result from [2] may help to obtain good bounds on $N$ in the special case when $F$ is subcubic. \n[1] https://arxiv.org/abs/2208.06358 \n[2] https://arxiv.org/abs/2206.13635
URL:https://dimag.ibs.re.kr/event/2022-08-31/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR