기초과학연구원 이산수학그룹
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 of the most common ways to obtain an interesting family F is to fix another family H of graphs and let F be the set …
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 of graph minors, fixed parameter complexity and the theory of sparsity. In this talk, we will survey structural and algorithmic results that concern width and …
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 talk about what formalization looks like in practice from the perspective of a combinatorialist.
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 is a finite set of vectors from a vector space, and the independent subsets are exactly the subsets that are linearly independent. Any such matroid …