기초과학연구원 이산수학그룹
We consider the spanning tree embedding problem in dense graphs without bipartite holes and sparse graphs. In 2005, Alon, Krivelevich and Sudakov asked for determining the best possible spectral gap …
Pivot-minors can be thought of as a dense analogue of graph minors. We shall discuss pivot-minors and two recent results for proper pivot-minor-closed classes of graphs. In particular, that for …
In 2006, Tao established the Gaussian counterpart of the celebrated Green-Tao theorem on arithmetic progressions of primes. In this talk, I will explain the extension of Tao's theorem and the …
For a given graph $H$, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of …
In many different areas of mathematics (such as number theory, discrete geometry, and combinatorics), one is often presented with a large "unstructured" object, and asked to find a smaller "structured" …
The Ramsey number $R(k)$ is the minimum n such that every red-blue colouring of the edges of the complete graph on n vertices contains a monochromatic copy of $K_k$. It …
Recently, Letzter proved that any graph of order n contains a collection P of $O(n \log^*n)$ paths with the following property: for all distinct edges e and f there exists …
Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition …
We study the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$, we prove that every graph on $n$ vertices with average degree …
We define new graph parameters, called flip-width, that generalize treewidth, degeneracy, and generalized coloring numbers for sparse graphs, and clique-width and twin-width for dense graphs. The flip-width parameters are defined …