Skip to main content

Oleksandra Gasanova: On independence polynomials of graphs

Time: Mon 2022-02-07 15.00 - 16.00

Location: Zoom

Video link: Meeting ID: 674 4199 2748

Participating: Oleksandra Gasanova (Uppsala)

Export to calendar


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.