Betti numbers of subgraphs

Publication date: 16 November 2015

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

for all

i g e 0

and

a l p h a i n m a t h b b Z^{n}

. In fact, it suffices to consider only the first syzygy module. In particular, we prove that

for all

a l p h a i n m a t h b b Z^{n}

if and only if

G

contains a subgraph that is isomorphic to either

H

or a multipartite graph

K_{2, d o t s, 2, a, b}

.