@ibsdimag profile picture
IBS Discrete Mathematics Group (기초과학연구원 이산수학그룹) @ibsdimag

Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, Korea

Joined October 2018
  • Tweets 1,046
  • Following 1
  • Followers 235
424 Photos and videos
On June 9, 2026, J. Pascal Gollin from University of Primorska gave a talk at the Discrete Math Seminar on the existence of a balanced separator dominated by a small number of vertices in a graph excluding a wheel as an induced minor. dimag.ibs.re.kr/2026/wheel-i…
1
56
#New_arXiv_paper Maria Chudnovsky, Linda Cook, James Davies, *Seokbeom Kim*, and *Sang-il Oum*, On the chromatic number of the union of comparability graphs, 2026. arxiv.org/abs/2606.09415

On the chromatic number of the union of comparability graphs

Resolving in a strong sense an old problem of Gyárfás from the 1980s on the union of two perfect graphs, we prove that for every pair of positive integers $d$ and $k$, there is a graph $G$...

arxiv.org
1
1,684
#New_accepted_paper Matthew Baker, Changxin Ding, and *Donggyu Kim*, The Jacobian of a regular orthogonal matroid and torsor structures on spanning quasi-trees of ribbon graphs, Adv. Math., accepted, 2026. arxiv.org/abs/2501.08796

The Jacobian of a regular orthogonal matroid and torsor structures...

Previous work of Chan--Church--Grochow and Baker--Wang shows that the set of spanning trees in a plane graph $G$ is naturally a torsor for the Jacobian group of $G$. Informally, this means that...

arxiv.org
2
1
453
On June 2, 2026, Maria Chudnovsky from Princeton University gave a talk on bounding treewidth of n-vertex graphs excluding fixed induced minors as a function of n at the Discrete Math Seminar. The title of her talk was "Induced minors and treewidth". dimag.ibs.re.kr/2026/treewid…
1
1
341
#New_arXiv_paper Seewoo Lee, Byung-Hak Hwang, Hyojae Lim, Jihoon Hyun,*Ilkyoo Choi*,Yeachan Park,Jineon Baek, Hyukpyo Hong,Keewoo Lee,Jaeseong Heo,Hyungryul Baik, Chul-hee Lee, Kyu-Hwan Lee, Lean-GAP: A Dataset of Formalized Graduate Algebra Problems, 2026 arxiv.org/abs/2606.02588

Lean-GAP: A Dataset of Formalized Graduate Algebra Problems

We present Lean-GAP (Lean-Graduate Agebra Problems), 430 formalized graduate-level algebra problems from the textbook Abstract Algebra by Dummit and Foote. We develop a scalable pipeline...

arxiv.org
4
3
641
On May 26, 2026, Fernanda Rivera Omaña from the University of Waterloo gave a talk at the Discrete Math Seminar on the Erdős-Pósa property for matroid minors. The title of her talk was "Erdős-Pósa theorem for matroids". dimag.ibs.re.kr/2026/fernand…
50
#New_published_paper Archontia C. Giannopoulou and *Sebastian Wiederrecht*, Two disjoint alternating paths in bipartite graphs: conformal crosses, Combinatorica, 46:19, May 2026. doi.org/10.1007/s00493-026-0…

Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses

Combinatorica - A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B. A conformal cross over some cycle C...

link.springer.com
1
1
307
On May 19, 2026, Xavier Goaoc from Université de Lorraine gave a talk at the Discrete Math Seminar on a tree decomposition of the chirotopes of a planar point set and its application to counting triangulations of a chirotope. dimag.ibs.re.kr/2026/xavier-…
2
1
314
The IBS Discrete Mathematics Group welcomes Arnaud Patey, a new graduate student of the Discrete Mathematics Group from May 18, 2026 to July 17, 2026. He is a MS student at ENS Rennes. dimag.ibs.re.kr/2026/welcome…
1
550
#New_arXiv_paper Dario Cavallaro, *Maximilian Gorsky*, Stephan Kreutzer, Dimitrios M. Thilikos, and Sebastian Wiederrecht, Optimal Bounds for the k-Disjoint Paths Problem, 2026. arxiv.org/abs/2605.14902

Optimal Bounds for the k-Disjoint Paths Problem

The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Paths, Rooted Minor...

