기초과학연구원 이산수학그룹
A seminal result of Tutte asserts that every 4-connected planar graph is hamiltonian. By Wagner's theorem, Tutte's result can be restated as: every 4-connected graph with no $K_{3,3}$ minor is hamiltonian. In 2018, Ding and Marshall posed the problem of characterizing the minor-minimal 3-connected non-hamiltonian graphs. They conjectured that every 3-connected non-hamiltonian graph contains a …
Two celebrated extensions of Helly's theorem are the Fractional Helly theorem of Katchalski and Liu (1979) and the Quantitative Volume theorem of Barany, Katchalski, and Pach (1982). Improving on several recent works, we prove an optimal combination of these two results. We show that given a family $F$ of $n$ convex sets in $\mathbb{R}^d$ such …
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 …