기초과학연구원 이산수학그룹
The fractional Helly theorem is a simple yet remarkable generalization of Helly's classical theorem on the intersection of convex sets, and it is of considerable interest to extend the fractional Helly …
Pósa's theorem states that any graph G whose degree sequence $d_1\leq \dots \leq d_n$ satisfies $d_i \geq i+1$ for all $i< n/2$ has a Hamilton cycle. This degree condition is …
A weak order is a way to rank n objects where ties are allowed. Weak orders have applications in diverse areas such as linguistics, designing combination locks, and even in …
Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number, $\chi_P(G)$, (the minimum number of colors needed for an online …
For given graphs $G$ and $F$, the Turán number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Briggs and Cox introduced a …
Oftentimes in chromatic graph theory, precoloring techniques are utilized in order to obtain the desired coloring result. For example, Thomassen's proof for 5-choosability of planar graphs actually shows that two adjacent …
We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be …
I will introduce Kazhdan-Lusztig polynomials of matroids and survey combinatorial and geometric theories built around them. The focus will be on the conjecture of Gedeon, Proudfoot, and Young that all …
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number …
Let $X$ be a real random variable; a typical anti-concentration inequality asserts that (under certain assumptions) if an interval $I$ has small length, then $\mathbb{P}(X\in I)$ is small, regardless the …