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:20240101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260710T163000 DTEND;TZID=Asia/Seoul:20260710T173000 DTSTAMP:20260416T075424 CREATED:20260324T141000Z LAST-MODIFIED:20260326T130309Z UID:12471-1783701000-1783704600@dimag.ibs.re.kr SUMMARY:Ting-Wei Chao\, Entropy method and mixture bound DESCRIPTION:The entropy method has been used in many recent works in extremal combinatorics. With the help of Shannon entropy\, significant progress has been made on several classical problems\, such as the union-closed conjecture and the Sidorenko conjecture. In our recent work\, we use the entropy method to give new proofs of the Kruskal–Katona theorem and Turán’s theorem\, as well as some of their generalizations. The new ingredient in our approach is a method for upper bounding the sum of $2^{\mathbb{H}(X_i)}$  for random variables $X_1\,\cdots\,X_k$ whose supports do not overlap too much. We call this method the mixture bound\, and it can be viewed as an entropic version of double counting. In this talk\, I will introduce the mixture bound and show some examples of how it can be applied on colorful versions of the Kruskal–Katona theorem. Base on joint work with Maya Sankar and Hung-Hsun Hans Yu. URL:https://dimag.ibs.re.kr/event/2026-07-10/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;VALUE=DATE:20260628 DTEND;VALUE=DATE:20260712 DTSTAMP:20260416T075424 CREATED:20260415T104127Z LAST-MODIFIED:20260415T104444Z UID:12537-1782604800-1783814399@dimag.ibs.re.kr SUMMARY:2026 Workshop on Topological Combinatorics DESCRIPTION:The 2026 Workshop on Topological Combinatorics will be held from June 28 to July 11\, 2026 at Gwangju Institute of Science and Technology (GIST)\, located in Gwangju in the southwest of Republic of Korea.  \nThe workshop aims to bring together researchers interested in applications of topology to combinatorics and related areas. This will be the fifth workshop in a series initiated by Ron Aharoni (August 2018 in Shantou\, July 2019 in Prague\, July 2020 on Zoom\, and June 2024 in Paris). \nThe first week (June 28 – July 04) will be reserved for presentations\, while the following days (July 05 – July 11) will be for discussion and collaborations.  \nThe campus offers a variety of amenities\, including a guesthouse that can accommodate approximately 20 guests. \nIn addition\, various lodging options are available within a 15–20 minute walking distance. \nWe are planning to provide accommodation for all invited participants\, and we are also considering offering partial travel support for those with limited funding. \n\nWebsite: https://sites.google.com/view/2026topocomb URL:https://dimag.ibs.re.kr/event/2026-06-28/ LOCATION:GIST CATEGORIES:Workshops and Conferences END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260609T163000 DTEND;TZID=Asia/Seoul:20260609T173000 DTSTAMP:20260416T075424 CREATED:20260122T084352Z LAST-MODIFIED:20260122T084352Z UID:12117-1781022600-1781026200@dimag.ibs.re.kr SUMMARY:Martin Milanič\, TBA DESCRIPTION: 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:20260602T163000 DTEND;TZID=Asia/Seoul:20260602T173000 DTSTAMP:20260416T075424 CREATED:20251210T144125Z LAST-MODIFIED:20251225T223707Z UID:11977-1780417800-1780421400@dimag.ibs.re.kr SUMMARY:Maria Chudnovsky\, TBA DESCRIPTION: 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:20260526T163000 DTEND;TZID=Asia/Seoul:20260526T173000 DTSTAMP:20260416T075424 CREATED:20260112T025344Z LAST-MODIFIED:20260122T105556Z UID:12084-1779813000-1779816600@dimag.ibs.re.kr SUMMARY:Sarah Morell\, Unsplittable Transshipments DESCRIPTION:We consider an arc-capacitated directed graph $D=(V\,A)$\, where each node $v$ is associated with a rational balance value $b(v)$. Nodes with negative balance values are referred to as sources\, while those with positive balance values are called sinks. A feasible $b$-transshipment is a flow $f : A \to \mathbb{R}_{\ge 0}$ that routes the total supply of the sources to the sinks through $D$\, while respecting the given arc capacity constraints and satisfying the balance requirements at each node. An unsplittable $b$-transshipment additionally requires that\, for each source-sink pair\, the flow sent from that source to that sink is routed along at most one directed path. Unsplittable $b$-transshipments (UT) generalize the well-studied single source unsplittable flow (SSUF) problem in which $D$ contains a single source and multiple sinks\, and each demand must be routed along a single path from the common source to its destination. \nGiven a feasible $b$-transshipment $f$ that is not necessarily unsplittable\, a natural question is whether there exists an feasible unsplittable $b$-transshipment flow $g$ that approximates $f$ in an arc-wise sense. In particular\, we seek bounds on the maximum deviation $|f_a-g_a|$ over all arcs $a \in A$. For the special case of SSUFs\, Dinitz\, Garg\, and Goemans (Combinatorica 1999) proved that there exists an unsplittable flow $g$ such that $g_a \leq f_a + d_{\max}$ for all $a \in A$\, where $d_{\max}$ denotes the maximum demand value. Jointly with Martin Skutella (Mathematical Programming 2022)\, we studied unsplittable flows with arc-wise lower bounds and showed that there exists an unsplittable flow $g$ satisfying $g_a \ge f_a – d_{\max}$ for all $a \in A$. \n In this talk\, we extend this line of research by adapting the techniques of Dinitz\, Garg\, and Goemans to the more general setting of UTs. We show that\, given any feasible $b$-transshipment $f$\, there exists a feasible unsplittable $b$-transshipment $g$ such that $g_a \leq f_a + d_{\max}$ (resp. $g_a \ge f_a – d_{\max}$) for all $a \in A$. \n This is joint work with Srinwanti Debgupta and Martin Skutella. 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:20260519T163000 DTEND;TZID=Asia/Seoul:20260519T173000 DTSTAMP:20260416T075424 CREATED:20251215T012742Z LAST-MODIFIED:20251215T012742Z UID:11990-1779208200-1779211800@dimag.ibs.re.kr SUMMARY:Xavier Goaoc\, TBA DESCRIPTION: 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:20260512T163000 DTEND;TZID=Asia/Seoul:20260512T173000 DTSTAMP:20260416T075424 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:20260506T163000 DTEND;TZID=Asia/Seoul:20260506T173000 DTSTAMP:20260416T075424 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:20260428T163000 DTEND;TZID=Asia/Seoul:20260428T173000 DTSTAMP:20260416T075424 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:20260407T163000 DTEND;TZID=Asia/Seoul:20260407T173000 DTSTAMP:20260416T075424 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:20260331T163000 DTEND;TZID=Asia/Seoul:20260331T173000 DTSTAMP:20260416T075424 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:20260324T163000 DTEND;TZID=Asia/Seoul:20260324T173000 DTSTAMP:20260416T075424 CREATED:20251114T231517Z LAST-MODIFIED:20260227T004232Z UID:11858-1774369800-1774373400@dimag.ibs.re.kr SUMMARY:Hidde Koerts\, Characterizing large clique number in tournaments DESCRIPTION:A backedge graph of a tournament $T$ with respect to a total ordering $\prec$ of the vertices of $T$ is a graph on $V(T)$ where $uv$ is an edge if and only if $uv \in A(T)$ and $v \prec u$. In 2023\, Aboulker\, Aubian\, Charbit and Lopes introduced the clique number of tournaments based on backedge graphs as a natural counterpart to the dichromatic number of tournaments. Specifically\, the clique number of a tournament is the minimum clique number of a backedge graph when considering all possible orderings. \nGiven this definition\, it is not immediately clear what the canonical clique object should be. In this talk\, we provide an answer to this question. We show that if a tournament has large clique number\, it contains a reasonably large subtournament from one of two simple and previously studied families of tournaments of unbounded clique number. \nThis talk is based on joint work with Logan Crew\, Xinyue Fan\, Benjamin Moore\, and Sophie Spirkl. URL:https://dimag.ibs.re.kr/event/2026-03-24/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260312T163000 DTEND;TZID=Asia/Seoul:20260312T173000 DTSTAMP:20260416T075424 CREATED:20260226T002641Z LAST-MODIFIED:20260226T002641Z UID:12290-1773333000-1773336600@dimag.ibs.re.kr SUMMARY:József Balogh\, Clique covers and decompositions of cliques of graphs DESCRIPTION:Two related papers will be discussed: \n1. In 1966\, Erdős\, Goodman\, and Pósa showed that if $G$ is an $n$-vertex graph\, then at most $\lfloor n^2/4 \rfloor$ cliques of $G$ are needed to cover the edges of $G$\, and the bound is best possible as witnessed by the balanced complete bipartite graph. This was generalized independently by Győri–Kostochka\, Kahn\, and Chung\, who showed that every $n$-vertex graph admits an edge-decomposition into cliques of total `cost’ at most $2 \lfloor n^2/4 \rfloor$\, where an $i$-vertex clique has cost $i$. Erdős suggested the following strengthening: every $n$-vertex graph admits an edge-decomposition into cliques of total cost at most $\lfloor n^2/4 \rfloor$\, where now an $i$-vertex clique has cost $i-1$. We prove fractional relaxations and asymptotically optimal versions of both this conjecture and a conjecture of Dau\, Milenkovic\, and Puleo on covering the $t$-vertex cliques of a graph instead of the edges. Our proofs introduce a general framework for these problems using Zykov symmetrization\, the Frankl–Rödl nibble method\, and the Szemerédi Regularity Lemma. It is joint work with Jialin He\, Robert Krueger\, The Nguyen\, and Michael Wigal. \n2. Let $r \ge 3$ be fixed and $G$ be an $n$-vertex graph. A long-standing conjecture of Győri states that if $e(G) = t_{r-1}(n) + k$\, where $t_{r-1}(n)$ denotes the number of edges of the Turán graph on $n$ vertices and $r – 1$ parts\, then $G$ has at least $(2 – o(1))k/r$ edge-disjoint $r$-cliques. We prove this conjecture. It is joint work with Michael Wigal. URL:https://dimag.ibs.re.kr/event/2026-03-12/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260310T163000 DTEND;TZID=Asia/Seoul:20260310T173000 DTSTAMP:20260416T075424 CREATED:20251018T001247Z LAST-MODIFIED:20260310T112956Z UID:11743-1773160200-1773163800@dimag.ibs.re.kr SUMMARY:Dario Cavallaro\, Well-quasi-ordering Eulerian directed graphs by (strong) immersion DESCRIPTION:Directed graphs prove to be very hard to tame in contrast to undirected graphs. In particular\, they are not well-quasi-ordered by any known relevant inclusion relation\, and are lacking fruitful structure theorems. This motivates the search for structurally rich subclasses of directed graphs that are well behaved. Eulerian directed graphs are a particularly prominent example\, sharing many similarities with undirected graphs. In fact\, it is conjectured that Eulerian directed graphs are well-quasi-ordered by weak immersion\, and even well-quasi-ordered by strong immersion when restricting to classes of bounded degree. We believe that we have a proof of both conjectures\, and I will report on the current status\, progress\, and steps towards said proof and its implications. This is joint work with Ken-ichi Kawarabayashi and Stephan Kreutzer. URL:https://dimag.ibs.re.kr/event/2026-03-10/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260303T163000 DTEND;TZID=Asia/Seoul:20260303T173000 DTSTAMP:20260416T075424 CREATED:20250911T064608Z LAST-MODIFIED:20260219T013227Z UID:11576-1772555400-1772559000@dimag.ibs.re.kr SUMMARY:Chính T. Hoàng\, Problems on graph coloring DESCRIPTION:A k-coloring of a graph is an assignment of k colors to its vertices such that no two adjacent adjacent vertices receive the same color. The Coloring Problem is the problem of determining the smallest k such that the graph admits a k-coloring. Given a set L of graphs\, a graph G is L-free if G does not contain any graph in L as an induced subgraph. The complexity of the Coloring Problem for L-free graphs is known (NP-complete or polynomial-time solvable) whenever L contains a single graph. There has been keen interest in coloring graphs whose forbidden list L contains basic graphs such as induced paths\, induced cycles and their complements. In this talk\, I will provide a survey of recent progress on this topic. URL:https://dimag.ibs.re.kr/event/2026-03-03/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260224T163000 DTEND;TZID=Asia/Seoul:20260224T173000 DTSTAMP:20260416T075424 CREATED:20251119T205949Z LAST-MODIFIED:20260202T004550Z UID:11865-1771950600-1771954200@dimag.ibs.re.kr SUMMARY:Marek Sokołowski\, Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP DESCRIPTION:In this talk\, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly\, we prove that directed SSSP can be solved within $\widetilde{O}(m+n^{2-\varepsilon})$ work and $\widetilde{O}(n^{1-\varepsilon})$ depth for some positive $\varepsilon>0$. For dense graphs with non-negative real weights\, this yields the first nearly work-efficient strongly polynomial algorithm with sublinear depth. Moreover\, we develop efficient parallel algorithms in the Word RAM model for several variants of SSSP in graphs with exponentially large edge weights. \nThis is a joint work with Adam Karczmarz and Wojciech Nadara. URL:https://dimag.ibs.re.kr/event/2026-02-24/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260210T163000 DTEND;TZID=Asia/Seoul:20260210T173000 DTSTAMP:20260416T075424 CREATED:20251120T125949Z LAST-MODIFIED:20260121T225453Z UID:11872-1770741000-1770744600@dimag.ibs.re.kr SUMMARY:Seonghun Park (박성훈)\, Formalizing Flag Algebras in the Lean Theorem Prover DESCRIPTION:Flag algebras are a mathematical framework introduced by Alexander Razborov in 2007\, which has been used to resolve a wide range of open problems in extremal graph theory in the past twenty years. This framework provides an algebraic setup where one can express relationships between induced subgraph densities symbolically. It also comes with mathematical techniques for systematically deriving such relationships that always hold. Some of these techniques have even been implemented in automatic tools\, such as Flagmatic. In this work\, we formalise flag algebras in Lean\, an interactive theorem prover based on dependent type theory. Lean is computer software that lets us write mathematical definitions and proofs in a computer and check the correctness of written proofs using a computer. By formalizing flag algebras in Lean\, we can ensure that the mathematical foundation of flag algebras does not have any mistakes\, and provide a mathematical guarantee that theorems proved by flag algebras are indeed correct. In this talk\, I will explain flag algebras and our Lean formalization using Mantel’s theorem as a guiding example. In the process\, I will describe the challenges and lessons learned during the formalization. \nThis is a joint work with Jihoon Hyun\, Gyeongwon Jeong\, Sang-il Oum\, and Hongseok Yang. URL:https://dimag.ibs.re.kr/event/2026-02-10/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260203T163000 DTEND;TZID=Asia/Seoul:20260203T173000 DTSTAMP:20260416T075424 CREATED:20260105T005335Z LAST-MODIFIED:20260105T054623Z UID:12035-1770136200-1770139800@dimag.ibs.re.kr SUMMARY:Xiaofan Yuan (袁晓璠)\, Rainbow structures in edge colored graphs DESCRIPTION:Let $G = (V\, E)$ be a graph on $n$ vertices\, and let $c : E \to P$\, where $P$ is a set of colors. Let $\delta^c(G) = \min_{v \in V} \{ d^{c}(v) \}$ where $d^c(v)$ is the number of colors on edges incident to a vertex $v$ of $G$. In 2011\, Fujita and Magnant showed that if $G$ is a graph on $n$ vertices that satisfies $\delta^c(G)\geq n/2$\, then for every two vertices $u\, v$ there is a properly-colored $u\,v$-path in $G$. We show that for sufficiently large graphs $G$\, the same bound for $\delta^c(G)$ implies that any two vertices are connected by a rainbow path. We also show sufficient conditions on $\delta^c(G)$ for the existence of a rainbow cycle of length $2k$ in sufficiently large bipartite graphs $G$\, which are tight in many cases. This is joint work with Andrzej Czygrinow. URL:https://dimag.ibs.re.kr/event/2026-02-03/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260127T163000 DTEND;TZID=Asia/Seoul:20260127T173000 DTSTAMP:20260416T075424 CREATED:20251015T110913Z LAST-MODIFIED:20260106T021752Z UID:11724-1769531400-1769535000@dimag.ibs.re.kr SUMMARY:Daniel Dadush\, A Strongly Polynomial Algorithm for Linear Programs with at Most Two Non-Zero Entries per Row or Column DESCRIPTION:We give a strongly polynomial algorithm for minimum cost generalized flow\, and hence for optimizing any linear program with at most two non-zero entries per row\, or at most two non-zero entries per column. Primal and dual feasibility were shown by Végh (MOR ’17) and Megiddo (SICOMP ’83) respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time\, also referred to as Smale’s 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) due to Allamigeon\, Dadush\, Loho\, Natura and Végh (FOCS ’22). The number of iterations needed by the IPM is bounded\, up to a polynomial factor in the number of inequalities\, by the straight line complexity of the central path. Roughly speaking\, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution\, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum (ORL ’04)\, the same bound applies to any linear program with at most two non-zeros per column or per row \nJoint work with Zhuan Khye Koh (Boston U)\, Bento Natura (Columbia)\, Neil Olver (LSE)\, and László A. Végh (Bonn). URL:https://dimag.ibs.re.kr/event/2026-01-27/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260120T163000 DTEND;TZID=Asia/Seoul:20260120T173000 DTSTAMP:20260416T075424 CREATED:20251012T113928Z LAST-MODIFIED:20251212T235119Z UID:11717-1768926600-1768930200@dimag.ibs.re.kr SUMMARY:Tomáš Masařík\, Separator Theorem for Minor-free Graphs in Linear Time DESCRIPTION:The planar separator theorem by Lipton and Tarjan [FOCS ’77\, SIAM Journal on Applied Mathematics ’79] states that any planar graph with $n$ vertices has a balanced separator of size $O(\sqrt{n})$ that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan’s theorem to nonplanar graphs\, Alon\, Seymour\, and Thomas [STOC ’90\, Journal of the AMS ’90] showed that any minor-free graph admits a balanced separator of size $O(\sqrt{n})$ that can be found in $O(n^{3/2})$ time. The superlinear running time in their separator theorem is a key bottleneck for generalizing algorithmic results from planar to minor-free graphs. Despite extensive research for more than two decades\, finding a balanced separator of size $O(\sqrt{n})$ in (linear) $O(n)$ time for minor-free graphs remains a major open problem. Known algorithms either give a separator of size much larger than $O(\sqrt{n})$ or have superlinear running time\, or both. \nIn this paper\, we answer the open problem affirmatively. Our algorithm is very simple: it runs a vertex-weighted variant of breadth-first search (BFS) a constant number of times on the input graph. Our key technical contribution is a weighting scheme on the vertices to guide the search for a balanced separator\, offering a new connection between the size of a balanced separator and the existence of a clique-minor model. We believe that our weighting scheme may be of independent interest. \nThis is a joint work with Édouard Bonnet\, Tuukka Korhonen\, Hung Le\, and Jason Li. URL:https://dimag.ibs.re.kr/event/2026-01-20/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260113T163000 DTEND;TZID=Asia/Seoul:20260113T173000 DTSTAMP:20260416T075424 CREATED:20251201T074437Z LAST-MODIFIED:20251208T125825Z UID:11942-1768321800-1768325400@dimag.ibs.re.kr SUMMARY:Ferdinand Ihringer\, Boolean Functions Analysis in the Grassmann Graph DESCRIPTION:Boolean function analysis for the hypercube $\{ 0\, 1 \}^n$ is a well-developed field and has many famous results such as the FKN Theorem or Nisan-Szegedy Theorem. One easy example is the classification of Boolean degree $1$ functions: If $f$ is a real\, $n$-variate affine function which is Boolean on the $n$-dimensional hypercube (that is\, $f(x) \in \{ 0\, 1 \}$ for $x \in \{ 0\, 1 \}^n$)\, then $f(x) = 0$\, $f(x) = 1$\, $f(x) = x_i$ or $f(x) = 1 – x_i$. The same classification (essentially) holds if we restrict $\{ 0\, 1\}^n$ to elements with Hamming weight $k$ if $n-k\, k \geq 2$. If we replace $k$-sets of $\{ 1\, \ldots\, n \}$ by $k$-spaces in $V(n\, q)$\, the $n$-dimensional vector space over the field with $q$ elements\, then suddenly even the simple question of classifying Boolean degree $1$ functions\, here traditionally known as Cameron-Liebler classes\, becomes seemingly hard to solve. \nWe will discuss some results on low-degree Boolean functions in the vector space setting. Most notably\, we will discuss how vector space Ramsey numbers\, so extremal combinatorics\, can be utilized in this finite geometrical setting. URL:https://dimag.ibs.re.kr/event/2026-01-13/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20260106T163000 DTEND;TZID=Asia/Seoul:20260106T173000 DTSTAMP:20260416T075424 CREATED:20251030T130957Z LAST-MODIFIED:20251226T132814Z UID:11793-1767717000-1767720600@dimag.ibs.re.kr SUMMARY:Daniel Mock\, A Simple Algorithm for the Dominating Set Problem and More DESCRIPTION:In [1]\, Fabianski et. al. developed a simple\, yet surprisingly powerful algorithmic framework to develop efficient parameterized graph algorithms. Notably they derive a simple parameterized algorithm for the dominating set problem on a variety of graph classes\, including powers of nowhere dense classes and biclique-free classes. These results encompass a wide range of previously known results and often improve the best known running times. Similar results follow for the distance-r variation of dominating set and for independent set. The running time of the algorithm is closely tied to model-theoretic properties\, i.e. stability and the Helly property. \nWe build upon these results and develop a similar algorithm which only relies on the strong Helly property and does not need stability. For the dominating set problem\, we get a parameterized algorithm that works (additionally to biclique-free classes and powers of nowhere dense classes) weakly gamma-closed classes while being simpler and faster than previously known results. \nIn this talk\, we introduce the basic framework\, results by Fabianski et. al and connections to other areas. We discuss our new insights and possible research directions. \n[1] Grzegorz Fabianski\, Michal Pilipczuk\, Sebastian Siebertz\, Szymon Torunczyk: Progressive Algorithms for Domination and Independence. STACS 2019 URL:https://dimag.ibs.re.kr/event/2026-01-06/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20251230T163000 DTEND;TZID=Asia/Seoul:20251230T173000 DTSTAMP:20260416T075424 CREATED:20251126T141109Z LAST-MODIFIED:20251126T141109Z UID:11882-1767112200-1767115800@dimag.ibs.re.kr SUMMARY:Yunbum Kook (국윤범)\, Sampling and volume computation DESCRIPTION:Since the development of the first randomized polynomial-time algorithm for volume computation by Dyer\, Frieze\, and Kannan in 1989\, convex-body sampling has been a central problem at the intersection of algorithms\, geometry\, and probability. A major milestone came in 1997\, when Kannan\, Lovász\, and Simonovits analyzed the Ball Walk and formulated the influential KLS conjecture. This was extended to log-concave distributions by Lovász and Vempala in 2006\, and further accelerated by Cousins and Vempala in 2015 through warm-start generation techniques. \nIn this talk\, I will present a gentle introduction to these milestones and how they have been streamlined and improved in the past few years. The talk is based on joint work with Santosh Vempala. URL:https://dimag.ibs.re.kr/event/2025-12-30/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20251226T163000 DTEND;TZID=Asia/Seoul:20251226T173000 DTSTAMP:20260416T075424 CREATED:20251002T131231Z LAST-MODIFIED:20251127T040716Z UID:11684-1766766600-1766770200@dimag.ibs.re.kr SUMMARY:Donggyu Kim (김동규)\, Grassmann-Plücker functions for orthogonal matroids DESCRIPTION:We present a new cryptomorphic definition of orthogonal matroids with coefficients using Grassmann-Plücker functions. The equivalence is motivated by Cayley’s identities expressing principal and almost-principal minors of a skew-symmetric matrix in terms of its pfaffians. As a corollary of the new cryptomorphism\, we deduce that each component of the orthogonal Grassmannian is parameterized by certain part of the Plücker coordinates. \nThis is joint work with Changxin Ding. URL:https://dimag.ibs.re.kr/event/2025-12-26/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20251216T163000 DTEND;TZID=Asia/Seoul:20251216T173000 DTSTAMP:20260416T075424 CREATED:20251128T074641Z LAST-MODIFIED:20251128T074641Z UID:11891-1765902600-1765906200@dimag.ibs.re.kr SUMMARY:Chi Hoi Yip\, Cliques in Paley graphs and cyclotomic graphs DESCRIPTION:Given a prime power $q \equiv 1 \pmod 4$\, the Paley graph of order $q$ is the graph defined over $\mathbb{F}_q$ (the finite field with $q$ elements)\, such that two vertices are adjacent if and only if their difference is a square in $\mathbb{F}_q$. In this talk\, I will present some recent progress on the clique number of Paley graphs of non-square order\, the characterization of maximum cliques in Paley graphs of square order\, as well as their extensions to cyclotomic graphs. In particular\, I will highlight a new proof of the Van Lint–MacWilliams’ conjecture using ideas from arithmetic combinatorics. URL:https://dimag.ibs.re.kr/event/2025-12-16/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20251209T163000 DTEND;TZID=Asia/Seoul:20251209T173000 DTSTAMP:20260416T075424 CREATED:20250716T135828Z LAST-MODIFIED:20251031T171121Z UID:11244-1765297800-1765301400@dimag.ibs.re.kr SUMMARY:Tuukka Korhonen\, Dynamic Treewidth in Logarithmic Time DESCRIPTION:We present a dynamic data structure that maintains a tree decomposition of width at most 9k+8 of a dynamic graph with treewidth at most k\, which is updated by edge insertions and deletions. The amortized update time of our data structure is $2^{O(k)} \log n$\, where n is the number of vertices. The data structure also supports maintaining any “dynamic programming scheme” on the tree decomposition\, providing\, for example\, a dynamic version of Courcelle’s theorem with $O_k(\log n)$ amortized update time; the $O_k(⋅)$ notation hides factors that depend on k. This improves upon a result of Korhonen\, Majewski\, Nadara\, Pilipczuk\, and Sokołowski [FOCS 2023]\, who gave a similar data structure but with amortized update time $2^{k^{O(1)}} n^{o(1)}$. Furthermore\, our data structure is arguably simpler. Our main novel idea is to maintain a tree decomposition that is “downwards well-linked”\, which allows us to implement local rotations and analysis similar to those for splay trees. \nThis talk is based on arXiv:2504.02790. URL:https://dimag.ibs.re.kr/event/2025-12-09/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20251208T163000 DTEND;TZID=Asia/Seoul:20251208T173000 DTSTAMP:20260416T075424 CREATED:20250812T235815Z LAST-MODIFIED:20251206T235635Z UID:11359-1765211400-1765215000@dimag.ibs.re.kr SUMMARY:Matthew Kwan\, Exponential anticoncentration of the permanent DESCRIPTION:Let A be a random n×n matrix with independent entries\, and suppose that the entries are “uniformly anticoncentrated” (for example\, A could be a uniformly random n×n matrix with ±1 entries). We prove that the permanent of A is exponentially anticoncentrated\, significantly improving previous bounds of Tao and Vu. Our proof also works for the determinant\, giving an alternative proof of a classical theorem of Kahn\, Komlós and Szemerédi. Joint work with Zach Hunter and Lisa Sauermann. URL:https://dimag.ibs.re.kr/event/2025-12-08/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;VALUE=DATE:20251127 DTEND;VALUE=DATE:20251201 DTSTAMP:20260416T075424 CREATED:20250421T055422Z LAST-MODIFIED:20251130T005151Z UID:10819-1764201600-1764547199@dimag.ibs.re.kr SUMMARY:5th East Asia Workshop on Extremal and Structural Graph Theory DESCRIPTION:The 5th East Asia Workshop on Extremal and Structural Graph Theory is a workshop to bring active researchers in the field of extremal and structural graph theory\, especially in the East Asia such as China\, Japan\, and Korea. \n \nDate\nNovember 27\, 2025 Thursday (Arrival Day) — November 30\, 2025 Sunday (Departure Day) \nVenue\nFraser Place Namdaemun\, Seoul \nProgram Book\nInvited Speakers\n\nShinya Fujita (Yokohama City University)\nJie Han (Beijing Institute of Technology)\nTony Huynh (IBS Discrete Mathematics Group)\nJaehoon Kim (KAIST)\nO-joung Kwon (Hanyang University / IBS Discrete Mathematics Group)\nHong Liu (IBS Extremal Combinatorics and Probability Group)\nJie Ma (University of Science and Technology of China / Tsinghua University)\nShun-ichi Maezawa (Nihon University)\nBoram Park (Seoul National University)\nShohei Satake (Kumamoto University)\nTuan Tran (University of Science and Technology of China)\nShoichi Tsuchiya (Senshu University)\nXuding Zhu (Zhejiang Normal University)\n\nOrganizers\nSeog-Jin Kim\, Sang-il Oum\, Kenta Ozeki\, Hehui Wu \nRegistration\nInvitation Only. https://indico.ibs.re.kr/event/1041/ \nThere is no registration fee and one dinner (banquet) will be provided. \nHistory\n\n4th East Asia Workshop on Extremal and Structural Graph Theory\n\nMar. 27 – Mar. 31\, 2025.\nSchool of Mathematics\, Sun-Yet Sen University\, Guangzhou\, China\nOrganizers: Ping Hu\, Seog-Jin Kim\, Kenta Ozeki\, Hehui Wu.\n\n\n\n\n3rd East Asia Workshop on Extremal and Structural Graph Theory\n\nNov. 1- Nov. 5\, 2023.\nThe Southern Beach Hotel & Resort\, Okinawa\, Japan\nSponsored by the IBS Discrete Mathematics Group\, Korea.\nOrganizers: Seog-Jin Kim\, Sang-il Oum\, Kenta Ozeki\, Hehui Wu.\n\n\n2nd East Asia Workshop on Extremal and Structural Graph Theory\n\nOct. 31-Nov. 4\, 2019.\nHeld at UTOP UBLESS Hotel\, Jeju\, Korea\nSponsored by the IBS Discrete Mathematics Group\, Korea.\nOrganizers: Seog-Jin Kim\, Sang-il Oum\, Kenta Ozeki\, Hehui Wu.\n\n\n1st East Asia Workshop on Extremal and Structural Graph Theory\n\nNov. 30-Dec. 2\, 2018.\nHeld and sponsored by the Shanghai Center for Mathematical Sciences in China\, under the name 2018 SCMS Workshop on Extremal and Structural Graph Theory.\nOrganizers: Ping Hu\, Seog-Jin Kim\, Kenta Ozeki\, Hehui Wu.\n\n\n\n\n\nThursday\nNovember 27\, 2025\n\n\n\n\nTime\nSpeaker\nAffiliation\nTitle\n\n\n\n\n16:00–18:00\n\nRegistration & Discussions\n\n\n\n\n \n\n\nFriday\nNovember 28\, 2025\n\n\n\n\nTime\nSpeaker\nAffiliation\nTitle\n\n\n\n\n09:20–10:00\nJaehoon Kim\nKAIST\nHamilton cycles in pseudorandom graphs: Dirac’s theorem and approximate decompositions\n\n\n10:00–10:30\n\nCoffee Break\n\n\n10:30–11:10\nJie Ma\nUniversity of Science and Technology of China / Tsinghua University\nAn exponential improvement for Ramsey lower bounds\n\n\n11:20–12:00\nShinya Fujita\nYokohama City University\nConnectivity keeping paths containing prescribed vertices in highly connected triangle-free graphs\n\n\n12:00–14:00\n\nLunch Break\n\n\n14:00–14:40\nShun-ichi Maezawa\nNihon University\nTree versus tree of preorder induced by rainbow forbidden subgraphs\n\n\n14:50–15:30\nTony Huynh\nIBS Discrete Mathematics Group\nRainbow triangles and the Erdős–Hajnal problem in projective geometries\n\n\n15:30–15:50\n\nCoffee Break\n\n\n16:30–17:30\n\nProblem Session\n\n\n\n\n \n\n\nSaturday\nNovember 29\, 2025\n\n\n\n\nTime\nSpeaker\nAffiliation\nTitle\n\n\n\n\n09:20–10:00\nXuding Zhu\nZhejiang Normal University\nTBA\n\n\n10:00–10:30\n\nCoffee Break\n\n\n10:30–11:10\nHong Liu\nIBS Extremal Combinatorics and Probability Group\nChromatic\, homomorphism\, blowup thresholds and beyond\n\n\n11:20–12:00\nShohei Satake\nKumamoto University\nTBA\n\n\n12:00–14:00\n\nLunch Break\n\n\n14:00–14:40\nShoichi Tsuchiya\nSenshu University\nOn the number of contractible edges in plane triangulations\n\n\n14:50–15:30\nTuan Tran\nUniversity of Science and Technology of China\nLittlewood-Offord bounds on the symmetric groups and applications\n\n\n15:30–15:50\n\nCoffee Break\n\n\n15:50–16:30\nO-joung Kwon\nHanyang University / IBS Discrete Mathematics Group\nA coarse Erdős–Pósa theorem\n\n\n16:30–17:30\n\nProblem Session\n\n\n18:30–21:00\n\nBanquet\n\n\n\n\n \n\n\nSunday\nNovember 30\, 2025\n\n\n\n\nTime\nSpeaker\nAffiliation\nTitle\n\n\n\n\n10:00–10:40\nJie Han\nBeijing Institute of Technology\nPerturbation of dense graphs\n\n\n10:40–10:50\n\nBreak\n\n\n10:50–11:30\nBoram Park\nSeoul National University\nGraphs avoiding cycles of length 0 modulo 4\n\n\n11:30–12:00\n\nClosing URL:https://dimag.ibs.re.kr/event/2025-east-asia-graph-theory/ LOCATION:Seoul\, Korea CATEGORIES:Workshops and Conferences ORGANIZER;CN="Seog-Jin Kim (%EA%B9%80%EC%84%9D%EC%A7%84)":MAILTO:skim12@konkuk.ac.kr END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20251125T163000 DTEND;TZID=Asia/Seoul:20251125T173000 DTSTAMP:20260416T075424 CREATED:20250929T123857Z LAST-MODIFIED:20251104T141401Z UID:11664-1764088200-1764091800@dimag.ibs.re.kr SUMMARY:Péter Pál Pach\, Product representation of perfect cubes DESCRIPTION:Let $F_{k\,d}(n)$ be the maximal size of a set ${A}\subseteq [n]$ such that the equation \[a_1a_2\cdots a_k=x^d\, \; a_1