Oleksandra Gasanova: On independence polynomials of graphs

Abstract

Let G be a simple graph. An independent set in G is a set of pairwise non-adjacent vertices of G. The independence polynomial of G is defined to be the generating function of the sequence \(\{s_k(G)\}\), where \(s_k(G)\) is the number of independent sets of G of cardinality k. There are several open questions related to this topic, for instance, it is conjectured that the independence polynomial of any tree is unimodal.

In my (mostly survey) talk I will give the necessary background and demonstrate a way to translate the question above into the language of commutative algebra. Indeed, to every graph one can associate a monomial Artinian algebra in such a way that the independent sets of G of cardinality k are in bijection with monomials of degree k of this algebra and therefore the independence polynomial of G is nothing but the Hilbert Series of this algebra. Given that the conjecture above concerns unimodality, one natural question we will discuss is whether we can make use of the Lefschetz properties.