기초과학연구원 이산수학그룹
We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking, this happens when the metric space is (i) expanding and (ii) well-spread, …
Motivated from the surrounding property of a point set in $\mathbb{R}^d$ introduced by Holmsen, Pach and Tverberg, we consider the transversal number and chromatic number of a simplicial sphere. As …
A geometric transversal to a family of convex sets in $\mathbb R^d$ is an affine flat that intersects the members of the family. While there exists a far-reaching theory concerning …
The Caccetta-Haggkvist conjecture, one of the best known in graph theory, is that in a digraph with $n$ vertices in which all outdegrees are at least $n/k$ there is a …
For given $k$ graphs $G_1,\dots, G_k$ over a common vertex set of size $n$, what conditions on $G_i$ ensures a 'colorful' copy of $H$, i.e. a copy of $H$ containing …
Graph Minor project by Robertson and Seymour is perhaps the deepest theory in Graph Theory. It gives a deep structural characterization of graphs without any graph $H$ as a minor. …
In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly …
Our talk will mainly focus on the relationship between substructures and eigenvalues of graphs. We will briefly survey recent developments on a conjecture of Bollobás and Nikiforov and a classical …
Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all …
We prove that there is a function $f : \mathbb{N} \to \mathbb{N}$ such that for every function $g : \mathbb{N} \to \mathbb{N} \cup \{\infty\}$ with $g(1)=1$ and $g \ge f$, …