기초과학연구원 이산수학그룹
The Grid Theorem of Robertson and Seymour is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for …
A notion of sublinear expander has played a central role in the resolutions of a couple of long-standing conjectures in embedding problems in graph theory, including e.g. the odd cycle …
A signed graph is a graph in which each edge has a positive or negative sign. Calling two graphs switch equivalent if one can get from one to the other …
Given a graph, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion, …
A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all …
Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example, consider classes of bounded tree- or clique-width. Since the 1990s, many directed analogues of …
A convex lattice polytope is the convex hull of a set of integral points. Vershik conjectured the existence of a limit shape for random convex lattice polygons, and three proofs …
Given a minor-closed graph class ${\cal G}$, the (minor) obstruction of ${\cal G}$ is the set of all minor-minimal graphs not in ${\cal G}$. Given a non-negative integer $k$, we define …
Let $\mathbb{F}_q$ be a finite field of order $q$ which is a prime power. In the finite field setting, we say that a function $\phi\colon \mathbb{F}_q^d\times \mathbb{F}_q^d\to \mathbb{F}_q$ is a Mattila-Sjölin …
Recently, significant progress has been made in the area of machine learning algorithms, and they have quickly become some of the most exciting tools in a scientist’s toolbox. In particular, …