기초과학연구원 이산수학그룹
Given a $k$-uniform hypergraph $H$, the Ramsey number $R(H;q)$ is the smallest integer $N$ such that any $q$-coloring of the edges of the complete $k$-uniform hypergraph on $N$ vertices contains …
A graph $G$ is (list, DP) $k$-critical if the (list, DP) chromatic number is $k$ but for every proper subgraph $G'$ of $G$, the (list, DP) chromatic number of $G'$ …
Robertson and Seymour introduced branch-width as a connectivity invariant of graphs in their proof of the Wagner conjecture. Decompositions based on this invariant provide a natural framework for implementing dynamic-programming …
Vertex Cover is perhaps the most-studied problem in parameterized complexity that frequently serves as a testing ground for new concepts and techniques. In this talk, I will focus on a …
We consider a continuous model of graphs, introduced by Dearing and Francis in 1974, where each edge of G to be a unit interval, giving rise to an infinite metric …
Given a $k$-uniform hypergraph $F$, its Turán density $\pi(F)$ is the infimum over all $d\in $ such that any $n$-vertex $k$-uniform hypergraph $H$ with at least $d\binom{n}{k}+o(n^k)$ edges contains a …
Consider a general Turan-type problem on hypergraphs. Let $\mathcal{F}$ be a family of $k$-subsets of $$ that does not contain sets $F_1, \ldots, F_s$ satisfying some property $P$. We show …
Let $F_{k,d}(n)$ be the maximal size of a set ${A}\subseteq $ such that the equation \ has no solution with $a_1,a_2,\ldots,a_k\in A$ and integer $x$. Erdős, Sárközy and T. Sós …
Extremely sparse random binary matrices tend to be singular, due to the likely presence of "local combinatorial dependencies" such as all-zero columns or pairs of identical columns. We discuss this …
We present a dynamic data structure that maintains a tree decomposition of width at most 9k+8 of a dynamic graph with treewidth at most k, which is updated by edge …