기초과학연구원 이산수학그룹
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 …
An archetype problem in extremal combinatorics is to study the structure of subgraphs appearing in different classes of (hyper)graphs. We will focus on such embedding problems in uniformly dense hypergraphs. …
Consider the following hat guessing game: $n$ players are placed on $n$ vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of $q$ …