기초과학연구원 이산수학그룹
Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate …
The first course in graph theory usually covers concepts such as matchings, independent sets, colourings, and forbidden subgraphs. Around 2004, Borgs, Chayes, Lovász, Sós, Szegedy, and Vestergombi introduced a very …
The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk, I will sketch a proof …
We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches …
Hadwiger's famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd conjectured the following strengthening of Hadwiger's conjecture: If G is a t-chromatic graph and S⊆V(G) takes all …
A circle graph is an intersection graph of a set of chords of a circle. In this talk, I will describe the unavoidable induced subgraphs of circle graphs with large …
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, …
Let $G=\mathbb{F}_p^n$. Which systems of linear equations $\Psi$ have the property that amongst all subsets of $G$ of fixed density, random subsets minimise the number of solutions to $\Psi$? This …
Let $X$ be a 2-dimensional simplicial complex. Denote by $\text{ex}_{\hom}(n,X)$ the maximum number of 2-simplices in an $n$-vertex simplicial complex that has no sub-simplicial complex homeomorphic to $X$. The asymptotics …
Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i,t_i)_{i=1}^k$ of vertices, the goal of the planar disjoint paths problem is to find …