Euiwoong Lee (이의웅), Parameterized Approximability of F-Deletion Problems
Room B332 IBS (기초과학연구원)For a family F of graphs, the F-Deletion Problem asks to remove the minimum number of vertices from a given graph G to ensure that G belongs to F. One …
For a family F of graphs, the F-Deletion Problem asks to remove the minimum number of vertices from a given graph G to ensure that G belongs to F. One …
Depth and width parameters of graphs, e.g., tree-width, path-width and tree-depth, play a crucial role in algorithmic and structural graph theory. These notions are of fundamental importance in the theory …
For the past few years, I've been working on formalizing proofs in matroid theory using the Lean proof assistant. This has led me to many interesting and unexpected places. I'll …
Every (finite) matroid consists of a (finite) set called the ground set, and a collection of distinguished subsets called the independent sets. A classic example arises when the ground set …
In 1980, Burr conjectured that every directed graph with chromatic number
An edge-colored graph
We prove the following variant of Helly’s classical theorem for Hamming balls with a bounded radius. For
We say that a 0-1 matrix A contains another such matrix (pattern) P if P can be obtained from a submatrix of A by possibly changing a few 1 entries …
Rödl and Ruciński established Ramsey's theorem for random graphs. In particular, for fixed integers
In general, random walks on fractal graphs are expected to exhibit anomalous behaviors, for example heat kernel is significantly different from that in the case of lattices. Alexander and Orbach …