기초과학연구원 이산수학그룹
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 …
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 …
The dimension of a poset is the least integer $d$ such that the poset is isomorphic to a subposet of the product of $d$ linear orders. In 1983, Kelly constructed …
By utilizing the recently developed hypergraph analogue of Godsil's identity by the second author, we prove that for all $n \geq k \geq 2$, one can reconstruct the matching polynomial …
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 …
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 $\mathbb{R}^d$ to …
A rooted spanning tree of a graph $G$ is called normal if the endvertices of all edges of $G$ are comparable in the tree order. It is well known that …
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 \(\chi\)-bounded …
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 …
Let S and T be two sets of points in a metric space with a total of n points. Each point in S and T has an associated value that specifies an upper limit on how many points it can …