기초과학연구원 이산수학그룹
A well-known conjecture of Burr and Erdős asserts that the Ramsey number $r(Q_n)$ of the hypercube $Q_n$ on $2^n$ vertices is of the order $O(2^n)$. In this paper, we show that …
Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender, Cornelissen, and van der Wegen, we consider the parameterized problem of computing a decomposition. …
For fixed integers $r\ge 3, e\ge 3$, and $v\ge r+1$, let $f_r(n,v,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ …
Finding the smallest integer $N=ES_d(n)$ such that in every configuration of $N$ points in $\mathbb{R}^d$ in general position, there exist $n$ points in convex position is one of the most …
Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded …
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 …
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 …
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 …
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 …