기초과학연구원 이산수학그룹
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 …
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 …
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 …
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 …
An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is …
Tutte (1961) proved that every simple $3$-connected graph $G$ has an edge $e$ such that $G \setminus e$ or $G / e$ is simple $3$-connected, unless $G$ is isomorphic to …
Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for …
This talk follows on from the recent talk of Pascal Gollin in this seminar series, but will aim to be accessible for newcomers. Erdős and Pósa proved in 1965 that …
It is known that the rank- and tree-width of the random graph $G(n,p)$ undergo a phase transition at $p = 1/n$; whilst for subcritical $p$, the rank- and tree-width are bounded above …
The Ramsey number $R(F,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a …