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“.
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.
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 simplical complex consisting of subsets of vertices not covering all edges. The title of her talk was “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.
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.