기초과학연구원 이산수학그룹
Extremal Combinatorics studies the maximum or minimum size of finite objects (numbers, sets, graphs) satisfying certain properties. In this talk, I introduce the conjectures I solved on Extremal Combinatorics, and …
In this talk, we will discuss the problem of determining the maximum number of edges in an n-vertex k-critical graph. A graph is considered k-critical if its chromatic number is …
Configurations of axis-parallel boxes in $\mathbb{R}^d$ are extensively studied in combinatorial geometry. Despite their perceived simplicity, there are many problems involving their structure that are not well understood. I will …
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 …
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 …
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 …
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 …
The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains …
A graph class $\mathcal{G}$ has the strong Erdős-Hajnal property (SEH-property) if there is a constant $c=c(\mathcal{G}) > 0$ such that for every member $G$ of $\mathcal{G}$, either $G$ or its …