기초과학연구원 이산수학그룹
We prove the existence of a computable function $f\colon\mathbb{N}\to\mathbb{N}$ such that for every integer $k$ and every digraph $D$ either contains a collection $\mathcal{C}$ of $k$ directed cycles of even …
There has been a raising interest on the study of perfect matchings in uniform hypergraphs in the past two decades, including extremal problems and their algorithmic versions. I will introduce …
Amazon drivers hit the road every day, each taking a Prime van in a traveling salesman problem tour through 150 or more customer stops. But even a whisper of the …
We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak, that for every graph $H$, there is a polynomial $p$ such that for every positive integer $s$, every …
Let $\mathcal{G}$ and $\mathcal{H}$ be minor-closed graphs classes. The class $\mathcal{H}$ has the Erdős-Pósa property in $\mathcal{G}$ if there is a function $f : \mathbb{N} \to \mathbb{N}$ such that every …
Bollobás proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ can contain at most …
The positive discrepancy of a graph $G$ of edge density $p$ is defined as the maximum of $e(U) - p|U|(|U|-1)/2$, where the maximum is taken over subsets of vertices in …
Delta-matroids are a generalization of matroids with connections to many parts of graph theory and combinatorics (such as matching theory and the structure of topological graph embeddings). Formally, a delta-matroid …
We say that two functors Λ and Γ between thin categories of relational structures are adjoint if for all structures A and B, we have that Λ(A) maps homomorphically to …
A family $\mathcal F$ of (di)graphs is said to have the half- or quarter-integral Erdős-Pósa property if, for any integer $k$ and any (di)graph $G$, there either exist $k$ copies …