상일

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...

Basis Number of Graphs Excluding Minors The basis number of a graph $G$ is the minimum $k$ such that the cycle space of $G$ is generated by a family of cycles using each edge at most $k$ times. A classical result of Mac Lane states that pla...

#New_arXiv_paper
*Colin Geniet* and Ugo Giocanti,
Basis Number of Graphs Excluding Minors, 2026.
arxiv.org/abs/2601.05195

Branch-width of connectivity functions is fixed-parameter tractable A connectivity function on a finite set $V$ is a symmetric submodular function $f \colon 2^V \to \mathbb{Z}$ with $f(\emptyset)=0$. We prove that finding a branch-decomposition of width at most $k$ fo...

#New_arXiv_paper
Tuukka Korhonen and *Sang-il Oum*,
Branch-width of connectivity functions is fixed-parameter tractable, 2026.
arxiv.org/abs/2601.04756

Post Image

Daniel Mock gave a talk at the Discrete Math Seminar on an algorithmic framework for showing the fixed-parameter tractability of the dominating set problem and its generalizations

On January 6, 2026, Daniel Mock from RWTH Aachen gave a talk on an…

https://dimag.ibs.re.kr/2026/daniel-mock/

Transducing Linear Decompositions of Tournaments Bojańczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-decompositions of bounded width can be produced by a CMSO transduction. We show that in the cas...

#New_arXiv_paper
*Colin Geniet*, Fatemeh Ghasemi, and Mamadou Moustapha Kanté,
Transducing Linear Decompositions of Tournaments, 2025.
arxiv.org/abs/2601.02999

IBS에서 열리는 겨울학교:
Recent Advances in Cut-Problems on Graphs.
2026년 1월 19일-23일 오전 10시-11시 30분.
www.ibs.re.kr/ecopro/winte...

Post Image

Welcome Eero Räty, Xiaofan Yuan, and Xin Wei, new members of IBS ECOPRO

The IBS Discrete Mathematics Group welcomes Dr. Eero Räty, Dr. Xiaofan Yuan, and Dr. Xin Wei, new research fellows at the IBS Extremal Combinatorics and Probability Group,…

https://dimag.ibs.re.kr/2026/welcome-raty-yuan-wei/

Post Image

Yunbum Kook (국윤범) gave a talk on a faster randomized algorithm for sampling points in a convex body at the Discrete Math Seminar

On December 30, 2025, Yunbum Kook (국윤범) from the Georgia Institute of Technology gave a talk at the Discrete Math Seminar on a…

https://dimag.ibs.re.kr/2025/sampling/

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_arXiv_paper
*Colin Geniet*, *Gunwoo Kim*, and Lucas Meijer,
First-Order Logic and Twin-Width for Some Geometric Graphs, 2025.
arxiv.org/abs/2512.21896

Sphere intersections and incidences over finite fields We bound the number of incidences between points and spheres in finite vector spaces by bounding the sum of the number of points in the pairwise intersections of the spheres. We obtain new incidence b...

#New_accepted_paper
Doowon Koh, Ben Lund, Chuandong Xu, and *Semin Yoo*,
Sphere intersections and incidences over finite fields,
Proc. Amer. Math. Soc., accepted, 2025.
arxiv.org/abs/2509.25997

On Dec 26, 2025, Donggyu Kim from the Georgia Tech, USA gave a talk at the Discrete Math Seminar on defining orthogonal matroids (even delta-matroids) with coefficients in terms of Grassmann-Plücker functions.
"Grassmann-Plücker functions for orthogonal matroids". dimag.ibs.re.kr/2025/orthogo...

Star clusters in independence complexes of hypergraphs We study the concept of star clusters in simplicial complexes, which was introduced by Barmak in 2013, by relating it with the structure of hypergraphs that correspond to the simplicial complexes. Thi...

#New_accepted_paper
*Jinha Kim*,
Star clusters in independence complexes of hypergraphs,
Combinatorica, accepted, 2025.
arxiv.org/abs/2408.14321

#New_published_paper
Stefan Kratsch, Marcin Pilipczuk, *Roohani Sharma*, and Magnus Wahlström,
Applications of flow-augmentation,
Computer Science Review, 60:100869, May 2026.
doi.org/10.1016/j.co...

Post Image

Chi Hoi Yip gave a talk on the maximum size of a clique in Paley graphs and cyclotomic graphs

On December 16, 2025, Chi Hoi Yip from Georgia Institute of Technology gave a talk at the Discrete Math Seminar on the maximum size of a clique in Paley…

https://dimag.ibs.re.kr/2025/chi-hoi-yip-seminar/

#New_accepted_conference_paper
*Roohani Sharma* and Michał Włodarczyk,
Protrusion Decompositions Revisited: Uniform Lossy Kernels For Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors,
STACS 2026 (March 9-13, 2026, Grenoble, France), accepted.