MinkiKim

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 …

We prove that if $n \geq 3$, then any family of $3n-3$ sets of matchings of size $n$ in any graph has a rainbow matching of size $n$. This improves on a previous result, in which $3n-3$ is replaced by $3n-2$. We also prove a "cooperative" generalization: for $t > 0$ and $n \geq 3$, …