arxiv.org
2
5
373
#New_arXiv_paper *Mujin Choi*, Tuukka Korhonen, and *Sang-il Oum*, Branch-width of represented matroids in matrix multiplication time, 2026. arxiv.org/abs/2605.14428

Branch-width of represented matroids in matrix multiplication time

For an $n$-element matroid $M$ given by an $n \times n$ matrix representation over a finite field $\mathbb F$ and an integer $k$, we present an $(O_{k,\mathbb F}(n^2) O(n^ω))$-time algorithm...

arxiv.org
1
1
302
On May 12, 2026, Benjamin Duhamel from ENS de Lyon gave a talk at the Discrete Math Seminar on characterizing forests F such that forbidding a biclique and an induced minor isomorphic to F implies bounded path-width. “Excluding a forest induced minor“. dimag.ibs.re.kr/2026/excludi…
1
1
312
#New_arXiv_paper Tung H. Nguyen and *Sang-il Oum*, Ramsey-type χ-bounds for χ-bounded graph classes, 2026. arxiv.org/abs/2605.08848

Ramsey-type $χ$-bounds for $χ$-bounded graph classes

We prove that for every path $P$, the class of graphs with no induced $P$ and no induced four-cycle $C_4$ is linearly $χ$-bounded. More generally, we ask for which pairs $\{T,H\}$ where $T$ is...

arxiv.org
1
1,258
#New_arXiv_paper *Maximilian Gorsky*, Kevin Hendrey, and *Tony Huynh*, The Erdős-Pósa property for prime-length cycles fails (and beyond), 2026. arxiv.org/abs/2605.04938

The Erdős-Pósa property for prime-length cycles fails (and beyond)

We prove that for every $t \in \mathbb{N}$, prime-length cycles do not have the $\frac{1}{t}$-integral Erdős-Pósa property, even when restricted to planar graphs. We in fact prove a more...

arxiv.org
2
1
327
#New_accepted_paper Katie Clinch, Dániel Garamvölgyi, John Haslegrave, Tony Huynh, Jan Legerský, and Anthony Nixon, Stable cuts, NAC-colourings and flexible realisations of graphs, J. Graph Theory, accepted, 2026. arxiv.org/abs/2412.16018

Stable cuts, NAC-colourings and flexible realisations of graphs

A (2-dimensional) realisation of a graph $G$ is a pair $(G,p)$, where $p$ maps the vertices of $G$ to $\mathbb{R}^2$. A realisation is flexible if it can be continuously deformed while keeping the...

arxiv.org
1
1
305
On May 6, 2026, Maximilian Gorsky from @ibsdimag gave a talk at the Discrete Math Seminar on a new algorithm for k-disjoint paths problem with an explicit running time. "The Disjoint Paths Problem lies in the Oort cloud of algorithms" dimag.ibs.re.kr/2026/maximil…
54
#New_arXiv_paper *Ilkyoo Choi*, Hojin Chu, Ringi Kim, and Boram Park, Existence of cycles of length divisible by 3 or 4, 2026. arxiv.org/abs/2605.02731

Existence of cycles of length divisible by 3 or 4

Dean conjectured that for each integer $k \ge 3$, every graph with minimum degree at least $k$ has a cycle whose length is divisible by $k$; this conjecture is known to be true for all $k\neq 5$....

arxiv.org
2
3
322
On April 28, 2026, Xin Wei (魏歆) from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on the maximum size of a t-perfect hash family over an alphabet of size q. “Separating hash families with large universe" dimag.ibs.re.kr/2026/xin-wei…
1
467
#New_accepted_paper Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, *O-joung Kwon*, *Sang-il Oum*, and Daniël Paulusma, Computing pivot-minors, Algorithmica, accepted, 2026. arxiv.org/abs/2311.04656

Computing pivot-minors

A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of...

arxiv.org
1
404
#New_arXiv_paper *Andreas Holmsen*, Attila Jung, Balázs Keszegh, Dániel G. Simon, and Gábor Tardos, Piercing all maximum cliques in hypergraphs, 2026. arxiv.org/abs/2604.21588

Piercing all maximum cliques in hypergraphs

Graphs whose maximum clique size exceeds half of the total number of vertices satisfy a classical property: the family of their maximum sized cliques can be pierced by a single vertex. This result...

arxiv.org
2
1
379
Load more