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

Session

Contributed talks

22 Aug 2025, 09:30

더케이호텔 경주

5. Unifying Islands of Tractability for Maximum Independent Set

Gunwoo Kim (KAIST & IBS DIMAG)

22/08/2025, 09:30

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

8. Approximation Algorithm for the Geometric Multimatching Problem

Shinwoo An (POSTECH)

23/08/2025, 09:30

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

9. Linear-Time Computation of the Frobenius Normal Form for Symmetric Toeplitz Matrices via Graph-Theoretic Decomposition

Homoon Ryu (Ajou University)

23/08/2025, 13:30

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

7. Progress on Covering a Hexagon with Seven Unit Triangles

Jeewon Kim (KAIST)

24/08/2025, 09:30

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

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

Jihyo Chae (Yonsei University)

24/08/2025, 10:10

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