Name: 2025 Korean Student Combinatorics Workshop (KSCW2025: 2025 조합론 학생 워크샵)
Start: 2025-08-20T12:00:00+09:00
End: 2025-08-24T18:00:00+09:00
Location: 더케이호텔 경주

Wednesday, 20 August
- 17:00 → 18:50
  
  Registration 1h 50m
- 19:00 → 21:00
  
  Dinner
Thursday, 21 August
- 09:30 → 10:50
  
  Opening & Introduction 1h 20m
- 11:00 → 11:50
  Invited talks
  - 11:00
    
    Oriented Matroids: Scope & Perspectives 50m
    
    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 2h 50m
- 16:30 → 18:50
  
  Group Discussion 2h 20m
- 19:00 → 21:00
  
  Dinner
Friday, 22 August
- 09:30 → 10:20
  Contributed talks
  - 09:30
    
    Unifying Islands of Tractability for Maximum Independent Set 50m
    
    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 1h 20m
- 12:00 → 13:20
  
  Lunch
- 13:30 → 14:20
  Invited talks
  - 13:30
    
    Things I worry about as a Postdoc 50m
    
    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 1h 20m
- 19:00 → 21:00
  
  Dinner
Saturday, 23 August
- 09:30 → 10:20
  Contributed talks
  - 09:30
    
    Approximation Algorithm for the Geometric Multimatching Problem 50m
    
    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 1h 20m
- 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 50m
    
    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 4h 20m
- 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 30m
    
    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 30m
    
    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 1h
- 12:00 → 13:20
  
  Lunch