Jinha Kim (김진하) gave a talk on the minimum size of a maximal independent set in a graph of bounded maximum degree at the Discrete Math Seminar

On February 15, 2022, Jinha Kim (김진하) from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on the minimum size of a maximal independent set (or equivalently, an independent dominating set) in a graph of maximum degree at most $\Delta$. The title of her talk was “Independent domination of graphs with bounded maximum degree“.

Jinha Kim (김진하), Independent domination of graphs with bounded maximum degree

An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\Delta=4$ or $\Delta\ge 6$, every connected $n$-vertex graph of maximum degree at most $\Delta$ has an independent dominating set of size at most $(1-\frac{\Delta}{ \lfloor\Delta^2/4\rfloor+\Delta })(n-1)+1$. In addition, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most $(1-\frac{\Delta}{ \lfloor\Delta^2/4\rfloor+\Delta })n$.
This is joint work with Eun-Kyung Cho, Minki Kim, and Sang-il Oum.

Jinha Kim (김진하) is awarded the Excellence Award for Young Scientist (미래인재상) by Korea Federation of Women’s Science and Technology Associations (KOFWST, 한국여성과학기술단체총연합회). Congratulations!

On November 19, 2021, Jinha Kim (김진하) of the IBS Discrete Mathematics Group received the Excellence Award for Young Scientist (미래인재상) by Korea Federation of Women’s Science and Technology Associations (KOFWST, 한국여성과학기술단체총연합회). This award was created to recognize woman scientists and engineers who have the potentials to elevate the nation’s competitiveness in science through great passion, dedication, and remarkable achievement in their work. Congratulations!

Jinha Kim explained the recent result on the Kalai-Meshulam conjecture by Zhang and Wu at the Discrete Math Seminar

On December 22, 2020, at the Discrete Math Seminar, Jinha Kim (김진하) from the IBS Discrete Mathematics Group presented the proof of the Kalai-Meshulam conjecture by Zhang and Wu, proving that for a graph G, the total Betti number of the independence complex of every induced subgraph of G is at most 1 if and only if G has no induced cycle of length 0 mod 3. The title of her talk was “On a conjecture by Kalai and Meshulam – the Betti number of the independence complex of ternary graphs“.

Jinha Kim (김진하), On a conjecture by Kalai and Meshulam – the Betti number of the independence complex of ternary graphs

Given a graph G=(V,E), the independence complex of G is the abstract simplicial complex I(G) on V whose faces are the independent sets of G. A graph is ternary if it does not contain an induced cycle of length divisible by three. Kalai and Meshulam conjectured that if G is ternary then the sum of the Betti numbers of I(G) is either 0 or 1. In this talk, I will introduce a result by Zhang and Wu, which proves the Kalai-Meshulam conjecture.

Jinha Kim (김진하) gave a talk on her work on the collapsibility of the non-cover complexes of graphs at the Discrete Math Seminar

On September 22, 2020, Jinha Kim (김진하) from the IBS Discrete Mathematics Group presented her recent work on the collapsibility of the non-cover complexes of graphs at the Discrete Math Seminar. The non-cover complex of a graph is a simplicial complex consisting of subsets of vertices not covering all edges. The title of her talk was “Collapsibility of Non-Cover Complexes of Graphs“.

Jinha Kim (김진하), Collapsibility of Non-Cover Complexes of Graphs

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 on $V$ whose faces are non-covers of $G$. Then the non-cover complex of $G$ is the combinatorial Alexander dual of the independence complex of $G$. In this talk, I will show the $(|V(G)|-i\gamma(G)-1)$-collapsibility of the non-cover complex of a graph $G$ where $i\gamma(G)$ denotes the independence domination number of $G$ using the minimal exclusion sequence method. This is joint work with Ilkyoo Choi and Boram Park.

Welcome Jinha Kim (김진하) and Minki Kim (김민기), new members of IBS Discrete Mathematics Group

The IBS Discrete Mathematics Group welcomes Dr. Jinha Kim (김진하) and Dr. Minki Kim (김민기), new research fellows at the IBS Discrete Mathematics Group from September 1, 2020.

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.

Minki Kim (김민기) received his Ph.D. from the Department of Mathematical Sciences at KAIST in 2018 under the supervision of Prof. Andreas Holmsen. Until recently, he was a postdoctoral fellow at Technion in Israel. He is interested in discrete geometry, topological combinatorics, and graph theory.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.