기초과학연구원 이산수학그룹
Let $G$ be a graph on the vertex set $V$. A vertex subset $W \subset V$ is a cover of $G$ if $V \setminus W$ is an independent set of $G$, and $W$ is a non-cover of $G$ if $W$ is not a cover of $G$. The non-cover complex of $G$ is a simplicial complex …
We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function $f$, such that for every integer $g > 0$, every graph of treewidth at least $f(g)$ contains the g×g-grid as a minor. For every …
Let $G$ be a graph on $V$ and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose faces are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of $I_n(G)$ for various classes of graphs, focusing on the class of …
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.