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:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260331T163000
DTEND;TZID=Asia/Seoul:20260331T173000
DTSTAMP:20260526T224033
CREATED:20250922T145919Z
LAST-MODIFIED:20260308T043639Z
UID:11631-1774974600-1774978200@dimag.ibs.re.kr
SUMMARY:Tung H. Nguyen\, Polynomial χ-boundedness for excluding the five-vertex path
DESCRIPTION:We overview the recent resolution of a 1985 open problem of Gyárfás\, that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path. The proof introduces a chromatic density framework involving chromatic quasirandomness and chromatic density increment\, which allows us to deduce the desired statement from the Erdős–Hajnal result for the five-vertex path.
URL:https://dimag.ibs.re.kr/event/2026-03-31/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260407T163000
DTEND;TZID=Asia/Seoul:20260407T173000
DTSTAMP:20260526T224033
CREATED:20260210T120802Z
LAST-MODIFIED:20260325T123033Z
UID:12159-1775579400-1775583000@dimag.ibs.re.kr
SUMMARY:Mamadou Moustapha Kanté\, Strongly flip-flat classes of graphs
DESCRIPTION:Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. Almost-wideness is a notion that was central in different characterisations of nowhere dense classes of graphs\, and in particular the game-theoretic one. In this talk I will present the flip-flatness notions and conjectures about the characterization of strongly flip-flat graph classes. Then\, I will present a proof that strongly flip-flat classes of graphs that are weakly sparse are indeed uniformly almost-wide\, making a step towards their characterisation. A consequence is a characterization of strongly flip-flat graph classes with low rank-depth colourings. \nThis is a joint work with F. Ghasemi\, J. Grange and F. Madelaine.
URL:https://dimag.ibs.re.kr/event/2026-04-07/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260428T163000
DTEND;TZID=Asia/Seoul:20260428T173000
DTSTAMP:20260526T224033
CREATED:20260303T004153Z
LAST-MODIFIED:20260303T004338Z
UID:12388-1777393800-1777397400@dimag.ibs.re.kr
SUMMARY:Xin Wei\, Separating hash families with large universe
DESCRIPTION:Separating hash families are useful combinatorial structures that generalize several well-studied objects in cryptography and coding theory. Let $p_t(N\, q)$ denote the maximum size of the universe for a $t$-perfect hash family of length $N$ over an alphabet of size $q$. We show that $q^{2 – o(1)} < p_t(t\, q) = o(q^2)$ for all  $t \ge 3$\, thereby resolving an open problem raised by Blackburn et al. (2008) for certain parameter ranges. Previously\, this result was known only for $t = 3$ and $t = 4$. Our approach establishes the existence of a large set of integers that avoids nontrivial solutions to a system of correlated linear equations. This is joint work with Xiande Zhang and Gennian Ge.
URL:https://dimag.ibs.re.kr/event/2026-04-28/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260506T163000
DTEND;TZID=Asia/Seoul:20260506T173000
DTSTAMP:20260526T224033
CREATED:20260313T150340Z
LAST-MODIFIED:20260403T110615Z
UID:12435-1778085000-1778088600@dimag.ibs.re.kr
SUMMARY:Maximilian Gorsky\, The Disjoint Paths Problem lies in the Oort cloud of algorithms
DESCRIPTION:In this talk we discuss recent work to that establishes that the bounds of the Vital Linkage Function is single-exponential. This has immediate impacts on the complexity of the k-Disjoint Paths Problem\, Minor Checking\, and more generally\, the Folio-Problem. We in fact prove something even stronger: It turns out that it is not in fact the number of terminals (or more generally vertices) that matters in these problems\, but rather their structure within the graph. Concretely\, we show that the Vital Linkage Function is single-exponential only in the bidimensionality of the terminals\, whilst the number of terminals contributes only polynomially. A direct consequence of this is an algorithm for the k-Disjoint Paths Problem running in $f(k)n^2$-time\, where f(k) is singly exponential in k and doubly exponential in the bidimensionality of k. This derives directly from an algorithm for the Folio-problem we give that has an analogous runtime. Notably these are the first algorithms for these problems in which the function f is explicit. In particular\, we give the first explicit bounds for the Vital Linkage Function. \nJoint work with Dario Cavallaro\, Stephan Kreutzer\, Dimitrios Thilikos\, and Sebastian Wiederrecht.
URL:https://dimag.ibs.re.kr/event/2026-05-06/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260512T163000
DTEND;TZID=Asia/Seoul:20260512T173000
DTSTAMP:20260526T224033
CREATED:20260320T061938Z
LAST-MODIFIED:20260407T022605Z
UID:12453-1778603400-1778607000@dimag.ibs.re.kr
SUMMARY:Benjamin Duhamel\, Excluding a forest induced minor
DESCRIPTION:We give an induced counterpart of the Forest Minor theorem: for any t ≥ 2\, the $K_{t\,t}$-subgraph-free H-induced-minor-free graphs have bounded pathwidth if and only if H belongs to a class F of forests\, which we describe as the induced minors of two (very similar) infinite parameterized families. This constitutes a significant step toward classifying the graphs H for which every weakly sparse H-induced-minor-free class has bounded treewidth. Our work builds on the theory of constellations developed in the Induced Subgraphs and Tree Decompositions series. \nThis is a joint work with É. Bonnet and R. Hickingbotham.
URL:https://dimag.ibs.re.kr/event/2026-05-12/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260519T163000
DTEND;TZID=Asia/Seoul:20260519T173000
DTSTAMP:20260526T224033
CREATED:20251215T012742Z
LAST-MODIFIED:20260511T073042Z
UID:11990-1779208200-1779211800@dimag.ibs.re.kr
SUMMARY:Xavier Goaoc\, A canonical tree decomposition for order types\, and some applications
DESCRIPTION:We introduce and study a notion of decomposition of planar point sets (or rather of their chirotopes) as trees decorated by smaller chirotopes. This decomposition is based on the concept of mutually avoiding sets (which we rephrase as modules)\, and adapts in some sense the modular decomposition of graphs in the world of chirotopes. The associated tree always exists and is unique up to some appropriate constraints. We also show how to compute the number of triangulations of a chirotope efficiently\, starting from its tree and the (weighted) numbers of triangulations of its parts. \nThis is joint work with Mathilde Bouvel\, Valentin Féray\, and Florent Koechlin.
URL:https://dimag.ibs.re.kr/event/2026-05-19/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260526T163000
DTEND;TZID=Asia/Seoul:20260526T173000
DTSTAMP:20260526T224033
CREATED:20260112T025344Z
LAST-MODIFIED:20260519T011855Z
UID:12084-1779813000-1779816600@dimag.ibs.re.kr
SUMMARY:Fernanda Rivera Omaña\, Erdős-Pósa theorem for matroids
DESCRIPTION:We will look at an analogue theorem of the classical Erdős-Pósa Theorem. We prove a $GF(q)$-representable matroid analogue of Robertson and Seymour’s theorem that planar graphs have an Erdős-Pósa property. Given a matroid $N$\, we prove that for every matroid $M$ with bounded branch width\, $M$ either contains $r$ skew copies of $N$\, or there is a small perturbation of $M$ that doesn’t contain $N$ as a minor. \nThis is joint work with James Davies and Meike Hatzel.
URL:https://dimag.ibs.re.kr/event/2026-05-26/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260602T163000
DTEND;TZID=Asia/Seoul:20260602T173000
DTSTAMP:20260526T224033
CREATED:20251210T144125Z
LAST-MODIFIED:20260524T215108Z
UID:11977-1780417800-1780421400@dimag.ibs.re.kr
SUMMARY:Maria Chudnovsky\, Induced minors and treewidth
DESCRIPTION:This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph\, and some complete bipartite graph as induced minors\, and some complete graph as a subgraph. Unfortunately\, such  classes still contain graphs of arbitrarily large treewidth. Moreover\, a result of Alecu\, Bonnet\, Bureo Villafana and Trotignon and its extensions suggest that there is no elegant characterization of families of bounded treewidth in terms of induced obstructions. \nOn the other hand\, it is conjectured that graphs in the classes as above have treewidth bounded by a poly-logarithmic function of their number of vertices. If true\, this will imply the existence of quasi-polynomial time algorithms for a host of problems on such  classes that are NP-complete in the general setting. \nWhile this conjecture remains open\, in joint work with Julien Codsi\, David Fischer and Daniel Lokshtanov\, we were able to prove the existence of a sub-polynomial bound on treewidth in terms of the number of vertices. This in turn leads to sub-exponential algorithmic behavior. \nIn this talk we will discuss some ideas of the proof\, and\, if time permits\, some results in the more general setting when the bound on the clique size is removed.
URL:https://dimag.ibs.re.kr/event/2025-06-02/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260609T163000
DTEND;TZID=Asia/Seoul:20260609T173000
DTSTAMP:20260526T224033
CREATED:20260420T212857Z
LAST-MODIFIED:20260522T151349Z
UID:12560-1781022600-1781026200@dimag.ibs.re.kr
SUMMARY:J. Pascal Gollin\, Dominated balanced separators in wheel-induced-minor-free graphs
DESCRIPTION:The grid theorem of Robertson and Seymour can be equivalently stated using balanced separators\, that are separators whose deletion leaves every component with no more than half of the vertices of the graph\, as follows. Every graph that excludes some planar graph as a minor has a balanced separator of bounded size. Building on this formulation\, Gartland and Lokshtanov conjectured an induced minor version of that theorem inspired by coarse graph theory. They conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator which is dominated by a bounded number of vertices. We confirm this conjecture for excluding any fixed wheel\, that is\, a cycle together with a universal vertex\, as an induced minor. \nThis talk is based on joint work with Maria Chudnovsky\, Matjaž Krnc\, and Martin Milanič.
URL:https://dimag.ibs.re.kr/event/2026-06-09/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260619T163000
DTEND;TZID=Asia/Seoul:20260619T173000
DTSTAMP:20260526T224033
CREATED:20260515T123736Z
LAST-MODIFIED:20260515T123736Z
UID:12649-1781886600-1781890200@dimag.ibs.re.kr
SUMMARY:Stefan Weltge\, Multiplicative assignment with upgrades
DESCRIPTION:We study a problem related to submodular function optimization and the exact matching problem for which we show a rather peculiar status: its natural LP-relaxation can have fractional optimal vertices\, but there is always also an optimal integral vertex\, which we can also compute in polynomial time. More specifically\, we consider the multiplicative assignment problem with upgrades in which we are given a set of customers and suppliers and we seek to assign each customer to a different supplier. Each customer has a demand and each supplier has a regular and an upgraded cost for each unit demand provided to the respective assigned client. Our goal is to upgrade at most k suppliers and to compute an assignment in order to minimize the total resulting cost. This can be cast as the problem to compute an optimal matching in a bipartite graph with the additional constraint that we must select k edges from a certain group of edges\, similar to selecting k red edges in the exact matching problem. Also\, selecting the suppliers to be upgraded corresponds to maximizing a submodular set function under a cardinality constraint. Our result yields an efficient LP-based algorithm to solve our problem optimally. In addition\, we provide also a purely strongly polynomial-time algorithm for it. As an application\, we obtain exact algorithms for the upgrading variant of the problem to schedule jobs on identical or uniformly related machines in order to minimize their sum of completion times\, i.e.\, where we may upgrade up to k jobs to reduce their respective processing times. \nThis is joint work with Alexander Armbruster\, Lars Rohwedder\, Andreas Wiese\, and Ruilong Zhang.
URL:https://dimag.ibs.re.kr/event/2026-06-19/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260710T163000
DTEND;TZID=Asia/Seoul:20260710T173000
DTSTAMP:20260526T224033
CREATED:20260324T141000Z
LAST-MODIFIED:20260505T064804Z
UID:12471-1783701000-1783704600@dimag.ibs.re.kr
SUMMARY:Ting-Wei Chao\, The Oddtown Problem Modulo a Composite Number
DESCRIPTION:A family of sets in $[n]$ is called an $\ell$-Oddtown if the sizes of all sets are not divisible by $\ell$\, but the sizes of pairwise intersections are divisible by $\ell$. The problem was completely solved when $\ell$ is a prime via an elegant linear algebraic method\, showing that the family has size at most $n$. However\, not much was known for composite numbers. By splitting the family into families correspond to each prime factor of $\ell$\, one can show that the number is at most $\omega n$\, where $omega$ is the number of prime factors of $\ell$. We used both combinatorial and Fourier analytic arguments to prove that the number of sets in any $\ell$-Oddtown is at most $\omega n-(2\omega+\varepsilon)\log_2 n$ for most $n\,\ell$.
URL:https://dimag.ibs.re.kr/event/2026-07-10/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260805T163000
DTEND;TZID=Asia/Seoul:20260805T173000
DTSTAMP:20260526T224033
CREATED:20260520T141609Z
LAST-MODIFIED:20260520T141609Z
UID:12683-1785947400-1785951000@dimag.ibs.re.kr
SUMMARY:Meike Hatzel\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2026-08-05/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260818T163000
DTEND;TZID=Asia/Seoul:20260818T173000
DTSTAMP:20260526T224033
CREATED:20260326T020259Z
LAST-MODIFIED:20260326T020259Z
UID:12486-1787070600-1787074200@dimag.ibs.re.kr
SUMMARY:Jinyoung Park (박진영)\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2026-08-18/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR