기초과학연구원 이산수학그룹
A major goal of additive combinatorics is to understand the structures of subsets A of an abelian group G which has a small doubling K = |A+A|/|A|. Freiman's celebrated theorem …
The peaceable queens problem asks to determine the maximum number $a(n)$ such that there is a placement of $a(n)$ white queens and $a(n)$ black queens on an $n \times n$ …
A replacement action is a function $\mathcal L$ that maps each graph to a collection of subgraphs of smaller size. Given a graph class $\mathcal H$, we consider a general …
The group \( S_n \) of permutations on \(=\{1,2,\dots,n\} \) is generated by simple transpositions \( s_i = (i,i+1) \). The length \( \ell(\pi) \) of a permutation \( \pi …
An induced packing of cycles in a graph is a set of vertex-disjoint cycles such that the graph has no edge between distinct cycles of the set. The classic Erdős-Pósa theorem …
A family $\mathcal{F}$ of graphs is said to satisfy the Erdős-Pósa property if there exists a function $f$ such that for every positive integer $k$, every graph $G$ contains either …
We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every …
In 1996, Reed, Robertson, Seymour and Thomas proved Younger's Conjecture, which states that for all directed graphs D, there exists a function f such that if D does not contain …
Since the proof of the graph minor structure theorem by Robertson and Seymour in 2004, its underlying ideas have found applications in a much broader range of settings than their …
The dimension of a poset is the least integer $d$ such that the poset is isomorphic to a subposet of the product of $d$ linear orders. In 1983, Kelly constructed …