Betti numbers of subgraphs

Abstract

Let $G$ be a simple graph on $n$ vertices. Let $H$ be either the complete graph $K_m$ or the complete bipartite graph $K_{r,s}$ on a subset of the vertices in $G$. We show that $G$ contains $H$ as a subgraph if and only if ${\beta }_{i,\alpha }(H)\le {\beta }_{i,\alpha }(G)$ for all $i\ge 0$ and $\alpha \in {\mathbb{Z}}^n$. In fact, it suffices to consider only the first syzygy module. In particular, we prove that ${\beta }_{1,\alpha }(H)\le {\beta }_{1,\alpha }(G)$ for all $\alpha \in {\mathbb{Z}}^n$ if and only if $G$ contains a subgraph that is isomorphic to either $H$ or a multipartite graph $K_{2,\dots ,2,a,b}$.

12 pages

References in corpus (1)

• Betti Numbers of Graph Ideals