기초과학연구원 이산수학그룹
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$ chessboard so that no queen can capture any queen of the opposite color. We consider the peaceable queens problem and its variant on the toroidal …
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 family of graph modification problems, called "$\mathcal L$-Replacement to $\mathcal H$", where the input is a graph $G$ and the question is whether it is …
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 \) is defined to be the minimum number of generators whose product is \( \pi \). It is well-known that the longest element in \( …
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 shows that for every positive integer $k$, every graph contains $k$ vertex-disjoint cycles or a set of $O(k\log k)$ vertices which intersects every cycle of $G$. …