On February 23, 2021, Minki Kim (김민기) from the IBS discrete mathematics group presented a talk on the existence of a rainbow matching of size n in a family of 3n-3 matchings for n>2 at the Discrete Math Seminar. The title of his talk was “Rainbow paths and rainbow matchings“.
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$, any $3n-4+t$ sets of edges, the union of every $t$ of which contains a matching of size $n$, have rainbow matching of size $n$. This is joint work with Ron Aharoni, Joseph Briggs, and Jinha Kim.
On September 29, 2020, Minki Kim (김민기) from the IBS Discrete Mathematics Group presented his work on the collapsibility of the complex $I_n(G)$ of vertex sets of a graph $G$ not containing any $n$-vertex independent set at the Discrete Math Seminar. The title of his talk was “Complexes of graphs with bounded independence number“.
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 graphs with bounded maximum degree. This is joint work with Alan Lew.
Jinha Kim (김진하) received his Ph.D. from the Department of Mathematics at Seoul National University in 2019 under the supervision of Prof. Woong Kook. Until recently, she was a postdoctoral fellow at Technion in Israel. She is interested in combinatorics, discrete geometry, topological combinatorics, and graph theory.