기초과학연구원 이산수학그룹
Let $\mathcal F$ be a fixed, finite family of graphs. In the $\mathcal F$-Deletion problem, the input is a graph G and a positive integer k, and the goal is to determine if there exists a set of at most k vertices whose deletion results in a graph that does not contain any graph of …
The notion of asymptotic dimension of metric spaces, introduced by Gromov, describes their large-scale behaviour. Asymptotic dimension of graph families has been recently studied, in particular, by Bonamy et al. who proved that the asymptotic dimension of proper minor-closed graph families is at most two. We will discuss nerve-type theorems for asymptotic dimension. In particular, …
We will discuss classical and recent results about phase transitions in random subgraphs of the hypercube and beyond. The focus will be on the giant component, long cycles, large matchings, and isoperimetric properties.
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 great opportunity for young and aspiring researchers to study topics which are important but not covered during the lectures in the university classes. Website: …
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 property while only communicating with their local network. The key property of a local certification is that if certificates are corrupted, some node in the …
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, namely the first-order model checking problem, and present the definition, some examples, and some basic proof techniques with the example of χ-boundedness. This is based …
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 Erdős-Hajnal conjecture. Roughly, our conjecture states that every colouring of the points of a finite projective geometry of dimension $n$ not containing a fixed …
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 in both matroids. This problem was introduced and solved by Edmonds in the 70s. The importance of matroid intersection stems from the large variety of …
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 (엄상일), IBS Discrete Mathematics Group Jang Soo Kim (김장수), Sungkyunkwan University Seunghyun Seo (서승현), Kangwon National University
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 (서재현), Yonsei University Kyungjin Cho (조경진), POSTECH