기초과학연구원 이산수학그룹
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. We prove that computing an optimal tree-partition is XALP-complete, which is likely to exclude FPT algorithms. However, we prove that computing a tree-partition of approximate …
By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 Pólya asked for which (0, 1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the …
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$ distinct edges contains at least $v+1$ vertices. In 1973, Brown, Erdős and Sós initiated the study of the function $f_r(n,v,e)$ and they proved that $\Omega(n^{\frac{er-v}{e-1}})=f_r(n,v,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil})$. …
A linear $3$-graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices. A linear $3$-graph is called a Steiner triple system if each pair of two distinct vertices belong to a unique edge. A simple greedy algorithm shows that every $n$-vertex Steiner triple system $G$ contains all …
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 classical problems in extremal combinatorics, known as the Erdős-Szekeres problem. In 1935, Erdős and Szekeres famously conjectured that $ES_2(n)=2^{n−2}+1$ holds, which was nearly settled by …
The disjoint paths logic, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate $\mathsf{dp}_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ for $i\in \{1,\ldots, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every …
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 chromatic number; equivalently, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that …
Various types of independent sets have been studied for decades. As an example, the minimum number of maximal independent sets in a connected graph of given order is easy to determine (hint; the answer is written in the stars). When considering this question for twin-free graphs, it becomes less trivial and one discovers some surprising …
The Graphic Travelling Salesman Problem is the problem of finding a spanning closed walk (a TSP walk) of minimum length in a given connected graph. The special case of the Graphic TSP on subcubic graphs has been studied extensively due to their worst-case behaviour in the famous $\frac{4}{3}$-integrality-gap conjecture on the "subtour elimination" linear programming …
I will first introduce the notion of recognisability of languages of terms and then its extensions to sets of relational structures. In a second step, I will discuss relations with decompositions of graphs/matroids and why their MSOL-definability is related to understanding recognisable sets. I will finally explain how to define in MSOL branch-decompositions for finitely …