기초과학연구원 이산수학그룹
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 …
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 …
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. …
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, …
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 …
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, …