기초과학연구원 이산수학그룹
The 2025 Summer School on Combinatorics and Algorithms is a venue for students and early-career researchers to learn selected topics in theoretical computer science and discrete mathematics. It will be …
A local certification of a graph property is a protocol in which nodes are given “certificates of a graph property” that allow the nodes to check whether their network has this …
This talk is an introduction to the recent notion of merge-width, proposed by Jan Dreier and Szymon Torúnczyk. I will give an overview of the context and motivations for merge-width, …
We formulate a geometric version of the Erdős-Hajnal conjecture that applies to finite projective geometries rather than graphs. In fact, we give a natural extension of the 'multicoloured' version of …
The matroid intersection problem is a fundamental problem in combinatorial optimization. In this problem we are given two matroids and the goal is to find the largest common independent set …
Website: https://cw2025.combinatorics.kr Invited Speakers Dongsu Kim (KAIST) Eun Jung Kim (KAIST) O-joung Kwon (Hanyang University) Ae Ja Lee (Pennsylvania State University) Zhicong Lin (Shandong University) Organizing Committee Sang-il Oum (엄상일), …
Venue The K-Hotel Gyeongju Website https://indico.ibs.re.kr/e/kscw2025 Organizers Seokbeom Kim (김석범), KAIST and IBS Discrete Mathematics Group Hyunwoo Lee (이현우), KAIST and IBS Extremal Combinatorics and Probability Group Jaehyeon Seo (서재현), …
We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$, there exists an integer $t=t(k,H)$ so that every graph $G$ either …
Lehel's conjecture states that every 2-edge-colouring of the complete graph $K_n$ admits a partition of its vertices into two monochromatic cycles. This was proven for sufficiently large n by Luczak, …
We will discuss two symmetry breaking parameters: distinguishing number and fixing number. Despite being introduced independently, they share meaningful connections. In particular, we show that if a tree is 2-distinguishable …