2025 Korean Student Combinatorics Workshop (KSCW2025: 2025 조합론 학생 워크샵)

20 Aug 2025, 12:00 → 24 Aug 2025, 18:00 Asia/Seoul

더케이호텔 경주

2025KSCW는 조합론을 공부하는 한국 학생 및 박사후연구원들이 서로 친목을 다지고 공동 연구를 진행할 수 있는 기틀을 마련하는 것을 목적으로 하는 워크샵입니다.

• 학부생들의 참여를 환영합니다!
• 신청 인원이 예상 수를 초과할 경우 조기 마감될 수 있으며, 신청하신 분들께 메일로 참석 가능 여부를 추후 안내해드립니다.
• 학부생 및 대학원생 참가자에게는 지도교수 확인서 제출을 요청드릴 수 있습니다.

 

현재 지원이 마감되었습니다.

프로그램 개요

• 미해결 문제를 서로 공유하고 선정된 문제들로 조를 편성하여 문제를 해결
• 참가자들의 기여 강연 및 박사후연구원들의 초청 강연

KSCW 2025 booklet (250816).pdf

Wednesday, 20 August

17:00 → 18:50 Registration

19:00 → 21:00 Dinner

Thursday, 21 August

09:30 → 10:50 Opening & Introduction

11:00 → 11:50 Invited talks

11:00 Oriented Matroids: Scope & Perspectives

This is a very brief introduction to oriented matroids based on personal recollection, with hope that the theory gets wider attention from younger generation of mathematics in Korea.

Speaker: Seunghun Lee (IBS DIMAG)

12:00 → 13:20 Lunch

13:30 → 16:20 Open Problem Session

16:30 → 18:50 Group Discussion

19:00 → 21:00 Dinner

Friday, 22 August

09:30 → 10:20 Contributed talks

09:30 Unifying Islands of Tractability for Maximum Independent Set

The Maximum Independent Set (MIS) problem is NP-complete and remains so for every minor-closed graph class that includes all planar graphs (Garey and Johnson [SIAM J. Appl. Math.'77]). On the other hand, due to the Grid Theorem of Robertson and Seymour [JCTB'95], every minor-closed graph class that excludes a planar graph has bounded treewidth, and MIS can be solved in polynomial time on such graph classes. A drawback of this result is that such graph classes are necessarily sparse. Since MIS can be efficiently solved on dense bipartite graphs, there has been interest in extending the tractability of MIS to larger graph classes.
I will provide an overview of these attempts and introduce a new parameter called odd cycle packing (OCP)-treewidth, which unifies the tractability of MIS on the classes of bounded odd cycle packing (OCP) number and bounded bipartite treewidth.

This is based on joint work with Mujin Choi, Maximilian Gorsky, Caleb McFarland, Sebastian Wiederrecht.

Speaker: Gunwoo Kim (KAIST & IBS DIMAG)

10:30 → 11:50 Group Discussion

12:00 → 13:20 Lunch

13:30 → 14:20 Invited talks

13:30 Things I worry about as a Postdoc

In this talk, I’ll share a few of these thoughts, from research focus to future planning, in the hope that they resonate with others in similar stages. There won’t be any magic answers, but maybe a few ideas that help make the uncertainty a bit more manageable.

Speaker: Hojin Chu (KIAS)

14:30 → 15:50 Group Discussion

19:00 → 21:00 Dinner

Saturday, 23 August

09:30 → 10:20 Contributed talks

09:30 Approximation Algorithm for the Geometric Multimatching Problem

Matching is one of the most fundamental combinatorial objects in both graph theory and combinatorial optimization. Moreover, a lot of variants of have been studied in both exact and approximation settings. In the first part of my talk, I will present several classical graph matching algorithms and illustrate some intuitions and techniques behind them.

Then I will focus on the geometric setting. Suppose we are given a set of points in a metric space, and we are asked to find a matching between them. Here, our underlying graph can be defined as a complete graph. This geometric matching problem provides both theoretical insights and real-world applications. In the second part of my talk, I will cover geometric variants of the aforementioned matching-like problems. This part shows that geometric tools can significantly improve the running time of the classical graph matching algorithms.

Speaker: Shinwoo An (POSTECH)

10:30 → 11:50 Group Discussion

12:00 → 13:20 Lunch

13:30 → 14:20 Contributed talks

13:30 Linear-Time Computation of the Frobenius Normal Form for Symmetric Toeplitz Matrices via Graph-Theoretic Decomposition

We introduce a linear-time algorithm for computing the Frobenius normal form (FNF) of symmetric Toeplitz matrices by utilizing their inherent structural properties through a graph-theoretic approach. Previous results of the authors established that the FNF of a symmetric Toeplitz matrix is explicitly represented as a direct sum of symmetric irreducible Toeplitz matrices, each corresponding to connected components in an associated weighted Toeplitz graph. Conventional matrix decomposition algorithms, such as Storjohann's method (1998), typically have cubic-time complexity. Moreover, standard graph component identification algorithms, such as breadth-first or depth-first search, operate linearly with respect to vertices and edges, translating to quadratic-time complexity solely in terms of vertices for dense graphs like weighted Toeplitz graphs. Our method uniquely leverages the structural regularities of weighted Toeplitz graphs, achieving linear-time complexity strictly with respect to vertices through two novel reductions: the α-type reduction, which eliminates isolated vertices, and the β-type reduction, applying residue class contractions to achieve rapid structural simplifications while preserving component structure. These reductions facilitate an efficient recursive decomposition process that yields linear-time performance for both graph component identification and the resulting FNF computation. This work highlights how structured combinatorial representations can lead to significant computational gains in symbolic linear algebra.

Speaker: Homoon Ryu (Ajou University)

14:30 → 18:50 Group Discussion

19:00 → 21:00 Dinner

Sunday, 24 August

09:30 → 10:40 Contributed talks

09:30 Progress on Covering a Hexagon with Seven Unit Triangles

John Conway and Alexander Soifer showed that an equilateral triangle T with side length n+ε can be covered using n²+2 unit equilateral triangles. They also conjectured that using n²+1 triangles is not enough.

As a more approachable version of this problem, we ask: Can a regular hexagon with side length 1+ε be covered by just 7 unit equilateral triangles? This simplified question reflects core aspects of the Conway--Soifer conjecture.

In this talk, I will present our progress on this problem, including our use of computer-assisted search and the insights it led to. This is joint work with Jineon Baek.

Speaker: Jeewon Kim (KAIST)

10:10 Capturing Additive Structures via Gowers Norms: From Arithmetic Progression Counts to Inverse Theorems

The Gowers uniformity norm has played a significant role in additive combinatorics as a measure of randomness associated with solution sets of certain linear configurations. In this talk, I introduce the notion of Gowers uniformity norms and demonstrate how they capture additive structures in a given set of integers. Gowers norms capture additive structures both through k-term arithmetic progression counts and through their connection to polynomial Freiman–Ruzsa via Gowers inverse theorems. I present applications of Gowers norms in both directions.

Speaker: Jihyo Chae (Yonsei University)

10:50 → 11:50 Final Discussion & Progress Report

12:00 → 13:20 Lunch