Skip to main content

Jonathan Leake: Log-concavity of independence sets of claw-free graphs via stable polynomials

Time: Tue 2020-03-03 11.00 - 11.50

Location: Institut Mittag-Leffler, Seminar Hall Kuskvillan

Participating: Jonathan Leake, University of California, Berkeley


In 2007, Chudnovsky and Seymour proved that the independence polynomial of a claw-free graph G is real-rooted. This implies log-concavity and unimodality of the number of independent sets of size k of a claw-free graph. They prove this result by inducting on certain subgraphs of G and showing "compatibility" of the associated independence polynomials. In this talk, we simplify their proof by generalizing to the multivariate independence polynomial of G. In fact we prove a more general result due to Engström, taking many aspects of polynomial stability theory (as in the work of Borcea and Brändén) as inspiration. As a comment, this work was done prior to the development of Lorentzian polynomials, and so connections to the Lorentzian notion are as-of-yet unknown. It would be interesting if such connections were to exist. (Note: this is joint work with Nick Ryder.)