기초과학연구원 이산수학그룹
We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every graph of sufficiently large pathwidth contains either a large complete subgraph, a large complete bipartite induced minor, or an induced minor isomorphic to H. The …
In 1996, Reed, Robertson, Seymour and Thomas proved Younger's Conjecture, which states that for all directed graphs D, there exists a function f such that if D does not contain k disjoint cycles, D contains a feedback vertex set, i.e. a subset of vertices whose deletion renders the graph acyclic, of size bounded by f(k). …
Since the proof of the graph minor structure theorem by Robertson and Seymour in 2004, its underlying ideas have found applications in a much broader range of settings than their original context. They have driven profound progress in areas such as vertex minors, pivot minors, matroids, directed graphs, and 2-dimensional simplicial complexes. In this talk, …
The dimension of a poset is the least integer
By utilizing the recently developed hypergraph analogue of Godsil's identity by the second author, we prove that for all
In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem. The theorem states the existence of a function f such that every digraph of directed tree-width f(k) contains a cylindrical grid of order k as a butterfly minor, but the given function grows non-elementarily with the size of the grid minor. We present an alternative …
We solve a long-standing open problem posed by Goodman and Pollack in 1988 by establishing a necessary and sufficient condition for a finite family of convex sets in
A rooted spanning tree of a graph
What causes a graph to have high chromatic number? One obvious reason is containing a large clique (a set of pairwise adjacent vertices). This naturally leads to investigation of
Modern practical software libraries that are designed for isomorphism tests and symmetry computation rely on combinatorial techniques combined with techniques from algorithmic group theory. The Weisfeiler-Leman algorithm is such a combinatorial technique. When taking a certain view from descriptive complexity theory, the algorithm is universal. After an introduction to problems arising in symmetry computation and …