상일

A lower bound on the number of edges in DP-critical graphs A graph $G$ is $k$-critical (list $k$-critical, DP $k$-critical) if $χ(G)= k$ ($χ_\ell(G)= k$, $χ_\mathrm{DP}(G)= k$) and for every proper subgraph $G'$ of $G$, $χ(G')<k$ ($χ_\ell(G')< k$, $χ_\mathrm{...

#New_accepted_paper
Peter Bradshaw, *Ilkyoo Choi*, Alexandr Kostochka, and Jingwei Xu,
A lower bound on the number of edges in DP-critical graphs,
J. Combin. Theory Ser. B, accepted, 2026.
arxiv.org/abs/2409.00937

József Balogh gave a talk on decomposing (or covering) the edge set of a graph into (or by) cliques at the Discrete Math Seminar On March 12, 2026, József Balogh from the University of Illinois at Urbana-Champaign gave a talk on decomposing the edge set of a graph into edge sets of clliques or covering by edge sets of cliques at the Discrete Math Seminar. The title of his talk was "Clique covers and decompositions of cliques of graphs".

József Balogh gave a talk on decomposing (or covering) the edge set of a graph into (or by) cliques at the Discrete Math Seminar

On March 12, 2026, József Balogh from the University of Illinois at Urbana-Champaign gave a talk on decomposing the edge set of a graph into edge sets of clliques or…

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining $0$ on the empty set. For a connectivity function $f$ on an $n$-element set $V$...

#New_arXiv_paper
*Sang-il Oum* and Marek Sokołowski,
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions, 2026.
arxiv.org/abs/2603.10710

Dario Cavallaro gave a talk on well-quasi-ordering of Eulerian digraphs under (strong) immersion at the Discrete Math Seminar On March 10, 2026, Dario Cavallaro from the TU Berlin gave a talk at the Discrete Math Seminar on well-quasi-ordering of Eulerian digraphs under (strong) immersion. The title of his talk was "Well-quasi-ordering Eulerian directed graphs by (strong) immersion".

Dario Cavallaro gave a talk on well-quasi-ordering of Eulerian digraphs under (strong) immersion at the Discrete Math Seminar

On March 10, 2026, Dario Cavallaro from the TU Berlin gave a talk at the Discrete Math Seminar on well-quasi-ordering of Eulerian digraphs under (strong) immersion. The…

New Strides Made on Deceptively Simple ‘Lonely Runner’ Problem | Quanta Magazine A straightforward conjecture about runners moving around a track turns out to be equivalent to many complex mathematical questions. Three new proofs mark the first significant progress on the problem ...

As runners move around a track, are they bound to end up “lonely”? Three new proofs suggest the answer is yes — the first significant progress on the problem in decades.
www.quantamagazine.org/new-strides-...

Post Image

Chính T. Hoàng gave a survey talk on graph coloring and forbidden induced subgraphs at the Discrete Math Seminar

On March 3, 2026, Chính T. Hoàng from the Wilfrid Laurier University, Waterloo, Canada gave a survey talk on graph coloring and…

https://dimag.ibs.re.kr/2026/chinh-t-hoang-seminar/

Variants of Merge-Width and Applications Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of several alternative def...

#New_arXiv_paper
Karolina Drabik, Maël Dumas, *Colin Geniet*, Jakub Nowakowski, Michał Pilipczuk, and Szymon Toruńczyk,
Variants of Merge-Width and Applications, 2026.
arxiv.org/abs/2602.23867

Triangulated spheres with holes in triangulated surfaces Let $\mathbb{S}_h$ denote a sphere with $h$ holes. Given a triangulation $G$ of a surface $\mathbb{M}$, we consider the question of when $G$ contains a spanning subgraph $H$ such that $H$ is a triangu...

#New_accepted_paper
Katie Clinch, Sean Dewar, Niloufar Fuladi, *Maximilian Gorsky*, *Tony Huynh*, Eleftherios Kastis, Atsuhiro Nakamoto, Anthony Nixon, and Brigitte Servatius,
Triangulated spheres with holes in triangulated surfaces,
Discrete Comput. Geom., accepted, 2026.
arxiv.org/abs/2410.04450

Towers and Bratteli-Vershik systems in Fibonacci-like unimodal maps For a class of Fibonacci-like unimodal maps, the restriction to the $ω$-limit set of the unique turning point defines a minimal Cantor system. We construct these Cantor sets geometrically using a nest...

#New_arXiv_paper
Jorge Olivares-Vinales and *Semin Yoo*,
Towers and Bratteli-Vershik systems in Fibonacci-like unimodal maps, 2026.
arxiv.org/abs/2602.21623

Shifted multiplicative subgroups are not ratio sets In a recent breakthrough, Kalmynin proved a conjecture of Lev--Sonn and a conjecture of Sárközy on additive decompositions of multiplicative subgroups of a prime field. In this paper, we prove a multi...

#New_arXiv_paper
Seoyoung Kim, Chi Hoi Yip, and *Semin Yoo*,
Shifted multiplicative subgroups are not ratio sets, 2026.
arxiv.org/abs/2602.20919

Post Image

Marek Sokołowski gave a talk on a new parallel algorithm computing single-source shortest paths in directed graphs at the Discrete Math Seminar

On February 24, 2026, Marek Sokołowski from the Max Planck Institute of Informatics gave a talk at…

https://dimag.ibs.re.kr/2026/marek-sokolowski-seminar/

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed as a counterpoint to...

#New_arXiv_paper
*Colin Geniet*, Aliénor Goubault-Larrecq, and Kévin Perrot,
Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions, 2026.
arxiv.org/abs/2602.18240

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications A signed tree model of a graph $G$ is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of $G$, together with 2-colored edges $xy$, call...

#New_arXiv_paper
Édouard Bonnet, *Colin Geniet*, *Eun Jung Kim*, and Sungmin Moon,
Fast shortest path in graphs with sparse signed tree models and applications, 2026.
arxiv.org/abs/2602.16605

On a variant of dichromatic number for digraphs with prescribed sets of arcs In this paper, we consider a variant of dichromatic number on digraphs with prescribed sets of arcs. Let $D$ be a digraph and let $Z_1, Z_2$ be two sets of arcs in $D$. For a subdigraph $H$ of $D$, le...

#New_accepted_paper
*O-joung Kwon* and Xiaopan Lian,
On a variant of dichromatic number for digraphs with prescribed sets of arcs,
Graphs and Combinatorics, accepted, 2026.
arxiv.org/abs/2307.05897

Post Image

Seonghun Park (박성훈) gave a talk on formalizing the flag algebra in the lean theorem prover

On February 10, 2026, Seonghun Park (박성훈) from KAIST gave a talk on formalizing the flag algebra introduced by Alexander Razborov in the lean theorem…

https://dimag.ibs.re.kr/2026/seonghun-park-flag-algebra/

First-Order Logic and Twin-Width for Some Geometric Graphs For some geometric graph classes, tractability of testing first-order formulas is precisely characterised by the graph parameter twin-width. This was first proved for interval graphs among others in [...

#New_accepted_conference_paper
*Colin Geniet*, *Gunwoo Kim*, and Lucas Meijer,
First-Order Logic and Twin-Width for Some Geometric Graphs,
In the Proceedings of the 42nd International Symposium on Computational Geometry (SoCG 2026), accepted, 2026.
arxiv.org/abs/2512.21896

On non-planar, cycle-conformal graphs A graph $G$ is called matching covered if all of its edges are contained in some perfect matching of $G$. Furthermore, a cycle $C \subseteq G$ is called conformal if $G - V(C)$ has a perfect matching ...

#New_arXiv_paper
*Maximilian Gorsky* and Clemens Kuske,
On non-planar, cycle-conformal graphs, 2026.
arxiv.org/abs/2602.07331

Post Image

Xiaofan Yuan gave a talk on the minimum color-degree condition for having a rainbow path at the Discrete Math Seminar

On February 3, 2026, Xiaofan Yuan from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math…

https://dimag.ibs.re.kr/2026/xiaofan-yuan-rainbow/

The price of homogeneity is polynomial We provide explicit and polynomial bounds for the Homogeneous Wall Lemma which occurred for the first time implicitly in the $13$th entry of Robertson and Seymour's Graph Minors Series [JCTB 1990] and...

#New_arXiv_paper
*Maximilian Gorsky*, Michał T. Seweryn, and Sebastian Wiederrecht,
The price of homogeneity is polynomial,
2026.
arxiv.org/abs/2602.01882

Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes Let $\mathcal{F}$ be a family of graphs, and let $p,r$ be nonnegative integers. The \textsc{$(p,r,\mathcal{F})$-Covering} problem asks whether for a graph $G$ and an integer $k$, there exists a set $D...

#New_accepted_paper
*Jungho Ahn*, *Jinha Kim*, and *O-joung Kwon*,
Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes,
J. Comput. System Sci., accepted, 2026.
arxiv.org/abs/2207.06660

Post Image

Welcome Hyunsung Choi (최현성), a new graduate student of the IBS Discrete Mathematics Group

The IBS Discrete Mathematics Group welcomes Hyunsung Choi (최현성), a new graduate student of the Discrete Mathematics Group from February 1, 2026. He received…

http://dimag.ibs.re.kr/2026/welcome-hyunsung-choi/

On a weaker notion of cross $t$-intersecting families We prove that if two families $\mathcal{F} \subseteq \binom{[n]}{k}$ and $\mathcal{F}' \subseteq \binom{[n]}{k'}$ satisfy $\sum_{1 \leq i, j \leq \ell} \lvert F_i \cap F_j' \rvert \geq \ell^2t - \ell ...

#New_arXiv_paper
Jiangdong Ai, Ming Chen, *Seokbeom Kim*, and Hyunwoo Lee,
On a weaker notion of cross t-intersecting families, 2025.
arxiv.org/abs/2601.20516

Post Image

Daniel Dadush gave a talk on a strongly polynomial-time algorithm to solve linear programming problems with at most two non-zero entries per each row or each column at the Discrete Math Seminar

On January 27, 2025, Daniel Dadush from CWI gave a…

https://dimag.ibs.re.kr/2026/daniel-dadush-seminar/

Product representations of polynomials over finite fields Erdős, Sárközy, and Sós studied the asymptotics of the maximum size of a subset of $\{1,2,\ldots, N\}$ such that it does not contain $k$ distinct elements whose product is a perfect square. More gener...

#New_arXiv_paper
Hyunwoo Lee, Chi Hoi Yip, and *Semin Yoo*,
Product representations of polynomials over finite fields, 2025.
arxiv.org/abs/2601.16657

Alt - AI Lecture Notetaker Transform your lectures into organized, searchable notes with AI. Join the waitlist for early access.

“KAIST 학생이 직접 쓰려고 만든 AI 강의 필기앱
# 10,000시간을 써도 무료⏤ 서버, API 비용이 안들기 때문에 가능합니다. 결제도 안 붙였어요.
# 로컬 AI⏤ 서버가 없기 때문에 인터넷이 필요없어요.
# 철저한 보안⏤모든 내용은 사용자 PC에만 저장됩니다.
# 실시간 번역“
www.altalt.io/ko

Paley-type matrices and $1$-factorizations of complete graphs Ball, Ortega--Moreno, and Prodromou asked whether, for every odd prime $p$, one can find a $1$-factor of the complete graph $K_{p+1}$ with some arithmetic restrictions related to quadratic residues. T...

#New_arXiv_paper
Chi Hoi Yip and *Semin Yoo*,
Paley-type matrices and 1-factorizations of complete graphs, 2026.
arxiv.org/abs/2601.12250

Post Image

Tomáš Masařík gave a talk at the Discrete Math Seminar on finding a balanced separator in an H-minor-free graph in linear time

On January 20, 2026, Tomáš Masařík from the University of Warsaw, Poland, gave a talk on a linear-time algorithm to…

https://dimag.ibs.re.kr/2026/tomas-masarik-seminar/

Erdős-Pósa property of $A$-paths in unoriented group-labelled graphs We characterize the obstructions to the Erdős-Pósa property of $A$-paths in unoriented group-labelled graphs. As a result, we prove that for every finite abelian group $Γ$ and for every subset $Λ$ of ...

#New_accepted_paper
*O-joung Kwon* and Youngho Yoo,
Erdős-Pósa property of A-paths in unoriented group-labelled graphs,
Combinatorica, accepted, 2026.
arxiv.org/abs/2411.05372

Post Image

Ferdinand Ihringer gave a talk at the Discrete Math Seminar on low-degree Boolean functions and applications of vector space Ramsey numbers

On January 13, 2026, Ferdinand Ihringer from the Southern University of Science and Technology, China gave a…

https://dimag.ibs.re.kr/2026/ferdinand-ihringer/

#New_accepted_paper
P. S. Ardra, R. Krithika, Saket Saurabh, and *Roohani Sharma*,
Balanced Substructures in Bicolored Graphs,
Theoret. Comput. Sci., accepted, 2026.
doi.org/10.1016/j.tc...